deba@326
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@326
|
2 |
*
|
deba@326
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@326
|
4 |
*
|
deba@326
|
5 |
* Copyright (C) 2003-2008
|
deba@326
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@326
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@326
|
8 |
*
|
deba@326
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@326
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@326
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@326
|
12 |
*
|
deba@326
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@326
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@326
|
15 |
* purpose.
|
deba@326
|
16 |
*
|
deba@326
|
17 |
*/
|
deba@326
|
18 |
|
deba@326
|
19 |
#include <iostream>
|
deba@326
|
20 |
#include <vector>
|
deba@326
|
21 |
#include <queue>
|
deba@326
|
22 |
#include <lemon/math.h>
|
deba@326
|
23 |
#include <cstdlib>
|
deba@326
|
24 |
|
deba@326
|
25 |
#include "test_tools.h"
|
deba@326
|
26 |
#include <lemon/list_graph.h>
|
deba@326
|
27 |
#include <lemon/max_matching.h>
|
deba@326
|
28 |
|
deba@326
|
29 |
using namespace std;
|
deba@326
|
30 |
using namespace lemon;
|
deba@326
|
31 |
|
deba@326
|
32 |
int main() {
|
deba@326
|
33 |
|
deba@326
|
34 |
typedef ListGraph Graph;
|
deba@326
|
35 |
|
deba@326
|
36 |
GRAPH_TYPEDEFS(Graph);
|
deba@326
|
37 |
|
deba@326
|
38 |
Graph g;
|
deba@326
|
39 |
g.clear();
|
deba@326
|
40 |
|
deba@326
|
41 |
std::vector<Graph::Node> nodes;
|
deba@326
|
42 |
for (int i=0; i<13; ++i)
|
deba@326
|
43 |
nodes.push_back(g.addNode());
|
deba@326
|
44 |
|
deba@326
|
45 |
g.addEdge(nodes[0], nodes[0]);
|
deba@326
|
46 |
g.addEdge(nodes[6], nodes[10]);
|
deba@326
|
47 |
g.addEdge(nodes[5], nodes[10]);
|
deba@326
|
48 |
g.addEdge(nodes[4], nodes[10]);
|
deba@326
|
49 |
g.addEdge(nodes[3], nodes[11]);
|
deba@326
|
50 |
g.addEdge(nodes[1], nodes[6]);
|
deba@326
|
51 |
g.addEdge(nodes[4], nodes[7]);
|
deba@326
|
52 |
g.addEdge(nodes[1], nodes[8]);
|
deba@326
|
53 |
g.addEdge(nodes[0], nodes[8]);
|
deba@326
|
54 |
g.addEdge(nodes[3], nodes[12]);
|
deba@326
|
55 |
g.addEdge(nodes[6], nodes[9]);
|
deba@326
|
56 |
g.addEdge(nodes[9], nodes[11]);
|
deba@326
|
57 |
g.addEdge(nodes[2], nodes[10]);
|
deba@326
|
58 |
g.addEdge(nodes[10], nodes[8]);
|
deba@326
|
59 |
g.addEdge(nodes[5], nodes[8]);
|
deba@326
|
60 |
g.addEdge(nodes[6], nodes[3]);
|
deba@326
|
61 |
g.addEdge(nodes[0], nodes[5]);
|
deba@326
|
62 |
g.addEdge(nodes[6], nodes[12]);
|
deba@326
|
63 |
|
deba@326
|
64 |
MaxMatching<Graph> max_matching(g);
|
deba@326
|
65 |
max_matching.init();
|
deba@326
|
66 |
max_matching.startDense();
|
deba@326
|
67 |
|
deba@326
|
68 |
int s=0;
|
deba@326
|
69 |
Graph::NodeMap<Node> mate(g,INVALID);
|
deba@326
|
70 |
max_matching.mateMap(mate);
|
deba@326
|
71 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
72 |
if ( mate[v]!=INVALID ) ++s;
|
deba@326
|
73 |
}
|
deba@326
|
74 |
int size=int(s/2); //size will be used as the size of a maxmatching
|
deba@326
|
75 |
|
deba@326
|
76 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
77 |
max_matching.mate(v);
|
deba@326
|
78 |
}
|
deba@326
|
79 |
|
deba@326
|
80 |
check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
|
deba@326
|
81 |
|
deba@326
|
82 |
Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g);
|
deba@326
|
83 |
max_matching.decomposition(pos0);
|
deba@326
|
84 |
|
deba@326
|
85 |
max_matching.init();
|
deba@326
|
86 |
max_matching.startSparse();
|
deba@326
|
87 |
s=0;
|
deba@326
|
88 |
max_matching.mateMap(mate);
|
deba@326
|
89 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
90 |
if ( mate[v]!=INVALID ) ++s;
|
deba@326
|
91 |
}
|
deba@326
|
92 |
check ( int(s/2) == size, "The size does not equal!" );
|
deba@326
|
93 |
|
deba@326
|
94 |
Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g);
|
deba@326
|
95 |
max_matching.decomposition(pos1);
|
deba@326
|
96 |
|
deba@326
|
97 |
max_matching.run();
|
deba@326
|
98 |
s=0;
|
deba@326
|
99 |
max_matching.mateMap(mate);
|
deba@326
|
100 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
101 |
if ( mate[v]!=INVALID ) ++s;
|
deba@326
|
102 |
}
|
deba@326
|
103 |
check ( int(s/2) == size, "The size does not equal!" );
|
deba@326
|
104 |
|
deba@326
|
105 |
Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g);
|
deba@326
|
106 |
max_matching.decomposition(pos2);
|
deba@326
|
107 |
|
deba@326
|
108 |
max_matching.run();
|
deba@326
|
109 |
s=0;
|
deba@326
|
110 |
max_matching.mateMap(mate);
|
deba@326
|
111 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
112 |
if ( mate[v]!=INVALID ) ++s;
|
deba@326
|
113 |
}
|
deba@326
|
114 |
check ( int(s/2) == size, "The size does not equal!" );
|
deba@326
|
115 |
|
deba@326
|
116 |
Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g);
|
deba@326
|
117 |
max_matching.decomposition(pos);
|
deba@326
|
118 |
|
deba@326
|
119 |
bool ismatching=true;
|
deba@326
|
120 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
121 |
if ( mate[v]!=INVALID ) {
|
deba@326
|
122 |
Node u=mate[v];
|
deba@326
|
123 |
if (mate[u]!=v) ismatching=false;
|
deba@326
|
124 |
}
|
deba@326
|
125 |
}
|
deba@326
|
126 |
check ( ismatching, "It is not a matching!" );
|
deba@326
|
127 |
|
deba@326
|
128 |
bool coincide=true;
|
deba@326
|
129 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
130 |
if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
|
deba@326
|
131 |
coincide=false;
|
deba@326
|
132 |
}
|
deba@326
|
133 |
}
|
deba@326
|
134 |
check ( coincide, "The decompositions do not coincide! " );
|
deba@326
|
135 |
|
deba@326
|
136 |
bool noarc=true;
|
deba@326
|
137 |
for(EdgeIt e(g); e!=INVALID; ++e) {
|
deba@326
|
138 |
if ( (pos[g.v(e)]==max_matching.C &&
|
deba@326
|
139 |
pos[g.u(e)]==max_matching.D) ||
|
deba@326
|
140 |
(pos[g.v(e)]==max_matching.D &&
|
deba@326
|
141 |
pos[g.u(e)]==max_matching.C) )
|
deba@326
|
142 |
noarc=false;
|
deba@326
|
143 |
}
|
deba@326
|
144 |
check ( noarc, "There are arcs between D and C!" );
|
deba@326
|
145 |
|
deba@326
|
146 |
bool oddcomp=true;
|
deba@326
|
147 |
Graph::NodeMap<bool> todo(g,true);
|
deba@326
|
148 |
int num_comp=0;
|
deba@326
|
149 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
150 |
if ( pos[v]==max_matching.D && todo[v] ) {
|
deba@326
|
151 |
int comp_size=1;
|
deba@326
|
152 |
++num_comp;
|
deba@326
|
153 |
std::queue<Node> Q;
|
deba@326
|
154 |
Q.push(v);
|
deba@326
|
155 |
todo.set(v,false);
|
deba@326
|
156 |
while (!Q.empty()) {
|
deba@326
|
157 |
Node w=Q.front();
|
deba@326
|
158 |
Q.pop();
|
deba@326
|
159 |
for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
|
deba@326
|
160 |
Node u=g.runningNode(e);
|
deba@326
|
161 |
if ( pos[u]==max_matching.D && todo[u] ) {
|
deba@326
|
162 |
++comp_size;
|
deba@326
|
163 |
Q.push(u);
|
deba@326
|
164 |
todo.set(u,false);
|
deba@326
|
165 |
}
|
deba@326
|
166 |
}
|
deba@326
|
167 |
}
|
deba@326
|
168 |
if ( !(comp_size % 2) ) oddcomp=false;
|
deba@326
|
169 |
}
|
deba@326
|
170 |
}
|
deba@326
|
171 |
check ( oddcomp, "A component of g[D] is not odd." );
|
deba@326
|
172 |
|
deba@326
|
173 |
int barrier=0;
|
deba@326
|
174 |
for(NodeIt v(g); v!=INVALID; ++v) {
|
deba@326
|
175 |
if ( pos[v]==max_matching.A ) ++barrier;
|
deba@326
|
176 |
}
|
deba@326
|
177 |
int expected_size=int( countNodes(g)-num_comp+barrier)/2;
|
deba@326
|
178 |
check ( size==expected_size, "The size of the matching is wrong." );
|
deba@326
|
179 |
|
deba@326
|
180 |
return 0;
|
deba@326
|
181 |
}
|