Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.
Close
From: Darrell Esau <desau@so...>  20130929 05:13:47
Attachments:
Message as HTML

Hi all, Is there a way to get a hamiltonian cycle for a given node, but not actually a cycle? Given a graph and a starting node, I'd like to find a path that will cover each node exactly once, but not returning to the origin. Any advice? Thanks! darrell 
From: Chris Esposito <chris.esposito@gm...>  20130929 05:22:03

Determining the existence of Hamiltonian paths in graphs is NPComplete, so if the graph is not small the only advice I'd offer is "have patience" :) Sent from my iPad On Sep 28, 2013, at 10:13 PM, Darrell Esau <desau@...> wrote: > Hi all, > > Is there a way to get a hamiltonian cycle for a given node, but not actually a cycle? > > Given a graph and a starting node, I'd like to find a path that will cover each node exactly once, but not returning to the origin. > > Any advice? > > Thanks! > darrell >  > October Webinars: Code for Performance > Free Intel webinars can help you accelerate application performance. > Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from > the latest Intel processors and coprocessors. See abstracts and register > > http://pubads.g.doubleclick.net/gampad/clk?id=60133471&iu=/4140/ostg.clktrk > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers 
From: Darrell Esau <desau@so...>  20130929 05:35:39
Attachments:
Message as HTML

Sure  but there is a HamiltonianCycle class in JGraphT which can give an approximate optimal tour. It seems like (to the untrained eye), it's a small step to take that and remove the cyclical requirement (thus making it just a hamiltonian path), and being able to specify a start node. On Sat, Sep 28, 2013 at 10:21 PM, Chris Esposito <chris.esposito@...>wrote: > Determining the existence of Hamiltonian paths in graphs is NPComplete, > so if the graph is not small the only advice I'd offer is "have patience" > :) > > Sent from my iPad > > On Sep 28, 2013, at 10:13 PM, Darrell Esau <desau@...> wrote: > > > Hi all, > > > > Is there a way to get a hamiltonian cycle for a given node, but not > actually a cycle? > > > > Given a graph and a starting node, I'd like to find a path that will > cover each node exactly once, but not returning to the origin. > > > > Any advice? > > > > Thanks! > > darrell > > >  > > October Webinars: Code for Performance > > Free Intel webinars can help you accelerate application performance. > > Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most > from > > the latest Intel processors and coprocessors. See abstracts and register > > > > > http://pubads.g.doubleclick.net/gampad/clk?id=60133471&iu=/4140/ostg.clktrk > > _______________________________________________ > > jgraphtusers mailing list > > jgraphtusers@... > > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > 
From: Joris Kinable <deus87@gm...>  20130930 01:14:55
Attachments:
Message as HTML

What you could do is the following: Take your graph and add an extra artificial node Z which has edges to every other node. Lets say you are trying to find your hamiltonian path starting from a vertex X. Lets assume there is such a path in the original graph which starts at X and ends in node Y. In the new graph, you would have a hamiltonian cycle: [X, ... , Y, Z, X]. Your hamiltonian path can be recovered by removing node Z from the cycle. Consequently, you can use the original HamiltonianCycle class in JGraphT on the graph extended by the artificial node. Just a small remark: As noted by Chris, the HC problem is NPhard. The HamiltonianCycle class works on small instances, but is by no means optimized for large instances. If you want to solve large instances, have a look at dedicated solvers such as the Concorde TSP solver. br, Joris On Sun, Sep 29, 2013 at 1:35 AM, Darrell Esau <desau@...> wrote: > Sure  but there is a HamiltonianCycle class in JGraphT which can give an > approximate optimal tour. It seems like (to the untrained eye), it's a > small step to take that and remove the cyclical requirement (thus making it > just a hamiltonian path), and being able to specify a start node. > > > > > On Sat, Sep 28, 2013 at 10:21 PM, Chris Esposito <chris.esposito@... > > wrote: > >> Determining the existence of Hamiltonian paths in graphs is NPComplete, >> so if the graph is not small the only advice I'd offer is "have patience" >> :) >> >> Sent from my iPad >> >> On Sep 28, 2013, at 10:13 PM, Darrell Esau <desau@...> wrote: >> >> > Hi all, >> > >> > Is there a way to get a hamiltonian cycle for a given node, but not >> actually a cycle? >> > >> > Given a graph and a starting node, I'd like to find a path that will >> cover each node exactly once, but not returning to the origin. >> > >> > Any advice? >> > >> > Thanks! >> > darrell >> > >>  >> > October Webinars: Code for Performance >> > Free Intel webinars can help you accelerate application performance. >> > Explore tips for MPI, OpenMP, advanced profiling, and more. Get the >> most from >> > the latest Intel processors and coprocessors. See abstracts and >> register > >> > >> http://pubads.g.doubleclick.net/gampad/clk?id=60133471&iu=/4140/ostg.clktrk >> > _______________________________________________ >> > jgraphtusers mailing list >> > jgraphtusers@... >> > https://lists.sourceforge.net/lists/listinfo/jgraphtusers >> > > > >  > October Webinars: Code for Performance > Free Intel webinars can help you accelerate application performance. > Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most > from > the latest Intel processors and coprocessors. See abstracts and register > > http://pubads.g.doubleclick.net/gampad/clk?id=60133471&iu=/4140/ostg.clktrk > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > 