Graph with loops and self-loop.

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

Graph with loops and self-loop.

raphaelrodrigues
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!
Reply | Threaded
Open this post in threaded view
|

Re: Graph with loops and self-loop.

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


------------------------------------------------------------------------------
"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