search

cytoscape / cytoscape-automation

Collection of scripts that include programmatic io and control of Cytoscape
Creative Commons Zero v1.0 Universal
81 stars 58 forks source link

Traverse a cyclic graph from point A to B #76

Closed brunolnetto closed 2 years ago

brunolnetto commented 2 years ago

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.

AlexanderPico commented 2 years ago

Thanks. I'll share this on the Cytoscape app developer mailing list in case anyone is interested in implementing such an algorithm in Cytoscape. https://groups.google.com/g/cytoscape-app-dev/c/F9dlCV_Cya0

This repo is for automation use cases involving CyREST, RCy3 and py4cytoscape. I'll close this issue here since it's not relevant.