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