Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
2 * test/max_matching_test.cc -
3 * Part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 * Permission to use, modify and distribute this software is granted
9 * provided that this copyright notice appears in all copies. For
10 * precise terms see the accompanying LICENSE file.
12 * This software is provided "AS IS" with no warranty of any kind,
13 * express or implied, and with no claim as to its suitability for any
24 #include "test_tools.h"
25 #include <lemon/invalid.h>
26 #include <lemon/list_graph.h>
27 #include <lemon/max_matching.h>
30 using namespace lemon;
34 typedef UndirListGraph Graph;
36 typedef Graph::Edge Edge;
37 typedef Graph::UndirEdgeIt UndirEdgeIt;
38 typedef Graph::IncEdgeIt IncEdgeIt;
39 typedef Graph::NodeIt NodeIt;
40 typedef Graph::Node Node;
45 std::vector<Graph::Node> nodes;
46 for (int i=0; i<13; ++i)
47 nodes.push_back(g.addNode());
49 g.addEdge(nodes[0], nodes[0]);
50 g.addEdge(nodes[6], nodes[10]);
51 g.addEdge(nodes[5], nodes[10]);
52 g.addEdge(nodes[4], nodes[10]);
53 g.addEdge(nodes[3], nodes[11]);
54 g.addEdge(nodes[1], nodes[6]);
55 g.addEdge(nodes[4], nodes[7]);
56 g.addEdge(nodes[1], nodes[8]);
57 g.addEdge(nodes[0], nodes[8]);
58 g.addEdge(nodes[3], nodes[12]);
59 g.addEdge(nodes[6], nodes[9]);
60 g.addEdge(nodes[9], nodes[11]);
61 g.addEdge(nodes[2], nodes[10]);
62 g.addEdge(nodes[10], nodes[8]);
63 g.addEdge(nodes[5], nodes[8]);
64 g.addEdge(nodes[6], nodes[3]);
65 g.addEdge(nodes[0], nodes[5]);
66 g.addEdge(nodes[6], nodes[12]);
68 MaxMatching<Graph> max_matching(g);
69 max_matching.runEdmonds(0);
72 Graph::NodeMap<Node> mate(g,INVALID);
73 max_matching.writeNMapNode(mate);
74 for(NodeIt v(g); v!=INVALID; ++v) {
75 if ( mate[v]!=INVALID ) ++s;
77 int size=(int)s/2; //size will be used as the size of a maxmatching
79 for(NodeIt v(g); v!=INVALID; ++v) {
83 check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
85 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
86 max_matching.writePos(pos0);
88 max_matching.resetMatching();
89 max_matching.runEdmonds(1);
91 max_matching.writeNMapNode(mate);
92 for(NodeIt v(g); v!=INVALID; ++v) {
93 if ( mate[v]!=INVALID ) ++s;
95 check ( (int)s/2 == size, "The size does not equal!" );
97 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
98 max_matching.writePos(pos1);
102 max_matching.writeNMapNode(mate);
103 for(NodeIt v(g); v!=INVALID; ++v) {
104 if ( mate[v]!=INVALID ) ++s;
106 check ( (int)s/2 == size, "The size does not equal!" );
108 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
109 max_matching.writePos(pos2);
111 max_matching.resetMatching();
114 max_matching.writeNMapNode(mate);
115 for(NodeIt v(g); v!=INVALID; ++v) {
116 if ( mate[v]!=INVALID ) ++s;
118 check ( (int)s/2 == size, "The size does not equal!" );
120 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
121 max_matching.writePos(pos);
123 bool ismatching=true;
124 for(NodeIt v(g); v!=INVALID; ++v) {
125 if ( mate[v]!=INVALID ) {
127 if (mate[u]!=v) ismatching=false;
130 check ( ismatching, "It is not a matching!" );
133 for(NodeIt v(g); v!=INVALID; ++v) {
134 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
138 check ( coincide, "The decompositions do not coincide! " );
141 for(UndirEdgeIt e(g); e!=INVALID; ++e) {
142 if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) ||
143 (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
146 check ( noedge, "There are edges between D and C!" );
149 Graph::NodeMap<bool> todo(g,true);
151 for(NodeIt v(g); v!=INVALID; ++v) {
152 if ( pos[v]==max_matching.D && todo[v] ) {
161 for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
162 Node u=g.runningNode(e);
163 if ( pos[u]==max_matching.D && todo[u] ) {
170 if ( !(comp_size % 2) ) oddcomp=false;
173 check ( oddcomp, "A component of g[D] is not odd." );
176 for(NodeIt v(g); v!=INVALID; ++v) {
177 if ( pos[v]==max_matching.A ) ++barrier;
179 int expected_size=(int)( countNodes(g)-num_comp+barrier)/2;
180 check ( size==expected_size, "The size of the matching is wrong." );