1 files changed, 124 insertions, 0 deletions
diff --git a/src/boost/libs/graph/test/random_matching_test.cpp b/src/boost/libs/graph/test/random_matching_test.cpp
new file mode 100644
index 00000000..7622e694
--- /dev/null
+++ b/src/boost/libs/graph/test/random_matching_test.cpp
@@ -0,0 +1,124 @@
+//=======================================================================
+// Copyright (c) 2005 Aaron Windsor
+//
+// 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 <cstdlib>
+#include <iostream>
+#include <boost/property_map/vector_property_map.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/random.hpp>
+#include <ctime>
+#include <boost/random.hpp>
+
+#include <boost/graph/max_cardinality_matching.hpp>
+
+using namespace boost;
+
+typedef adjacency_list<vecS, 
+                       vecS, 
+                       undirectedS, 
+                       property<vertex_index_t, int> >  undirected_graph;
+
+typedef property_map<undirected_graph,vertex_index_t>::type vertex_index_map_t;
+typedef vector_property_map<graph_traits<undirected_graph>::vertex_descriptor, vertex_index_map_t > mate_t;
+typedef graph_traits<undirected_graph>::vertex_iterator vertex_iterator_t;
+typedef graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor_t;
+typedef graph_traits<undirected_graph>::vertices_size_type v_size_t;
+
+
+int main(int argc, char** argv)
+{  
+  if (argc < 3)
+    {
+      std::cout << "Usage: " << argv[0] << " n m" << std::endl
+                << "Tests the checked matching on a random graph w/ n vertices and m edges" << std::endl;
+      exit(-1);
+    }
+  
+  int n = atoi(argv[1]);
+  int m = atoi(argv[2]);
+
+  undirected_graph g(n);
+  
+
+  typedef boost::mt19937 base_generator_type;
+  base_generator_type generator(static_cast<unsigned int>(std::time(0)));
+  boost::uniform_int<> distribution(0, n-1);
+  boost::variate_generator<base_generator_type&, boost::uniform_int<> > rand_num(generator, distribution);
+
+  int num_edges = 0;
+  bool success;
+
+  while (num_edges < m)
+    {
+      vertex_descriptor_t u = random_vertex(g,rand_num);
+      vertex_descriptor_t v = random_vertex(g,rand_num);
+      if (u != v)
+        {
+          if (!edge(u,v,g).second)
+            boost::tie(tuples::ignore, success) = add_edge(u, v, g);
+          else
+            success = false;
+
+          if (success)
+            num_edges++;
+        }
+    }
+
+  mate_t mate(n);
+  bool random_graph_result = checked_edmonds_maximum_cardinality_matching(g,mate);  
+ 
+  if (!random_graph_result)
+    {
+      std::cout << "TEST 1 FAILED!!!" << std::endl << std::endl;
+
+      std::cout << "Graph has edges: ";
+      typedef graph_traits<undirected_graph>::edge_iterator edge_iterator_t;
+      edge_iterator_t ei,ei_end;
+      for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
+        std:: cout << *ei << ", ";
+      std::cout << std::endl;
+      
+      std::cout << "Matching is: ";
+      vertex_iterator_t vi, vi_end;
+      for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
+        if (mate[*vi] != graph_traits<undirected_graph>::null_vertex() &&
+            *vi < mate[*vi])
+          std::cout << "{" << *vi << "," << mate[*vi] << "}, ";
+      std::cout << std::endl;
+    }
+
+  //Now remove an edge from the random_mate matching.
+  vertex_iterator_t vi, vi_end;
+  for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
+    if (mate[*vi] != graph_traits<undirected_graph>::null_vertex())
+      break;
+  
+  mate[mate[*vi]] = graph_traits<undirected_graph>::null_vertex();
+  mate[*vi] = graph_traits<undirected_graph>::null_vertex();
+  
+  //...and run the matching verifier - it should tell us that the matching isn't
+  //a maximum matching.
+  bool modified_random_verification_result =
+    maximum_cardinality_matching_verifier<undirected_graph,mate_t,vertex_index_map_t>::verify_matching(g,mate,get(vertex_index,g));
+  
+  if (modified_random_verification_result)
+    {
+      std::cout << "TEST 2 FAILED!!!" << std::endl;
+    }
+
+  //find a greedy matching on the graph
+  mate_t greedy_mate(n);
+  greedy_matching<undirected_graph, mate_t>::find_matching(g,greedy_mate);
+
+  if (matching_size(g,mate) > matching_size(g,greedy_mate) &&
+      maximum_cardinality_matching_verifier<undirected_graph,mate_t,vertex_index_map_t>::verify_matching(g,greedy_mate,get(vertex_index,g)))
+        std::cout << "TEST 3 FAILED!!!" << std::endl;
+
+  return 0;
+}
+