--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/stdcpp/tsrc/Boost_test/graph/src/matching_test.cpp Tue Feb 02 02:01:42 2010 +0200
@@ -0,0 +1,380 @@
+//=======================================================================
+// 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)
+//
+//=======================================================================
+
+/*
+ * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
+*/
+
+#include <boost/graph/max_cardinality_matching.hpp>
+
+#include <iostream> // for std::cout
+#include <boost/vector_property_map.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/adjacency_matrix.hpp>
+#include <boost/graph/random.hpp>
+#include <ctime>
+#include <boost/random.hpp>
+#include <boost/test/minimal.hpp>
+#ifdef __SYMBIAN32__
+#include "std_log_result.h"
+#define LOG_FILENAME_LINE __FILE__, __LINE__
+#endif
+using namespace boost;
+
+typedef adjacency_list<vecS,
+ vecS,
+ undirectedS,
+ property<vertex_index_t, int> > undirected_graph;
+
+typedef adjacency_list<listS,
+ listS,
+ undirectedS,
+ property<vertex_index_t, int> > undirected_list_graph;
+
+typedef adjacency_matrix<undirectedS,
+ property<vertex_index_t,int> > undirected_adjacency_matrix_graph;
+
+
+template <typename Graph>
+struct vertex_index_installer
+{
+ static void install(Graph& g) {}
+};
+
+
+template <>
+struct vertex_index_installer<undirected_list_graph>
+{
+ static void install(undirected_list_graph& g)
+ {
+ typedef graph_traits<undirected_list_graph>::vertex_iterator vertex_iterator_t;
+ typedef graph_traits<undirected_list_graph>::vertices_size_type v_size_t;
+
+ vertex_iterator_t vi, vi_end;
+ v_size_t i = 0;
+ for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi, ++i)
+ put(vertex_index, g, *vi, i);
+ }
+};
+
+
+
+template <typename Graph>
+void complete_graph(Graph& g, int n)
+{
+ //creates the complete graph on n vertices
+ typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
+
+ g = Graph(n);
+ vertex_iterator_t vi, vi_end, wi;
+ tie(vi,vi_end) = vertices(g);
+ for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
+ {
+ wi = vi;
+ ++wi;
+ for(; wi != vi_end; ++wi)
+ add_edge(*vi,*wi,g);
+ }
+}
+
+
+
+template <typename Graph>
+void gabows_graph(Graph& g, int n)
+{
+ //creates a graph with 2n vertices, consisting of the complete graph
+ //on n vertices plus n vertices of degree one, each adjacent to one
+ //vertex in the complete graph. without any initial matching, this
+ //graph forces edmonds' algorithm into worst-case behavior.
+
+ typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
+
+ g = Graph(2* n);
+
+ vertex_iterator_t vi, vi_end, ui, ui_end, halfway;
+
+ tie(ui,ui_end) = vertices(g);
+
+ halfway = ui;
+ for(int i = 0; i < n; ++i)
+ ++halfway;
+
+
+ while(ui != halfway)
+ {
+ vi = ui;
+ ++vi;
+ while (vi != halfway)
+ {
+ add_edge(*ui,*vi,g);
+ ++vi;
+ }
+ ++ui;
+ }
+
+ tie(ui,ui_end) = vertices(g);
+
+ while(halfway != ui_end)
+ {
+ add_edge(*ui, *halfway, g);
+ ++ui;
+ ++halfway;
+ }
+
+}
+
+
+
+template <typename Graph>
+void matching_test(std::size_t num_v, const std::string& graph_name)
+{
+ typedef typename property_map<Graph,vertex_index_t>::type vertex_index_map_t;
+ typedef vector_property_map< typename graph_traits<Graph>::vertex_descriptor, vertex_index_map_t > mate_t;
+ typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
+ typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
+
+ const std::size_t double_num_v = num_v * 2;
+
+ bool all_tests_passed = true;
+
+ //form the complete graph on 2*n vertices; the maximum cardinality matching, greedy matching,
+ //and extra greedy matching should all be the same - a matching of size n.
+
+ Graph g(double_num_v);
+ complete_graph(g,double_num_v);
+
+ vertex_index_installer<Graph>::install(g);
+
+ mate_t edmonds_mate(double_num_v);
+ mate_t greedy_mate(double_num_v);
+ mate_t extra_greedy_mate(double_num_v);
+
+ //find a maximum cardinality matching using edmonds' blossom-shrinking algorithm, starting
+ //with an empty matching.
+ bool edmonds_result =
+ matching < Graph, mate_t, vertex_index_map_t,
+ edmonds_augmenting_path_finder, empty_matching, maximum_cardinality_matching_verifier>
+ (g,edmonds_mate, get(vertex_index,g));
+
+ BOOST_CHECK (edmonds_result);
+ if (!edmonds_result)
+ {
+ std::cout << "Verifier reporting a problem finding a perfect matching on" << std::endl
+ << "the complete graph using " << graph_name << std::endl;
+ all_tests_passed = false;
+ }
+
+ //find a greedy matching
+ bool greedy_result =
+ matching<Graph, mate_t, vertex_index_map_t,
+ no_augmenting_path_finder, greedy_matching, maximum_cardinality_matching_verifier>
+ (g,greedy_mate, get(vertex_index,g));
+
+ BOOST_CHECK (greedy_result);
+ if (!greedy_result)
+ {
+ std::cout << "Verifier reporting a problem finding a greedy matching on" << std::endl
+ << "the complete graph using " << graph_name << std::endl;
+ all_tests_passed = false;
+ }
+
+ //find an extra greedy matching
+ bool extra_greedy_result =
+ matching<Graph, mate_t, vertex_index_map_t,
+ no_augmenting_path_finder, extra_greedy_matching, maximum_cardinality_matching_verifier>
+ (g,extra_greedy_mate,get(vertex_index,g));
+
+ BOOST_CHECK (extra_greedy_result);
+ if (!extra_greedy_result)
+ {
+ std::cout << "Verifier reporting a problem finding an extra greedy matching on" << std::endl
+ << "the complete graph using " << graph_name << std::endl;
+ all_tests_passed = false;
+ }
+
+ //as a sanity check, make sure that each of the matchings returned is a valid matching and has
+ //1000 edges.
+
+ bool edmonds_sanity_check =
+ is_a_matching(g,edmonds_mate) && matching_size(g,edmonds_mate) == num_v;
+
+ BOOST_CHECK (edmonds_sanity_check);
+ if (edmonds_result && !edmonds_sanity_check)
+ {
+ std::cout << "Verifier okayed edmonds' algorithm on the complete graph, but" << std::endl
+ << "the matching returned either wasn't a valid matching or wasn't" << std::endl
+ << "actually a maximum cardinality matching." << std::endl;
+ all_tests_passed = false;
+ }
+
+ bool greedy_sanity_check =
+ is_a_matching(g,greedy_mate) && matching_size(g,greedy_mate) == num_v;
+
+ BOOST_CHECK (greedy_sanity_check);
+ if (greedy_result && !greedy_sanity_check)
+ {
+ std::cout << "Verifier okayed greedy algorithm on the complete graph, but" << std::endl
+ << "the matching returned either wasn't a valid matching or wasn't" << std::endl
+ << "actually a maximum cardinality matching." << std::endl;
+ all_tests_passed = false;
+ }
+
+ bool extra_greedy_sanity_check =
+ is_a_matching(g,extra_greedy_mate) && matching_size(g,extra_greedy_mate) == num_v;
+
+ BOOST_CHECK (extra_greedy_sanity_check);
+ if (extra_greedy_result && !extra_greedy_sanity_check)
+ {
+ std::cout << "Verifier okayed extra greedy algorithm on the complete graph, but" << std::endl
+ << "the matching returned either wasn't a valid matching or wasn't" << std::endl
+ << "actually a maximum cardinality matching." << std::endl;
+ all_tests_passed = false;
+ }
+
+ //Now remove an edge from the edmonds_mate matching.
+ vertex_iterator_t vi,vi_end;
+ for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
+ if (edmonds_mate[*vi] != graph_traits<Graph>::null_vertex())
+ break;
+
+ edmonds_mate[edmonds_mate[*vi]] = graph_traits<Graph>::null_vertex();
+ edmonds_mate[*vi] = graph_traits<Graph>::null_vertex();
+
+ //...and run the matching verifier - it should tell us that the matching isn't
+ //a maximum matching.
+ bool modified_edmonds_verification_result =
+ maximum_cardinality_matching_verifier<Graph,mate_t,vertex_index_map_t>::verify_matching(g,edmonds_mate,get(vertex_index,g));
+
+ BOOST_CHECK (!modified_edmonds_verification_result);
+ if (modified_edmonds_verification_result)
+ {
+ std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
+ all_tests_passed = false;
+ }
+
+ Graph h(double_num_v);
+ gabows_graph(h,num_v);
+
+ vertex_index_installer<Graph>::install(h);
+
+ //gabow's graph always has a perfect matching. it's also a good example of why
+ //one should initialize with the extra_greedy_matching in most cases.
+
+ mate_t gabow_mate(double_num_v);
+
+ bool gabows_graph_result = checked_edmonds_maximum_cardinality_matching(h,gabow_mate);
+
+ BOOST_CHECK (gabows_graph_result);
+ if (!gabows_graph_result)
+ {
+ std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
+ << " Verifier reporting a maximum cardinality matching not found." << std::endl;
+ all_tests_passed = false;
+ }
+
+ BOOST_CHECK (matching_size(h,gabow_mate) == num_v);
+ if (gabows_graph_result && matching_size(h,gabow_mate) != num_v)
+ {
+ std::cout << "Problem on Gabow's Graph with " << graph_name << ":" << std::endl
+ << " Verifier reported a maximum cardinality matching found," << std::endl
+ << " but matching size is " << matching_size(h,gabow_mate)
+ << " when it should be " << num_v << std::endl;
+ all_tests_passed = false;
+ }
+
+ Graph j(double_num_v);
+ vertex_index_installer<Graph>::install(j);
+
+ typedef boost::mt19937 base_generator_type;
+ base_generator_type generator(static_cast<unsigned int>(std::time(0)));
+ boost::uniform_int<> distribution(0, double_num_v-1);
+ boost::variate_generator<base_generator_type&, boost::uniform_int<> > rand_num(generator, distribution);
+
+ std::size_t num_edges = 0;
+ bool success;
+
+ while (num_edges < 4*double_num_v)
+ {
+ vertex_descriptor_t u = random_vertex(j,rand_num);
+ vertex_descriptor_t v = random_vertex(j,rand_num);
+ if (u != v)
+ {
+ tie(tuples::ignore, success) = add_edge(u, v, j);
+ if (success)
+ num_edges++;
+ }
+ }
+
+ mate_t random_mate(double_num_v);
+ bool random_graph_result = checked_edmonds_maximum_cardinality_matching(j,random_mate);
+
+ BOOST_CHECK(random_graph_result);
+ if (!random_graph_result)
+ {
+ std::cout << "Matching in random graph not maximum for " << graph_name << std::endl;
+ all_tests_passed = false;
+ }
+
+ //Now remove an edge from the random_mate matching.
+ for(tie(vi,vi_end) = vertices(j); vi != vi_end; ++vi)
+ if (random_mate[*vi] != graph_traits<Graph>::null_vertex())
+ break;
+
+ random_mate[random_mate[*vi]] = graph_traits<Graph>::null_vertex();
+ random_mate[*vi] = graph_traits<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<Graph,mate_t,vertex_index_map_t>::verify_matching(j,random_mate,get(vertex_index,j));
+
+ BOOST_CHECK(!modified_random_verification_result);
+ if (modified_random_verification_result)
+ {
+ std::cout << "Verifier was fooled into thinking that a non-maximum matching was maximum" << std::endl;
+ all_tests_passed = false;
+ }
+
+ BOOST_CHECK(all_tests_passed);
+ if (all_tests_passed)
+ {
+ std::cout << graph_name << " passed all tests for n = " << num_v << '.' << std::endl;
+ }
+
+}
+
+
+
+
+int test_main(int argc, char* argv[])
+{
+
+ matching_test<undirected_graph>(10, "adjacency_list (using vectors)");
+ matching_test<undirected_list_graph>(10, "adjacency_list (using lists)");
+ matching_test<undirected_adjacency_matrix_graph>(10, "adjacency_matrix");
+
+ matching_test<undirected_graph>(50, "adjacency_list (using vectors)");
+ matching_test<undirected_list_graph>(50, "adjacency_list (using lists)");
+ matching_test<undirected_adjacency_matrix_graph>(50, "adjacency_matrix");
+
+ matching_test<undirected_graph>(51, "adjacency_list (using vectors)");
+ matching_test<undirected_list_graph>(51, "adjacency_list (using lists)");
+ matching_test<undirected_adjacency_matrix_graph>(51, "adjacency_matrix");
+
+#ifdef __SYMBIAN32__
+std_log(LOG_FILENAME_LINE,"[End Test Case ]");
+
+ testResultXml("matching_test");
+ close_log_file();
+#endif
+ return 0;
+}
+
+