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
18 using namespace std;
19 using namespace boost;
20
generate_graph(int n,double p,vector<vector<int>> & r1)21 void 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(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(j);
34 }
35
36 template < class Graph >
num_incident(typename graph_traits<Graph>::vertex_descriptor u,typename graph_traits<Graph>::vertex_descriptor v,const Graph & g)37 typename 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.
53 template < typename Graph, typename GraphTC >
check_transitive_closure(Graph & g,GraphTC & tc)54 bool 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
test(int n,double p)132 bool test(int n, double p)
133 {
134 vector< vector< int > > g1, g1_tc;
135 generate_graph(n, p, 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 g1, g1_tc, vertex_index_map(get(boost::vertex_index, g1)));
145 }
146
147 if (check_transitive_closure(g1, g1_tc))
148 return true;
149 else
150 {
151 cout << "Original graph was ";
152 print_graph(g1, get(boost::vertex_index, g1));
153 cout << "Result is ";
154 print_graph(g1_tc, get(boost::vertex_index, g1_tc));
155 return false;
156 }
157 }
158
main()159 int main()
160 {
161 srand(time(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