| 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 | |
|---|
| 14 | int main(int argc, char* argv[]) |
|---|
| 15 | { |
|---|
| 16 | graph_t g(5), g_TC; |
|---|
| 17 | |
|---|
| 18 | add_edge(u: 0, v: 2, g_&: g); |
|---|
| 19 | add_edge(u: 1, v: 0, g_&: g); |
|---|
| 20 | add_edge(u: 1, v: 2, g_&: g); |
|---|
| 21 | add_edge(u: 1, v: 4, g_&: g); |
|---|
| 22 | add_edge(u: 3, v: 0, g_&: g); |
|---|
| 23 | add_edge(u: 3, v: 2, g_&: g); |
|---|
| 24 | add_edge(u: 4, v: 2, g_&: g); |
|---|
| 25 | add_edge(u: 4, v: 3, g_&: g); |
|---|
| 26 | |
|---|
| 27 | transitive_closure(g, tc&: 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(t0&: i, t1&: iend) = edges(g_: g_TC); i != iend; ++i) |
|---|
| 34 | { |
|---|
| 35 | cout << source(e: *i, g_TC) << "->" << target(e: *i, g_TC) << " " ; |
|---|
| 36 | } |
|---|
| 37 | cout << endl; |
|---|
| 38 | } |
|---|
| 39 | |
|---|
