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