COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/max_matching.cc @ 986:e997802b855c

Last change on this file since 986:e997802b855c was 986:e997802b855c, checked in by Alpar Juttner, 15 years ago

Naming changes:

  • head -> target
  • tail -> source
File size: 7.7 KB
Line 
1///Generates a random graph, and tests max_matching.h on it.
2#include <iostream>
3#include <queue>
4#include <math.h>
5
6#include <list_graph.h>
7#include <dimacs.h>
8#include <graph_gen.h>
9#include <max_matching.h>
10#include <time_measure.h>
11#include <graph_wrapper.h>
12
13using namespace lemon;
14
15int main(int, char **) {
16 
17  typedef UndirGraph<ListGraph> UGW;
18  typedef UGW::Edge Edge;
19  typedef UGW::EdgeIt EdgeIt;
20  typedef UGW::OutEdgeIt OutEdgeIt;
21  typedef UGW::NodeIt NodeIt;
22  typedef UGW::Node Node;
23   
24  UGW G;
25
26  //  random_init(); //If you want to use a random graph with a random
27  //  number of edges and nodes.
28
29  int i;
30  int j;
31  std::cout<<"Number of nodes: ";
32  std::cin >> i;
33  std::cout<<"Number of edges: ";
34  std::cin >> j;
35
36  //  readDimacs(std::cin, G);
37  randomGraph(G, i, j ); 
38
39  Timer ts;
40  bool noerror=true;
41 
42  std::cout <<
43    "\n  Testing max_matching.h on a random graph with " <<
44    G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n"
45            << std::endl;
46  MaxMatching<UGW> max_matching(G);
47
48 
49  std::cout <<
50    "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... "
51            <<std::endl;
52  ts.reset(); 
53  max_matching.runEdmonds(0);
54  std::cout<<"Elapsed time: "<<ts<<std::endl;
55  int s=0;
56  UGW::NodeMap<Node> mate(G,INVALID);
57  max_matching.writeNMapNode(mate);
58  NodeIt v;
59  for(G.first(v); G.valid(v); G.next(v) ) {
60    if ( G.valid(mate[v]) ) {
61      ++s;
62    }
63  }
64  int size=(int)s/2;  //size will be used as the size of a maxmatching
65  std::cout << size << " is the size of the matching found by runEdmonds(0),"<<std::endl;
66  if ( size == max_matching.size() ) {
67    std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl;
68  } else { 
69    std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl;
70    noerror=false;
71  }
72
73
74  std::cout<<"Writing the position by calling writePos...";
75  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos0(G);
76  max_matching.writePos(pos0);
77  std::cout << "OK" << std::endl;
78
79
80  std::cout << "Resetting the matching and the position by calling"<< std::endl;
81  std::cout<<"resetPos() and resetMatching()...";
82  max_matching.resetPos();
83  max_matching.resetMatching();
84  std::cout <<"OK" << std::endl;
85
86
87  std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl;
88  ts.reset(); 
89  max_matching.runEdmonds(1);
90  std::cout<<"Elapsed time: "<<ts<<std::endl;
91  s=0;
92  max_matching.writeNMapNode(mate);
93  for(G.first(v); G.valid(v); G.next(v) ) {
94    if ( G.valid(mate[v]) ) {
95      ++s;
96    }
97  }
98  std::cout << (int)s/2 <<
99    " is the size of the matching found by runEdmonds(1),"<<std::endl;
100  if ( (int)s/2 == size ) {
101    std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;
102  } else { 
103    std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
104    noerror=false;
105  }
106  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G);
107  max_matching.writePos(pos1);
108
109
110  std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl;
111  max_matching.resetPos();
112  ts.reset(); 
113  max_matching.run();
114  std::cout<<"Elapsed time: "<<ts<<std::endl;
115  s=0;
116  max_matching.writeNMapNode(mate);
117  for(G.first(v); G.valid(v); G.next(v) ) {
118    if ( G.valid(mate[v]) ) {
119      ++s;
120    }
121  }
122  if ( (int)s/2 == size ) {
123    std::cout<< "Found a matching of proper size."<< std::endl;
124  } else { 
125    std::cout<< "Found a matching of inproper size!"<< std::endl;
126    noerror=false;
127  }
128  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G);
129  max_matching.writePos(pos2);
130
131
132  std::cout << "\nCalling resetPos() and resetMatching()...";
133  max_matching.resetPos();
134  max_matching.resetMatching();
135  std::cout<<"OK"<<std::endl;
136  std::cout <<"Calling greedyMatching() and then runEdmonds(1)... " <<std::endl;
137  ts.reset(); 
138  max_matching.run();
139  std::cout<<"Elapsed time: "<<ts<<std::endl;
140  s=0;
141  max_matching.writeNMapNode(mate);
142  for(G.first(v); G.valid(v); G.next(v) ) {
143    if ( G.valid(mate[v]) ) {
144      ++s;
145    }
146  }
147  std::cout << (int)s/2 << " is the size of the matching found by run(),"<<std::endl;
148  if ( (int)s/2 == size ) {
149    std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;
150  } else { 
151    std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
152    noerror=false;
153  }
154  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G);
155  max_matching.writePos(pos);
156   
157 
158  std::cout<<"\nChecking if the output is a matching...";
159  bool ismatching=true;
160  for(G.first(v); G.valid(v); G.next(v) )
161    if ( G.valid(mate[v]) ) {
162      Node u=mate[v];
163      if (mate[u]!=v) ismatching=false;
164    }
165  if ( ismatching ) std::cout<<"OK"<<std::endl;
166  else std::cout<< "It is not a matching!"<< std::endl;
167  noerror = noerror && ismatching;
168 
169
170  std::cout<<"\nChecking the dual..."<<std::endl;
171   
172  std::cout<<"Checking if the four position outputs coincide...";
173  bool coincide=true;
174  int err_node=0;
175  for(G.first(v); G.valid(v); G.next(v) ) {
176    if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
177      ++err_node;
178      coincide=false;
179    }
180  }
181  if ( coincide ) std::cout << "OK" <<std::endl;
182  else {
183    std::cout << "They do not coincide! Number of erroneous nodes: "
184              << err_node << std::endl;
185  }     
186  noerror=noerror && coincide;
187
188
189  std::cout<<"Checking if there is no edge between D and C...";
190  bool noedge=true;
191  EdgeIt e;
192  for(G.first(e); G.valid(e); G.next(e) ) {
193    if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) ||
194         (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )
195      noedge=false;
196  }
197  if ( noedge ) std::cout<<"OK"<<std::endl;
198  else std::cout<< "There are edges between D and C!"<< std::endl;
199  noerror = noerror && noedge;
200
201
202  std::cout<<"Checking if all the components of G[D] are odd...";
203  bool oddcomp=true;
204  UGW::NodeMap<bool> todo(G,true);
205  int num_comp=0;
206  for(G.first(v); G.valid(v); G.next(v) ) {
207    if ( pos[v]==max_matching.D && todo[v] ) {
208      int comp_size=1;
209      ++num_comp;
210      std::queue<Node> Q;
211      Q.push(v);
212      todo.set(v,false);
213      while (!Q.empty()) {
214        Node w=Q.front();       
215        Q.pop();
216        OutEdgeIt e;
217        for(G.first(e,w); G.valid(e); G.next(e)) {
218          Node u=G.bNode(e);
219          if ( pos[u]==max_matching.D && todo[u] ) {
220            ++comp_size;
221            Q.push(u);
222            todo.set(u,false);
223          }
224        }
225      }
226      if ( !(comp_size % 2) ) oddcomp=false; 
227    }
228  }
229  std::cout << "\n  found     " << num_comp << "     component(s) of G[D],";
230  if ( oddcomp ) std::cout<<" each is odd."<<std::endl;
231  else std::cout<< " but not all are odd!"<< std::endl;
232  noerror = noerror && oddcomp;
233
234
235  int barrier=0;
236  for(G.first(v); G.valid(v); G.next(v) )
237    if ( pos[v]==max_matching.A ) ++barrier;
238  std::cout << barrier << " is the number of nodes in A (i.e. the size of the barrier), so" << std::endl;
239  std::cout << num_comp - barrier << " is the deficiency of the graph, and hence" << std::endl;
240  int expected_size=(int)(G.nodeNum()-num_comp+barrier)/2;
241  std::cout << expected_size << " should be the size of the maximum matching," << std::endl;
242  if ( size==expected_size )
243    std::cout<<"which equals to the number of vertices missed by the found matching!"<<std::endl;
244  else {
245    std::cout<<"which does not equal to the number of vertices missed by the matchings found!"
246             <<std::endl;
247    noerror=false;
248  }
249
250
251  if ( num_comp == 1 && barrier == 0 )
252    std::cout<<"\nThis graph is factor-critical."<<std::endl;
253  if ( num_comp == 0 && barrier == 0 )
254    std::cout<<"\nThis graph has a perfect matching."<<std::endl;
255
256
257  if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl;
258  else std::cout<<"\nSome errors found!\n"<<std::endl;
259
260  return 0;
261}
262
263
264
265
266
267
268
269
270
Note: See TracBrowser for help on using the repository browser.