Finding all paths between 2 nodes undirected multigraph

Discussion in 'C++' started by nick, Sep 9, 2008.

  1. nick

    nick Guest

    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
    nick, Sep 9, 2008
    #1
    1. Advertising

  2. On Sep 9, 1:57 am, nick <> 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-
    Le Chaud Lapin, Sep 12, 2008
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    372
  2. Noah
    Replies:
    5
    Views:
    751
  3. disappearedng
    Replies:
    0
    Views:
    355
    disappearedng
    Jul 22, 2009
  4. disappearedng
    Replies:
    0
    Views:
    1,433
    disappearedng
    Jul 22, 2009
  5. Replies:
    6
    Views:
    520
    Öö Tiib
    Jul 29, 2013
Loading...

Share This Page