Re: [boost] BGL: How do I find ancestors to a node?

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-01-11 16:05:34

> To answer the second quesiton (is vertex A
> an ancestor to vertex B), check the condition
>  discover_time(A) <= discover_time(B) and
>  finish_time(A) >= finish_time(B)

Consider this example graph:

  A -> B -> C

and a dfs_visitor like this:

class dfs_time_visitor : public boost::default_dfs_visitor {
public:
 dfs_time_visitor(NameMap & nm)
  : namemap(nm), time(0) {
 }
 void discover_vertex(VertexDescriptor u, Graph const & g) const {
  std::string v = namemap[u];
  std::cout << "discover_time(" << v << ") = " << time++ << std::endl;
 }
 void finish_vertex(VertexDescriptor u, Graph const & g) const {
  std::string v = namemap[u];
  std::cout << "finish_time(" << v << ") = " << time++ << std::endl;
 }
 NameMap & namemap;
 mutable int time;
};

With this, I get these results with VC6 sp5:

discover_time(A) = 0
discover_time(B) = 1
finish_time(B) = 2
discover_time(C) = 3
finish_time(C) = 4
finish_time(A) = 5

Now, according to the condition above, this results in these
ancestor-relations:

ancestor(A, A) = 1
ancestor(A, B) = 1
ancestor(A, C) = 1

ancestor(B, A) = 0
ancestor(B, B) = 1
ancestor(B, C) = 0 // !!!

ancestor(C, A) = 0
ancestor(C, B) = 0
ancestor(C, C) = 1

I would expect B to be an ancestor of C.

What am I missing?

Thanks,

Asger Alstrup