jgrapht-users

[jgrapht-users] finding all paths from one vertex to another

[guille l. <gui...@gm...>]

Hi,

I want to find all possible paths between two vertex in a
SimpleDirectedGraph (no loops and no multiple edges). I was going to
do it using the DepthFirstIterator, but I'm just wondering if there is
already a way to do it with JGraphT. I've seen the KShortestPath
algorithm, but I'm not sure if it is appropriate for what I want since
I just need all path (so I thought it may be easier to get them from a
DFS). Anyway, I'll appreciate some suggestion since I'm new JGraphT
and i'm not yet very familiar with its API.

thanks,

guille

Re: [jgrapht-users] finding all paths from one vertex to another

[John V. S. <js...@gm...>]

guille lists wrote:
> I want to find all possible paths between two vertex in a
> SimpleDirectedGraph (no loops and no multiple edges). I was going to
> do it using the DepthFirstIterator, but I'm just wondering if there is
> already a way to do it with JGraphT. I've seen the KShortestPath
> algorithm, but I'm not sure if it is appropriate for what I want since
> I just need all path (so I thought it may be easier to get them from a
> DFS). Anyway, I'll appreciate some suggestion since I'm new JGraphT
> and i'm not yet very familiar with its API.

This question comes up a lot...for an arbitary graph, the number of 
paths between two vertices can be huge (consider a complete graph, for 
instance), so we don't provide a method for it.  I'll bet there's some 
value of K above which you wouldn't want to get any more :)

JVS

Re: [jgrapht-users] finding all paths from one vertex to another

[from.pampas <mar...@gm...>]

Guille, did you find the way? do you have any advise to start with the same
issue that you have?
Thanks
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p976521.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] finding all paths from one vertex to another

[from.pampas <mar...@gm...>]

I've found an interesting paper with a very easy algorithm to explore all
possible paths...
"APAC: An exact algorithm for retrieving cycles and paths in all kind of
graphs by Ricardo Simoes (2009)"
As is very easy to understand, it's easy to adapt as well. 
Hoping to be useful to someone

from.pampas
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p994056.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] finding all paths from one vertex to another

[DanielAgota <ago...@gm...>]

Hi,

do you need the exact paths?
You could rewrite/extend the BreadhtFirstIterator for instance... take a
look at the encounterVertex/encounterVertexAgain methods.

I have used/extended the methods above to count the number of shortest paths
between one StartVertex and all the others and get their distances from the
start vertex - the length of the shortest path.

You could also use the FloydWarhallShortestPaths (check spelling) class, if
you know the maximal number of paths you are interested in.

Or combine the two, to find the number of shortest paths and list them :)
... it definitely won't scale very good...

Regards, Daniel
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p995888.html
Sent from the jgrapht-users mailing list archive at Nabble.com.

Re: [jgrapht-users] finding all paths from one vertex to another

[honza <jan...@ag...>]

Hi,
I need the same algorithm. Have you implemented it? Can you provide me with
your implementation?
Thanks!

--
View this message in context: http://jgrapht-users.107614.n3.nabble.com/finding-all-paths-from-one-vertex-to-another-tp108000p4024717.html
Sent from the jgrapht-users mailing list archive at Nabble.com.