Finding all paths between 2 nodes undirected multigraph

[nick]

Hi,

I have a undirected multigraph i.e there can be more than 1 edge
between 2 vertices in the undirected graph.

0 --a-- 1 --b-- 2
|__c__|__d__|

Vertices: 0, 1, 2
Edges:
0 - 1, Edge a
0 - 1, Edge c
1 - 2, Edge b
1 - 2, Edge d

Suppose I want to find all the paths between vertices 0 and 2. The
answer is: [a,b], [a,d], [c,b], [c,d].

In my implementation, I use a 'pathList' (to store each discovered
path) and a stack-based DFS. In my DFS implementation:

stack.push( target(starting_vertex)
while (!stack.empty())
{
edge e = stack.pop()
v = target(e)
if (color(v) == WHITE)
{
// tree edge
stack.push( adj_edges(v) )
pathList.append(e)
if (v == target_vertex)
break;
}
else if (color(v) == GRAY) || (color(v) == BLACK)
continue;
}
color(v) = BLACK

How can I extend this skeleton to allow for continuing the exploration
without restarting from the DFS walk from the start vertex? Instead, I
should be able to backtrack from the target_vertex back and pop out
the unwanted stack and pathList entries.

Regards
Nic

 

[Le Chaud Lapin]

Hi,

I have a undirected multigraph i.e there can be more than 1 edge
between 2 vertices in the undirected graph.

 0 --a-- 1 --b-- 2
 |__c__|__d__|

Vertices: 0, 1, 2
Edges:
  0 - 1, Edge a
  0 - 1, Edge c
  1 - 2, Edge b
  1 - 2, Edge d

Suppose I want to find all the paths between vertices 0 and 2. The
answer is: [a,b], [a,d], [c,b], [c,d].

In my implementation, I use a 'pathList' (to store each discovered
path) and a stack-based DFS. In my DFS implementation:

stack.push( target(starting_vertex)
while (!stack.empty())
{
    edge e = stack.pop()
    v = target(e)
    if (color(v) == WHITE)
   {
      // tree edge
      stack.push( adj_edges(v) )
      pathList.append(e)
      if (v == target_vertex)
          break;
   }
   else if (color(v) == GRAY) || (color(v) == BLACK)
       continue;}

color(v) = BLACK

How can I extend this skeleton to allow for continuing the exploration
without restarting from the DFS walk from the start vertex? Instead, I
should be able to backtrack from the target_vertex back and pop out
the unwanted stack and pathList entries.

Not sure if you are committed to this algorithm. If not, you could use
recursion.

The path from source vertex S to target vertex T is path from S to an
intermediate vertex I concatenated with the path from I to T.

So you would write a function

Path path (Vertex S, Vertex T)
{
if (S == T)
return Path(); // empty path assumes no self-cycles

// Accumulate all white edges sourced by S.
// If there are no white edges, then that means
// you are trapped, so...
return Path(); // again empty path
// For each such edge e,
// 1. mark it visited
// 2. determine target vertex I of e
// 3. pi = path(I, T)
// if (pi.is_empty())
// pf = Path(); // empty path
// else
// pf = e + pi
// mark all e as unvisited
// return pf.
}

I haven't checked this code, so it is most likely incorrect, but this
is basic idea.

-Le Chaud Lapin-