Re: [jgrapht-users] Non-cyclical Hamiltonian?

[Joris K. <de...@gm...>]

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 <de...@so...> 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 <chr...@gm...
> > 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 <de...@so...> 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
>> > jgr...@li...
>> > 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
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>