]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright (c) 2005 Aaron Windsor | |
3 | // | |
f67539c2 | 4 | // Distributed under the Boost Software License, Version 1.0. |
7c673cae FG |
5 | // (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | // | |
8 | //======================================================================= | |
9 | #include <string> | |
10 | #include <iostream> | |
11 | #include <boost/graph/adjacency_list.hpp> | |
12 | #include <cassert> | |
13 | ||
14 | #include <boost/graph/max_cardinality_matching.hpp> | |
15 | ||
7c673cae FG |
16 | using namespace boost; |
17 | ||
f67539c2 | 18 | typedef adjacency_list< vecS, vecS, undirectedS > my_graph; |
7c673cae FG |
19 | |
20 | int main() | |
21 | { | |
22 | ||
f67539c2 TL |
23 | // Create the following graph: (it'll look better when output |
24 | // to the terminal in a fixed width font...) | |
25 | ||
26 | const int n_vertices = 18; | |
27 | ||
28 | std::vector< std::string > ascii_graph; | |
29 | ||
30 | ascii_graph.push_back(" 0 1---2 3 "); | |
31 | ascii_graph.push_back(" \\ / \\ / "); | |
32 | ascii_graph.push_back(" 4---5 6---7 "); | |
33 | ascii_graph.push_back(" | | | | "); | |
34 | ascii_graph.push_back(" 8---9 10---11 "); | |
35 | ascii_graph.push_back(" / \\ / \\ "); | |
36 | ascii_graph.push_back(" 12 13 14---15 16 17 "); | |
7c673cae | 37 | |
f67539c2 TL |
38 | // It has a perfect matching of size 8. There are two isolated |
39 | // vertices that we'll use later... | |
7c673cae | 40 | |
f67539c2 | 41 | my_graph g(n_vertices); |
7c673cae | 42 | |
f67539c2 TL |
43 | // our vertices are stored in a vector, so we can refer to vertices |
44 | // by integers in the range 0..15 | |
7c673cae | 45 | |
f67539c2 TL |
46 | add_edge(1, 2, g); |
47 | add_edge(0, 4, g); | |
48 | add_edge(1, 5, g); | |
49 | add_edge(2, 6, g); | |
50 | add_edge(3, 7, g); | |
51 | add_edge(4, 5, g); | |
52 | add_edge(6, 7, g); | |
53 | add_edge(4, 8, g); | |
54 | add_edge(5, 9, g); | |
55 | add_edge(6, 10, g); | |
56 | add_edge(7, 11, g); | |
57 | add_edge(8, 9, g); | |
58 | add_edge(10, 11, g); | |
59 | add_edge(8, 13, g); | |
60 | add_edge(9, 14, g); | |
61 | add_edge(10, 15, g); | |
62 | add_edge(11, 16, g); | |
63 | add_edge(14, 15, g); | |
7c673cae | 64 | |
f67539c2 | 65 | std::vector< graph_traits< my_graph >::vertex_descriptor > mate(n_vertices); |
7c673cae | 66 | |
f67539c2 TL |
67 | // find the maximum cardinality matching. we'll use a checked version |
68 | // of the algorithm, which takes a little longer than the unchecked | |
69 | // version, but has the advantage that it will return "false" if the | |
70 | // matching returned is not actually a maximum cardinality matching | |
71 | // in the graph. | |
7c673cae | 72 | |
f67539c2 TL |
73 | bool success = checked_edmonds_maximum_cardinality_matching(g, &mate[0]); |
74 | assert(success); | |
7c673cae | 75 | |
f67539c2 | 76 | std::cout << "In the following graph:" << std::endl << std::endl; |
7c673cae | 77 | |
f67539c2 TL |
78 | for (std::vector< std::string >::iterator itr = ascii_graph.begin(); |
79 | itr != ascii_graph.end(); ++itr) | |
80 | std::cout << *itr << std::endl; | |
7c673cae | 81 | |
f67539c2 TL |
82 | std::cout << std::endl |
83 | << "Found a matching of size " << matching_size(g, &mate[0]) | |
84 | << std::endl; | |
7c673cae | 85 | |
f67539c2 | 86 | std::cout << "The matching is:" << std::endl; |
7c673cae | 87 | |
f67539c2 TL |
88 | graph_traits< my_graph >::vertex_iterator vi, vi_end; |
89 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) | |
90 | if (mate[*vi] != graph_traits< my_graph >::null_vertex() | |
91 | && *vi < mate[*vi]) | |
92 | std::cout << "{" << *vi << ", " << mate[*vi] << "}" << std::endl; | |
7c673cae | 93 | |
f67539c2 | 94 | std::cout << std::endl; |
7c673cae | 95 | |
f67539c2 | 96 | // now we'll add two edges, and the perfect matching has size 9 |
7c673cae | 97 | |
f67539c2 TL |
98 | ascii_graph.pop_back(); |
99 | ascii_graph.push_back(" 12---13 14---15 16---17 "); | |
7c673cae | 100 | |
f67539c2 TL |
101 | add_edge(12, 13, g); |
102 | add_edge(16, 17, g); | |
7c673cae | 103 | |
f67539c2 TL |
104 | success = checked_edmonds_maximum_cardinality_matching(g, &mate[0]); |
105 | assert(success); | |
7c673cae | 106 | |
f67539c2 | 107 | std::cout << "In the following graph:" << std::endl << std::endl; |
7c673cae | 108 | |
f67539c2 TL |
109 | for (std::vector< std::string >::iterator itr = ascii_graph.begin(); |
110 | itr != ascii_graph.end(); ++itr) | |
111 | std::cout << *itr << std::endl; | |
7c673cae | 112 | |
f67539c2 TL |
113 | std::cout << std::endl |
114 | << "Found a matching of size " << matching_size(g, &mate[0]) | |
115 | << std::endl; | |
7c673cae | 116 | |
f67539c2 | 117 | std::cout << "The matching is:" << std::endl; |
7c673cae | 118 | |
f67539c2 TL |
119 | for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) |
120 | if (mate[*vi] != graph_traits< my_graph >::null_vertex() | |
121 | && *vi < mate[*vi]) | |
122 | std::cout << "{" << *vi << ", " << mate[*vi] << "}" << std::endl; | |
7c673cae | 123 | |
f67539c2 | 124 | return 0; |
7c673cae | 125 | } |