Re: all paths between 2 nodes

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 04/09/04 

Date: Thu, 8 Apr 2004 16:42:57 -0600

On 8 Apr 2004, Glenn C. Rhoads wrote:

> I wrote,
>
> "Going from vertex A to vertex B when the edge is oriented
> in the opposite direction is not a path (at least not under
> my definition of path)."
>
> and you responded with,
>
> "I don't think that is anyone's definition of a path."
>
>
> There is no way to interpret your response other than
> as a disagreement, i.e. that you think a path can go
> opposite an edge's orientation.

  Say P="going when the edge is oriented in the opposite direction is not
a path."
  You say P is not valid under your definition of a path.
  I say that "I don't think that P is valid in anyone's definition of a
path."

  You are wrong to assume there was no interpretation different from how
you interpreted the statement, since you did misunderstand my sentence.

> I missed this post. Looking at it now, the explanation
> isn't all that clear. You give an example of how to
> compute the number when the graph has "levels" with all
> edges going between adjacent levels. What does your
> algorithm do when the graph doesn't look like that?
> (e.g. there could be an edge between two vertices in the
> same level).

  There will always be a "source" vertex in the remaining graph (i.e. in
the graph with the already-labeled vertices removed.)
  Anyway, it's clear that the three people discussing this algorithm know
what is going on, so let's stop nit-picking everyone's wording and
misunderstanding everyone's sentences.

> Note that both versions *must* update the values! This is
> where your "level graph" example is not general enough.
> Suppose you want to compute the number of paths from A to
> B in the following graph (view with a fixed font).
>
>
> A-----------B
> \ / / /
> \ / / /
> D--E--F
> \ /
> \ /
> G
>
>
> All edges go from left to right. Note the edges D-->B
> and E-->B (it's hard to draw in ascii).
>
> When you start at A, you cannot simply say there is one
> path from A to B and never update the number of paths
> to vertex B.

> You have to update the number of paths to B once for each incoming
> edge. So you add 1 at vertices A, D, and E, and add 2 at vertex F
> (since there are two paths to F).

  In my process, I never look at B UNTILL all vertices that point to it
have already been labeled. A will get 1, then D is a source in the
remaining graph, so D gets the sum of its in-neighbours = 1. Then G or E
are suitable next candidates. Once those are both gone, F is taken, and
then B is given the sum of the labels from A,D,E,F.

  So B is NOT updated multiple times - it is given a label once. The
ordering I gave here is simply the topsort.

  J

Relevant Pages

  • Re: all paths between 2 nodes
    ... > to directed cycles.) ... "directed acyclic graph" is a directed graph without any cycles. ... in the opposite direction is not a path (at least not under ... traverse edges in the direction opposite to their orientation, ...
    (comp.theory)
  • Re: all paths between 2 nodes
    ... it is a directed graph without any directed cycles. ... >> in the opposite direction is not a path (at least not under ... orientation of the edges deals almost exclusively with network ... flow algorithms (frequently you want to push flow in the ...
    (comp.theory)
  • Re: all paths between 2 nodes
    ... opposite an edge's orientation. ... compute the number when the graph has "levels" with all ... an incoming edge emanates from a node unreachable from the ... already have the queue code handy). ...
    (comp.theory)
  • Re: Multigraph edges
    ... edge going in the opposite direction. ... or you can simply drop the symmetric condition on the map above. ... You can think of a graph as a set V and a map ->N (the natural ...
    (sci.math)
  • Re: biconnected cyclic directed path
    ... I meant Biconnected as 2-connected or graph with no bridges. ... bridges this orientation of each edge looks fine. ... Cyclic directed path is any path ...
    (sci.math)