Recommended Algo for Finding Paths in a Graph with Loops

[alex.pico]

brunolnetto commented:

Hi,

I am a new user of Cytoscape and have no patience to explore exhaustively the library myself. There is a well-known use case for traversing a graph from point A to point B. I am pretty sure this library comprehends the "linear" case, since the topic is broadly researched, and called depth and breadth traverse. My question refers to the case when loops appear on the original graph. In this case, the previously mentioned algorithm gets stuck on these cycles, both in directed and undirected structures.

Since you have much more resources than myself, I propose adapting the algorithm available on this repository.

The rationale is:

1. Find non-cyclic paths
2. Find cycles (Tarjan algorithm)
3. Find the intersection between each non-cyclic path and cycle (Extended Venn/Euler algorithm: implementation here);
4. Find the intersection between cycles themselves (Extended Venn/Euler algorithm: implementation here);
5. Find in and out vertices on non-cyclic paths to cycles;
6. Find paths from out to in vertices along cycles;
7. Glue these cyclic-paths on non-cyclic paths;

I thank you for your attention.