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

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-01-11 18:14:57

Hi,

Hmm, I'm sorry to bother you all once more. However, I'm still having trouble
with the ancestors.

Consider this graph, where U is the source and W the sink:

   U
  / \
 V   X
 |   |
 |   Y
  \ /
   W

The program below (based on your example) gives the following result:

--
u 0, v 1, w 2, x 5, y 6,
u 9, v 4, w 3, x 8, y 7,
x ancestor to w: 0
w ancestor to x: 0
--
which is wrong, because X is an ancestor to W.
Now, if I change the order of construction of the graph, the result will
change.
For instance, the ordering
 E edge_array[] = { E(u, x), E(u, v), E(v, w), E(x, y), E(y, w) };
gives the following result, which is correct:
--
u 0, v 7, w 3, x 1, y 2,
u 9, v 8, w 4, x 6, y 5,
x ancestor to w: 1
w ancestor to x: 0
--
I must be missing something, but I can't figure out what. Can you help me?
I'm using VC6 sp5.
Thanks,
Asger Alstrup
--
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/pending/integer_range.hpp>
#include <boost/pending/indirect_cmp.hpp>
using namespace boost;
template < typename TimeMap > class dfs_time_visitor:public
default_dfs_visitor {
 typedef typename property_traits < TimeMap >::value_type T;
public:
 dfs_time_visitor(TimeMap dmap, TimeMap fmap, T & t)
  :  m_dtimemap(dmap), m_ftimemap(fmap), m_time(t) {
 }
 template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
 {
  put(m_dtimemap, u, m_time++);
 }
 template < typename Vertex, typename Graph >
  void finish_vertex(Vertex u, const Graph & g) const
 {
  put(m_ftimemap, u, m_time++);
 }
 TimeMap m_dtimemap;
 TimeMap m_ftimemap;
 T & m_time;
};
int
main()
{
 // Select the graph type we wish to use
 typedef adjacency_list < vecS, vecS, directedS > graph_t;
 typedef graph_traits < graph_t >::vertices_size_type size_type;
 // Set up the vertex names
 enum
 { u, v, w, x, y, N };
 char name[] = { 'u', 'v', 'w', 'x', 'y' };
 // Specify the edges in the graph
 typedef std::pair < int, int >  E;
 E edge_array[] = { E(u, v), E(u, x), E(v, w), E(x, y), E(y, w)
 };
#ifdef BOOST_MSVC
 graph_t g(N);
 for (std::size_t j = 0; j < sizeof(edge_array) / sizeof(E); ++j)
  add_edge(edge_array[j].first, edge_array[j].second, g);
#else
 graph_t g(edge_array, edge_array + sizeof(edge_array) / sizeof(E), N);
#endif
 // Typedefs
 typedef boost::graph_traits < graph_t >::vertex_descriptor Vertex;
 typedef size_type* Iiter;
 // discover time and finish time properties
 std::vector < size_type > dtime(num_vertices(g));
 std::vector < size_type > ftime(num_vertices(g));
 size_type t = 0;
 dfs_time_visitor < size_type * >vis(&dtime[0], &ftime[0], t);
 depth_first_search(g, visitor(vis));
 int i;
 for (i = 0; i < N; ++i)
  std::cout << name[i] << " " << dtime[i] << ", ";
 std::cout << std::endl;
 for (i = 0; i < N; ++i)
  std::cout << name[i] << " " << ftime[i] << ", ";
 std::cout << std::endl;
 std::cout << "x ancestor to w: " << (dtime[x] <= dtime[w] && ftime[x] >=
ftime[w]) << std::endl;
 std::cout << "w ancestor to x: " << (dtime[w] <= dtime[x] && ftime[w] >=
ftime[x]) << std::endl;
 return EXIT_SUCCESS;
}