## Re: [jgrapht-users] Graph with loops and self-loop.

 Re: [jgrapht-users] Graph with loops and self-loop. From: Joris Kinable - 2014-04-28 20:03:55 Attachments: Message as HTML ```Hi, I've never dealt with these kind of graphs so I'm not entirely sure what's supported in jgrapht. However, it wouldn't surprise me that there is no such algorithm in jgrapht. Any algorithm that computes a path from vertex x to a vertex y keeps track of the vertices it visited in order to prevent loops. What you want however is not very difficult to implement. Simply use an algorithm (like Breadth First Search) which computes all paths from x to y, thereby ignoring the loops. This gives you a list of paths. So based on your example this will give you path: A->B->C and A->. Then for each vertex with a self loop, you can generate all the variations on this path iteratively. For example if you have a loop on vertices B and A, this would result in: ABC (path you generated using BFS) Expansions: AABC AABBC ABBC AC (path you generated using BFS) Expansions: AAC Hope this helps. br, Joris On Mon, Apr 28, 2014 at 1:19 PM, raphaelrodrigues wrote: > Hi, i have a Graph with loops and self-loop. The objective is to get all > the > possible paths. > > With the algorithms provide by JgraphT, i can't pass through the loops. The > algorithms pass one time in the Vertex that has loops and after that the > algoritm don't get the other possible paths from this Vertex . > > For example, if i have: > A->B > A->A > A->C > > B->A > > >From (A To C) I wanna get: > Path1: A ->B->A->C > Path2: A->C > > With jgrapht i only get: > Path1: A-> C > > What i wanna know is if there a possible way to find all the path with a > limit of depth maybe? Or the best way to deal with self loops and loops? > > Thank you very much! > > > > -- > View this message in context: > http://jgrapht-users.107614.n3.nabble.com/Graph-with-loops-and-self-loop-tp4024920.html > Sent from the jgrapht-users mailing list archive at Nabble.com. > > > ------------------------------------------------------------------------------ > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE > Instantly run your Selenium tests across 300+ browser/OS combos. Get > unparalleled scalability from the best Selenium testing platform available. > Simple to use. Nothing to install. Get started now for free." > http://p.sf.net/sfu/SauceLabs > _______________________________________________ > jgrapht-users mailing list > jgrapht-users@... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > ```

 [jgrapht-users] Graph with loops and self-loop. From: raphaelrodrigues - 2014-04-28 17:19:40 ```Hi, i have a Graph with loops and self-loop. The objective is to get all the possible paths. With the algorithms provide by JgraphT, i can't pass through the loops. The algorithms pass one time in the Vertex that has loops and after that the algoritm don't get the other possible paths from this Vertex . For example, if i have: A->B A->A A->C B->A >From (A To C) I wanna get: Path1: A ->B->A->C Path2: A->C With jgrapht i only get: Path1: A-> C What i wanna know is if there a possible way to find all the path with a limit of depth maybe? Or the best way to deal with self loops and loops? Thank you very much! -- View this message in context: http://jgrapht-users.107614.n3.nabble.com/Graph-with-loops-and-self-loop-tp4024920.html Sent from the jgrapht-users mailing list archive at Nabble.com. ```
 Re: [jgrapht-users] Graph with loops and self-loop. From: Joris Kinable - 2014-04-28 20:03:55 Attachments: Message as HTML ```Hi, I've never dealt with these kind of graphs so I'm not entirely sure what's supported in jgrapht. However, it wouldn't surprise me that there is no such algorithm in jgrapht. Any algorithm that computes a path from vertex x to a vertex y keeps track of the vertices it visited in order to prevent loops. What you want however is not very difficult to implement. Simply use an algorithm (like Breadth First Search) which computes all paths from x to y, thereby ignoring the loops. This gives you a list of paths. So based on your example this will give you path: A->B->C and A->. Then for each vertex with a self loop, you can generate all the variations on this path iteratively. For example if you have a loop on vertices B and A, this would result in: ABC (path you generated using BFS) Expansions: AABC AABBC ABBC AC (path you generated using BFS) Expansions: AAC Hope this helps. br, Joris On Mon, Apr 28, 2014 at 1:19 PM, raphaelrodrigues wrote: > Hi, i have a Graph with loops and self-loop. The objective is to get all > the > possible paths. > > With the algorithms provide by JgraphT, i can't pass through the loops. The > algorithms pass one time in the Vertex that has loops and after that the > algoritm don't get the other possible paths from this Vertex . > > For example, if i have: > A->B > A->A > A->C > > B->A > > >From (A To C) I wanna get: > Path1: A ->B->A->C > Path2: A->C > > With jgrapht i only get: > Path1: A-> C > > What i wanna know is if there a possible way to find all the path with a > limit of depth maybe? Or the best way to deal with self loops and loops? > > Thank you very much! > > > > -- > View this message in context: > http://jgrapht-users.107614.n3.nabble.com/Graph-with-loops-and-self-loop-tp4024920.html > Sent from the jgrapht-users mailing list archive at Nabble.com. > > > ------------------------------------------------------------------------------ > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE > Instantly run your Selenium tests across 300+ browser/OS combos. Get > unparalleled scalability from the best Selenium testing platform available. > Simple to use. Nothing to install. Get started now for free." > http://p.sf.net/sfu/SauceLabs > _______________________________________________ > jgrapht-users mailing list > jgrapht-users@... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > ```