The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
25 #include "test_tools.h"
26 #include <lemon/invalid.h>
27 #include <lemon/list_graph.h>
28 #include <lemon/max_matching.h>
31 using namespace lemon;
35 typedef ListUGraph Graph;
37 typedef Graph::Edge Edge;
38 typedef Graph::UEdgeIt UEdgeIt;
39 typedef Graph::IncEdgeIt IncEdgeIt;
40 typedef Graph::NodeIt NodeIt;
41 typedef Graph::Node Node;
46 std::vector<Graph::Node> nodes;
47 for (int i=0; i<13; ++i)
48 nodes.push_back(g.addNode());
50 g.addEdge(nodes[0], nodes[0]);
51 g.addEdge(nodes[6], nodes[10]);
52 g.addEdge(nodes[5], nodes[10]);
53 g.addEdge(nodes[4], nodes[10]);
54 g.addEdge(nodes[3], nodes[11]);
55 g.addEdge(nodes[1], nodes[6]);
56 g.addEdge(nodes[4], nodes[7]);
57 g.addEdge(nodes[1], nodes[8]);
58 g.addEdge(nodes[0], nodes[8]);
59 g.addEdge(nodes[3], nodes[12]);
60 g.addEdge(nodes[6], nodes[9]);
61 g.addEdge(nodes[9], nodes[11]);
62 g.addEdge(nodes[2], nodes[10]);
63 g.addEdge(nodes[10], nodes[8]);
64 g.addEdge(nodes[5], nodes[8]);
65 g.addEdge(nodes[6], nodes[3]);
66 g.addEdge(nodes[0], nodes[5]);
67 g.addEdge(nodes[6], nodes[12]);
69 MaxMatching<Graph> max_matching(g);
70 max_matching.runEdmonds(0);
73 Graph::NodeMap<Node> mate(g,INVALID);
74 max_matching.writeNMapNode(mate);
75 for(NodeIt v(g); v!=INVALID; ++v) {
76 if ( mate[v]!=INVALID ) ++s;
78 int size=(int)s/2; //size will be used as the size of a maxmatching
80 for(NodeIt v(g); v!=INVALID; ++v) {
84 check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
86 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
87 max_matching.writePos(pos0);
89 max_matching.resetMatching();
90 max_matching.runEdmonds(1);
92 max_matching.writeNMapNode(mate);
93 for(NodeIt v(g); v!=INVALID; ++v) {
94 if ( mate[v]!=INVALID ) ++s;
96 check ( (int)s/2 == size, "The size does not equal!" );
98 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
99 max_matching.writePos(pos1);
103 max_matching.writeNMapNode(mate);
104 for(NodeIt v(g); v!=INVALID; ++v) {
105 if ( mate[v]!=INVALID ) ++s;
107 check ( (int)s/2 == size, "The size does not equal!" );
109 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
110 max_matching.writePos(pos2);
112 max_matching.resetMatching();
115 max_matching.writeNMapNode(mate);
116 for(NodeIt v(g); v!=INVALID; ++v) {
117 if ( mate[v]!=INVALID ) ++s;
119 check ( (int)s/2 == size, "The size does not equal!" );
121 Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
122 max_matching.writePos(pos);
124 bool ismatching=true;
125 for(NodeIt v(g); v!=INVALID; ++v) {
126 if ( mate[v]!=INVALID ) {
128 if (mate[u]!=v) ismatching=false;
131 check ( ismatching, "It is not a matching!" );
134 for(NodeIt v(g); v!=INVALID; ++v) {
135 if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
139 check ( coincide, "The decompositions do not coincide! " );
142 for(UEdgeIt e(g); e!=INVALID; ++e) {
143 if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) ||
144 (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
147 check ( noedge, "There are edges between D and C!" );
150 Graph::NodeMap<bool> todo(g,true);
152 for(NodeIt v(g); v!=INVALID; ++v) {
153 if ( pos[v]==max_matching.D && todo[v] ) {
162 for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
163 Node u=g.runningNode(e);
164 if ( pos[u]==max_matching.D && todo[u] ) {
171 if ( !(comp_size % 2) ) oddcomp=false;
174 check ( oddcomp, "A component of g[D] is not odd." );
177 for(NodeIt v(g); v!=INVALID; ++v) {
178 if ( pos[v]==max_matching.A ) ++barrier;
180 int expected_size=(int)( countNodes(g)-num_comp+barrier)/2;
181 check ( size==expected_size, "The size of the matching is wrong." );