1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/stdcpp/tsrc/Boost_test/graph/src/matching_example.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,146 @@
1.4 +//=======================================================================
1.5 +// Copyright (c) 2005 Aaron Windsor
1.6 +//
1.7 +// Distributed under the Boost Software License, Version 1.0.
1.8 +// (See accompanying file LICENSE_1_0.txt or copy at
1.9 +// http://www.boost.org/LICENSE_1_0.txt)
1.10 +//
1.11 +//=======================================================================
1.12 +
1.13 +/*
1.14 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.15 +*/
1.16 +
1.17 +
1.18 +#include <boost/graph/adjacency_list.hpp>
1.19 +#include <boost/graph/max_cardinality_matching.hpp>
1.20 +
1.21 +#include <cassert>
1.22 +#include <string>
1.23 +#include <iostream>
1.24 +
1.25 +#ifdef __SYMBIAN32__
1.26 +#include "std_log_result.h"
1.27 +#define LOG_FILENAME_LINE __FILE__, __LINE__
1.28 +#endif
1.29 +
1.30 +#include <boost/test/minimal.hpp>
1.31 +
1.32 +using namespace boost;
1.33 +
1.34 +typedef adjacency_list<vecS, vecS, undirectedS> my_graph;
1.35 +
1.36 +int test_main(int argc, char* argv[])
1.37 +{
1.38 +
1.39 +
1.40 + // Create the following graph: (it'll look better when output
1.41 + // to the terminal in a fixed width font...)
1.42 +
1.43 + const int n_vertices = 18;
1.44 +
1.45 + std::vector<std::string> ascii_graph;
1.46 +
1.47 + ascii_graph.push_back(" 0 1---2 3 ");
1.48 + ascii_graph.push_back(" \\ / \\ / ");
1.49 + ascii_graph.push_back(" 4---5 6---7 ");
1.50 + ascii_graph.push_back(" | | | | ");
1.51 + ascii_graph.push_back(" 8---9 10---11 ");
1.52 + ascii_graph.push_back(" / \\ / \\ ");
1.53 + ascii_graph.push_back(" 12 13 14---15 16 17 ");
1.54 +
1.55 + // It has a perfect matching of size 8. There are two isolated
1.56 + // vertices that we'll use later...
1.57 +
1.58 + my_graph g(n_vertices);
1.59 +
1.60 + // our vertices are stored in a vector, so we can refer to vertices
1.61 + // by integers in the range 0..15
1.62 +
1.63 + add_edge(0,4,g);
1.64 + add_edge(1,5,g);
1.65 + add_edge(2,6,g);
1.66 + add_edge(3,7,g);
1.67 + add_edge(4,5,g);
1.68 + add_edge(6,7,g);
1.69 + add_edge(4,8,g);
1.70 + add_edge(5,9,g);
1.71 + add_edge(6,10,g);
1.72 + add_edge(7,11,g);
1.73 + add_edge(8,9,g);
1.74 + add_edge(10,11,g);
1.75 + add_edge(8,13,g);
1.76 + add_edge(9,14,g);
1.77 + add_edge(10,15,g);
1.78 + add_edge(11,16,g);
1.79 + add_edge(14,15,g);
1.80 +
1.81 + std::vector<graph_traits<my_graph>::vertex_descriptor> mate(n_vertices);
1.82 +
1.83 + // find the maximum cardinality matching. we'll use a checked version
1.84 + // of the algorithm, which takes a little longer than the unchecked
1.85 + // version, but has the advantage that it will return "false" if the
1.86 + // matching returned is not actually a maximum cardinality matching
1.87 + // in the graph.
1.88 +
1.89 +
1.90 + #ifndef __SYMBIAN32__
1.91 + bool success = checked_edmonds_maximum_cardinality_matching(g, &mate[0]);
1.92 + assert(success);
1.93 + #endif
1.94 +
1.95 + std::cout << "In the following graph:" << std::endl << std::endl;
1.96 +
1.97 + for(std::vector<std::string>::iterator itr = ascii_graph.begin(); itr != ascii_graph.end(); ++itr)
1.98 + std::cout << *itr << std::endl;
1.99 +
1.100 + std::cout << std::endl << "Found a matching of size " << matching_size(g, &mate[0]) << std::endl;
1.101 +
1.102 + std::cout << "The matching is:" << std::endl;
1.103 +
1.104 + graph_traits<my_graph>::vertex_iterator vi, vi_end;
1.105 + for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1.106 + if (mate[*vi] != graph_traits<my_graph>::null_vertex() && *vi < mate[*vi])
1.107 + std::cout << "{" << *vi << ", " << mate[*vi] << "}" << std::endl;
1.108 +
1.109 + std::cout << std::endl;
1.110 +
1.111 + //now we'll add two edges, and the perfect matching has size 9
1.112 +
1.113 + ascii_graph.pop_back();
1.114 + ascii_graph.push_back(" 12---13 14---15 16---17 ");
1.115 +
1.116 + add_edge(12,13,g);
1.117 + add_edge(16,17,g);
1.118 +
1.119 + #ifndef __SYMBIAN32__
1.120 + success = checked_edmonds_maximum_cardinality_matching(g, &mate[0]);
1.121 + assert(success);
1.122 + #endif
1.123 +
1.124 + std::cout << "In the following graph:" << std::endl << std::endl;
1.125 +
1.126 + for(std::vector<std::string>::iterator itr = ascii_graph.begin(); itr != ascii_graph.end(); ++itr)
1.127 + std::cout << *itr << std::endl;
1.128 +
1.129 + std::cout << std::endl << "Found a matching of size " << matching_size(g, &mate[0]) << std::endl;
1.130 +
1.131 + std::cout << "The matching is:" << std::endl;
1.132 +
1.133 + for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
1.134 + if (mate[*vi] != graph_traits<my_graph>::null_vertex() && *vi < mate[*vi])
1.135 + std::cout << "{" << *vi << ", " << mate[*vi] << "}" << std::endl;
1.136 +
1.137 +
1.138 + #ifdef __SYMBIAN32__
1.139 + std_log(LOG_FILENAME_LINE,"[End Test Case ]");
1.140 + testResultXml("matching_example");
1.141 + close_log_file();
1.142 + #endif
1.143 +
1.144 + return 0;
1.145 +}
1.146 +
1.147 +
1.148 +
1.149 +