//=======================================================================

 // 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;

 }