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 | |
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(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 | |
36 | template < class Graph > |
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 > |
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 | |
132 | bool 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 | |
159 | int 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 | |