Graph Theory Algorithms

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.

Answers


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.


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


Need Your Help

Jquery Callback function - "this"

javascript jquery jquery-ui callback

i've a jquery (UI) App here where the whole JQuery Code gets a little bit messy, so i started to think around how to structure this in a little bit fancier way... i read a blog post somewhere, that...

Problem in Interfaces (polymorphism) C#

c# interface polymorphism

i have two classes which have some common methods like