]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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/progress.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 | public: | |
25 | double operator()() { | |
26 | return double(rand())/RAND_MAX; | |
27 | } | |
28 | } gen; | |
29 | r1.clear(); | |
30 | r1.resize(n); | |
31 | for (int i = 0; i < n; ++i) | |
32 | for (int j = 0; j < n; ++j) | |
33 | if (gen() < p) | |
34 | r1[i].push_back(j); | |
35 | } | |
36 | ||
37 | template <class Graph> | |
38 | typename graph_traits<Graph>::degree_size_type | |
39 | num_incident(typename graph_traits<Graph>::vertex_descriptor u, | |
40 | typename graph_traits<Graph>::vertex_descriptor v, | |
41 | const Graph& g) | |
42 | { | |
43 | typename graph_traits<Graph>::degree_size_type d = 0; | |
44 | typename graph_traits<Graph>::out_edge_iterator i, i_end; | |
45 | for (boost::tie(i, i_end) = out_edges(u, g); i != i_end; ++i) | |
46 | if (target(*i, g) == v) | |
47 | ++d; | |
48 | return d; | |
49 | } | |
50 | ||
51 | ||
52 | // (i,j) is in E' iff j is reachable from i | |
53 | // Hmm, is_reachable does not detect when there is a non-trivial path | |
54 | // from i to i. It always returns true for is_reachable(i,i). | |
55 | // This needs to be fixed/worked around. | |
56 | template <typename Graph, typename GraphTC> | |
57 | bool check_transitive_closure(Graph& g, GraphTC& tc) | |
58 | { | |
59 | typename graph_traits<Graph>::vertex_iterator i, i_end; | |
60 | for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) { | |
61 | typename graph_traits<Graph>::vertex_iterator j, j_end; | |
62 | for (boost::tie(j, j_end) = vertices(g); j != j_end; ++j) { | |
63 | bool g_has_edge; | |
64 | typename graph_traits<Graph>::edge_descriptor e_g; | |
65 | typename graph_traits<Graph>::degree_size_type num_tc; | |
66 | boost::tie (e_g, g_has_edge) = edge(*i, *j, g); | |
67 | num_tc = num_incident(*i, *j, tc); | |
68 | if (*i == *j) { | |
69 | if (g_has_edge) { | |
70 | if (num_tc != 1) | |
71 | return false; | |
72 | } else { | |
73 | bool can_reach = false; | |
74 | typename graph_traits<Graph>::adjacency_iterator k, k_end; | |
75 | for (boost::tie(k, k_end) = adjacent_vertices(*i, g); k != k_end; ++k) { | |
76 | std::vector<default_color_type> color_map_vec(num_vertices(g)); | |
77 | if (is_reachable(*k, *i, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) { | |
78 | can_reach = true; | |
79 | break; | |
80 | } | |
81 | } | |
82 | if (can_reach) { | |
83 | if (num_tc != 1) { | |
84 | std::cout << "1. " << *i << std::endl; | |
85 | return false; | |
86 | } | |
87 | } else { | |
88 | if (num_tc != 0) { | |
89 | std::cout << "2. " << *i << std::endl; | |
90 | return false; | |
91 | } | |
92 | } | |
93 | } | |
94 | } else { | |
95 | std::vector<default_color_type> color_map_vec(num_vertices(g)); | |
96 | if (is_reachable(*i, *j, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) { | |
97 | if (num_tc != 1) | |
98 | return false; | |
99 | } else { | |
100 | if (num_tc != 0) | |
101 | return false; | |
102 | } | |
103 | } | |
104 | } | |
105 | } | |
106 | return true; | |
107 | } | |
108 | ||
109 | bool test(int n, double p) | |
110 | { | |
111 | vector< vector<int> > g1, g1_tc; | |
112 | generate_graph(n, p, g1); | |
113 | cout << "Created graph with " << n << " vertices.\n"; | |
114 | ||
115 | vector< vector<int> > g1_c(g1); | |
116 | ||
117 | { | |
118 | progress_timer t; | |
119 | cout << "transitive_closure" << endl; | |
120 | transitive_closure(g1, g1_tc, vertex_index_map(get(boost::vertex_index, g1))); | |
121 | } | |
122 | ||
123 | if(check_transitive_closure(g1, g1_tc)) | |
124 | return true; | |
125 | else { | |
126 | cout << "Original graph was "; | |
127 | print_graph(g1, get(boost::vertex_index, g1)); | |
128 | cout << "Result is "; | |
129 | print_graph(g1_tc, get(boost::vertex_index, g1_tc)); | |
130 | return false; | |
131 | } | |
132 | } | |
133 | ||
134 | ||
135 | int main() | |
136 | { | |
137 | srand(time(0)); | |
138 | static class { | |
139 | public: | |
140 | double operator()() { | |
141 | return double(rand())/RAND_MAX; | |
142 | } | |
143 | } gen; | |
144 | ||
145 | ||
146 | for (size_t i = 0; i < 100; ++i) { | |
147 | int n = 0 + int(20*gen()); | |
148 | double p = gen(); | |
149 | if (!test(n, p)) { | |
150 | cout << "Failed." << endl; | |
151 | return 1; | |
152 | } | |
153 | } | |
154 | cout << "Passed." << endl; | |
155 | } | |
156 |