 # Boost :

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, &ftime, 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;
}
```