1// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
2// Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
3// Distributed under the Boost Software License, Version 1.0. (See
4// accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7#include <iostream>
8#include <cstdlib>
9#include <ctime>
10
11#include <boost/graph/vector_as_graph.hpp>
12#include <boost/graph/adjacency_list.hpp>
13#include <boost/graph/adjacency_list_io.hpp>
14#include <boost/graph/graph_utility.hpp>
15#include <boost/graph/transitive_closure.hpp>
16#include <boost/timer/timer.hpp>
17
18using namespace std;
19using namespace boost;
20
21void generate_graph(int n, double p, vector< vector< int > >& r1)
22{
23 static class
24 {
25 public:
26 double operator()() { return double(rand()) / RAND_MAX; }
27 } gen;
28 r1.clear();
29 r1.resize(new_size: n);
30 for (int i = 0; i < n; ++i)
31 for (int j = 0; j < n; ++j)
32 if (gen() < p)
33 r1[i].push_back(x: j);
34}
35
36template < class Graph >
37typename graph_traits< Graph >::degree_size_type num_incident(
38 typename graph_traits< Graph >::vertex_descriptor u,
39 typename graph_traits< Graph >::vertex_descriptor v, const Graph& g)
40{
41 typename graph_traits< Graph >::degree_size_type d = 0;
42 typename graph_traits< Graph >::out_edge_iterator i, i_end;
43 for (boost::tie(i, i_end) = out_edges(u, g); i != i_end; ++i)
44 if (target(*i, g) == v)
45 ++d;
46 return d;
47}
48
49// (i,j) is in E' iff j is reachable from i
50// Hmm, is_reachable does not detect when there is a non-trivial path
51// from i to i. It always returns true for is_reachable(i,i).
52// This needs to be fixed/worked around.
53template < typename Graph, typename GraphTC >
54bool check_transitive_closure(Graph& g, GraphTC& tc)
55{
56 typename graph_traits< Graph >::vertex_iterator i, i_end;
57 for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i)
58 {
59 typename graph_traits< Graph >::vertex_iterator j, j_end;
60 for (boost::tie(j, j_end) = vertices(g); j != j_end; ++j)
61 {
62 bool g_has_edge;
63 typename graph_traits< Graph >::edge_descriptor e_g;
64 typename graph_traits< Graph >::degree_size_type num_tc;
65 boost::tie(e_g, g_has_edge) = edge(*i, *j, g);
66 num_tc = num_incident(*i, *j, tc);
67 if (*i == *j)
68 {
69 if (g_has_edge)
70 {
71 if (num_tc != 1)
72 return false;
73 }
74 else
75 {
76 bool can_reach = false;
77 typename graph_traits< Graph >::adjacency_iterator k, k_end;
78 for (boost::tie(k, k_end) = adjacent_vertices(*i, g);
79 k != k_end; ++k)
80 {
81 std::vector< default_color_type > color_map_vec(
82 num_vertices(g));
83 if (is_reachable(*k, *i, g,
84 boost::make_iterator_property_map(
85 color_map_vec.begin(),
86 get(boost::vertex_index, g))))
87 {
88 can_reach = true;
89 break;
90 }
91 }
92 if (can_reach)
93 {
94 if (num_tc != 1)
95 {
96 std::cout << "1. " << *i << std::endl;
97 return false;
98 }
99 }
100 else
101 {
102 if (num_tc != 0)
103 {
104 std::cout << "2. " << *i << std::endl;
105 return false;
106 }
107 }
108 }
109 }
110 else
111 {
112 std::vector< default_color_type > color_map_vec(
113 num_vertices(g));
114 if (is_reachable(*i, *j, g,
115 boost::make_iterator_property_map(color_map_vec.begin(),
116 get(boost::vertex_index, g))))
117 {
118 if (num_tc != 1)
119 return false;
120 }
121 else
122 {
123 if (num_tc != 0)
124 return false;
125 }
126 }
127 }
128 }
129 return true;
130}
131
132bool test(int n, double p)
133{
134 vector< vector< int > > g1, g1_tc;
135 generate_graph(n, p, r1&: g1);
136 cout << "Created graph with " << n << " vertices.\n";
137
138 vector< vector< int > > g1_c(g1);
139
140 {
141 boost::timer::auto_cpu_timer t;
142 cout << "transitive_closure" << endl;
143 transitive_closure(
144 g: g1, tc&: g1_tc, params: vertex_index_map(p: get(boost::vertex_index, g1)));
145 }
146
147 if (check_transitive_closure(g&: g1, tc&: g1_tc))
148 return true;
149 else
150 {
151 cout << "Original graph was ";
152 print_graph(G: g1, name: get(boost::vertex_index, g1));
153 cout << "Result is ";
154 print_graph(G: g1_tc, name: get(boost::vertex_index, g1_tc));
155 return false;
156 }
157}
158
159int main()
160{
161 srand(seed: time(timer: 0));
162 static class
163 {
164 public:
165 double operator()() { return double(rand()) / RAND_MAX; }
166 } gen;
167
168 for (size_t i = 0; i < 100; ++i)
169 {
170 int n = 0 + int(20 * gen());
171 double p = gen();
172 if (!test(n, p))
173 {
174 cout << "Failed." << endl;
175 return 1;
176 }
177 }
178 cout << "Passed." << endl;
179}
180

source code of boost/libs/graph/test/transitive_closure_test.cpp