1 // Copyright (C) 2004 Jeremy Siek <jsiek@cs.indiana.edu>
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5 #include <boost/graph/adjacency_list.hpp>
6 #include <boost/graph/depth_first_search.hpp>
7 #include <boost/graph/transitive_closure.hpp>
8 #include <iostream>
9 using namespace std;
10
11 using namespace boost;
12 typedef adjacency_list<> graph_t;
13
main(int argc,char * argv[])14 int main(int argc, char* argv[])
15 {
16 graph_t g(5), g_TC;
17
18 add_edge(0, 2, g);
19 add_edge(1, 0, g);
20 add_edge(1, 2, g);
21 add_edge(1, 4, g);
22 add_edge(3, 0, g);
23 add_edge(3, 2, g);
24 add_edge(4, 2, g);
25 add_edge(4, 3, g);
26
27 transitive_closure(g, g_TC);
28
29 cout << "original graph: 0->2, 1->0, 1->2, 1->4, 3->0, 3->2, 4->2, 4->3"
30 << endl;
31 cout << "transitive closure: ";
32 graph_t::edge_iterator i, iend;
33 for (boost::tie(i, iend) = edges(g_TC); i != iend; ++i)
34 {
35 cout << source(*i, g_TC) << "->" << target(*i, g_TC) << " ";
36 }
37 cout << endl;
38 }
39