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 
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   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
num_incident(typename graph_traits<Graph>::vertex_descriptor u,typename graph_traits<Graph>::vertex_descriptor v,const Graph & g)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>
check_transitive_closure(Graph & g,GraphTC & tc)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 
test(int n,double p)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 
main()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 
157