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! |
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 <[hidden email]> wrote: Hi, i have a Graph with loops and self-loop. The objective is to get all the ------------------------------------------------------------------------------ "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 [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
Free forum by Nabble | Edit this page |