Le Chaud Lapin
9/12/2008 5:28:00 AM
On Sep 9, 1:57 am, nick <freesof...@gmail.com> wrote:
> 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-