All simple paths in Multigraph (Depth First Traversal)

Question

After reading and searching for quite a while, I still can't get my head around Depth First Traversal (or Search) of a Multigraph (two vertices can have more than one edge).

I found this answer on another SO question:

Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

which is a good answer, but it applies only on Simple Graphs.

So in short, I need all simple paths (no repeating vertices) from vertex A to Vertex B in a Multigraph, not just the shortest.

I'm implementing this in Java, using JGraphT, if that is of any help. I don't mind a solution in another language. The graph is directed, and weighted, if this also of any help.

P.S. I'm not concerned about the running time of the algorithm (I will cache the results).

I'm looking for output similar to the one in the linked question (I have some more information attached to the edges, but that doesn't have much to do with the traversal:

All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

Thank you.

Answer 1

Multigraphs and normal graphs shouldn't actually require different code. In both cases, you're going to need to know whether you've visited a given node on this particular path in the past. That works regardless of how many edges can connect two vertices.

Thus, what you're going to want to do is, for each path, keep a list of the vertices you've already visited, and never travel to an already-visited vertex. Thus, some pseudocode:

function DFSHelper(vertex v, array visited):
    for edge in v.edges:
        if edge.vertex_at_end not in visited:
            DFSHelper(edge.vertex_at_end, visited + [edge.vertex_at_end])
    for v in visited:
        print v + "->"

function DFS(vertex v):
    DFSHelper(v, [])

Adjust as appropriate (for example, this currently prints all subpaths of a given path, like "A", "A->B", "A->B->C", etc).

Also note that this will print some paths twice (if there are multiple edges between the same pair of vertices). You can adjust to eliminate this behavior by only traveling to vertex A from vertex B once in a given function (that is, if multiple edges connect the two, only recurse on the first edge, and ignore the rest).