Non-cyclical Hamiltonian?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Non-cyclical Hamiltonian?

Darrell Esau
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
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Non-cyclical Hamiltonian?

Chris Esposito
Determining the existence of Hamiltonian paths in graphs is NP-Complete, 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 <[hidden email]> 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
> _______________________________________________
> jgrapht-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users

------------------------------------------------------------------------------
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
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Non-cyclical Hamiltonian?

Darrell Esau
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 <[hidden email]> wrote:
Determining the existence of Hamiltonian paths in graphs is NP-Complete, 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 <[hidden email]> 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
> _______________________________________________
> jgrapht-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Non-cyclical Hamiltonian?

Joris Kinable
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 NP-hard. 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 <[hidden email]> 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 <[hidden email]> wrote:
Determining the existence of Hamiltonian paths in graphs is NP-Complete, 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 <[hidden email]> 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
> _______________________________________________
> jgrapht-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
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
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
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
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users