Graph Theory Algorithms

Question

I am working on to get all the possible paths starting from a Node 'A' and ending at the same node. The graph is a directed graph ( i.e each node is connected to at least one node ).

The constraints are : I can visit a node exactly once, except for , ( of course the starting node).

The Problem : I tried to implement this using graphraverse function in MATLAB , but it gives me only one such way. Any algorithm or logic that can be implemented in C, java would work.

I would be glad if someone can give me any pointers to it .

Note: I don't want the shortest path, I want a set of possible paths.

This problem is called "getting the list of cycles in a directed graph." These keywords may help you find the answer, as one [has been posted on SO before](https://stackoverflow.com/a/2794683/6323677). — bream, Jun 16 '22 at 01:20

arne.b · Answer 1 · 2018-02-19T09:17:33.423

Why not write your own recursive function?

findPath(Node start, Node end, List<Node> alreadyVisited)
    for (Node neighbor: other ends of outgoing edges from start) { 
         if (neighbor == end)
             display("Found a path: " + alreadyVisited + end)
         else if (neighbor not in alreadyVisited)
             findPath(neighbor, end, alreadyVisited + neighbor)
    }

...or something alike. Since you look for cycles, the initial call should have the same value passed to start and end. Of course, if output to the prompt is not sufficient, you need to collect the correct paths in a global array or find a more elegant way of returning them.

Also, doing a bidirectional search (following incoming edges simultaneously and checking for the intersection of nodes reached by consecutive outgoing edges and consecutive incoming edges instead of only whether the desired end point has been reached) should be faster for larger graphs.

@Brackets I do not remember why I added a `graph` parameter - it does not seem necessary so I removed it. If each `Node` contains a list of its neighbors, no separate Graph class is needed. — arne.b, Feb 19 '18 at 09:20

score -1 · Answer 2 · answered Jun 11 '12 at 07:57

-1

Don't know your level but the boost library is very good if you can get it configured correctly

answered Jun 11 '12 at 07:57

Paul de Lange

10,613
10
41
56

@Jochen : I guess there are finite no. of paths , because I can't visit any intermediate node more than once. Also since there are very few nodes that trace back to the starting node , if we can find all the paths between starting nodes and those nodes , it would be solved – NG_21 Jun 11 '12 at 08:26

Graph Theory Algorithms

2 Answers2