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

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

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