1 files changed, 156 insertions, 0 deletions
diff --git a/src/boost/libs/graph/test/transitive_closure_test.cpp b/src/boost/libs/graph/test/transitive_closure_test.cpp
new file mode 100644
index 00000000..cdae591d
--- /dev/null
+++ b/src/boost/libs/graph/test/transitive_closure_test.cpp
@@ -0,0 +1,156 @@
+// Copyright (C) 2001 Vladimir Prus <ghost@cs.msu.su>
+// Copyright (C) 2001 Jeremy Siek <jsiek@cs.indiana.edu>
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <iostream>
+#include <cstdlib>
+#include <ctime>
+
+#include <boost/graph/vector_as_graph.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/adjacency_list_io.hpp>
+#include <boost/graph/graph_utility.hpp>
+#include <boost/graph/transitive_closure.hpp>
+#include <boost/progress.hpp>
+
+using namespace std;
+using namespace boost;
+
+void generate_graph(int n, double p, vector< vector<int> >& r1)
+{
+  static class {
+  public:
+    double operator()() {
+      return double(rand())/RAND_MAX;
+    }
+  } gen;  
+  r1.clear();
+  r1.resize(n);
+  for (int i = 0; i < n; ++i)
+    for (int j = 0; j < n; ++j) 
+      if (gen() < p)
+        r1[i].push_back(j);
+}
+
+template <class Graph>
+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)
+{
+  typename graph_traits<Graph>::degree_size_type d = 0;
+  typename graph_traits<Graph>::out_edge_iterator i, i_end;
+  for (boost::tie(i, i_end) = out_edges(u, g); i != i_end; ++i)
+    if (target(*i, g) == v)
+      ++d;
+  return d;
+}
+
+
+// (i,j) is in E' iff j is reachable from i
+// Hmm, is_reachable does not detect when there is a non-trivial path
+// from i to i. It always returns true for is_reachable(i,i).
+// This needs to be fixed/worked around.
+template <typename Graph, typename GraphTC>
+bool check_transitive_closure(Graph& g, GraphTC& tc)
+{
+  typename graph_traits<Graph>::vertex_iterator i, i_end;
+  for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) {
+    typename graph_traits<Graph>::vertex_iterator j, j_end;
+    for (boost::tie(j, j_end) = vertices(g); j != j_end; ++j) {
+      bool g_has_edge;
+      typename graph_traits<Graph>::edge_descriptor e_g;
+      typename graph_traits<Graph>::degree_size_type num_tc;
+      boost::tie (e_g, g_has_edge) = edge(*i, *j, g);
+      num_tc = num_incident(*i, *j, tc);
+      if (*i == *j) {
+        if (g_has_edge) {
+          if (num_tc != 1)
+            return false;
+        } else {
+          bool can_reach = false;
+          typename graph_traits<Graph>::adjacency_iterator k, k_end;
+          for (boost::tie(k, k_end) = adjacent_vertices(*i, g); k != k_end; ++k) {
+            std::vector<default_color_type> color_map_vec(num_vertices(g));
+            if (is_reachable(*k, *i, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) {
+              can_reach = true;
+              break;
+            }
+          }
+          if (can_reach) {
+            if (num_tc != 1) {
+              std::cout << "1. " << *i << std::endl;
+              return false;
+            }
+          } else {
+            if (num_tc != 0) {
+              std::cout << "2. " << *i << std::endl;
+              return false;
+            }
+          }       
+        }
+      } else {
+        std::vector<default_color_type> color_map_vec(num_vertices(g));
+        if (is_reachable(*i, *j, g, boost::make_iterator_property_map(color_map_vec.begin(), get(boost::vertex_index, g)))) {
+          if (num_tc != 1)
+            return false;
+        } else {
+          if (num_tc != 0)
+            return false;
+        }
+      }
+    }
+  }
+  return true;
+}
+
+bool test(int n, double p)
+{
+  vector< vector<int> > g1, g1_tc;
+  generate_graph(n, p, g1);
+  cout << "Created graph with " << n << " vertices.\n";
+
+  vector< vector<int> > g1_c(g1);
+
+  {
+    progress_timer t;
+    cout << "transitive_closure" << endl;
+    transitive_closure(g1, g1_tc, vertex_index_map(get(boost::vertex_index, g1)));
+  }
+
+  if(check_transitive_closure(g1, g1_tc))
+    return true;
+  else {
+    cout << "Original graph was ";
+    print_graph(g1, get(boost::vertex_index, g1));
+    cout << "Result is ";
+    print_graph(g1_tc, get(boost::vertex_index, g1_tc));
+    return false;
+  }
+}
+
+
+int main()
+{
+  srand(time(0));
+  static class {
+  public:
+    double operator()() {
+      return double(rand())/RAND_MAX;
+    }
+  } gen;  
+
+
+  for (size_t i = 0; i < 100; ++i) {
+    int n = 0 + int(20*gen());
+    double p = gen();
+    if (!test(n, p)) {
+      cout << "Failed." << endl;
+      return 1; 
+    }
+  }
+  cout << "Passed." << endl;
+}
+