COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/max_matching_test.cc @ 1078:ce8466be7683

Last change on this file since 1078:ce8466be7683 was 1078:ce8466be7683, checked in by jacint, 20 years ago

Edmonds max_matching.h tester

File size: 4.8 KB
Line 
1/* -*- C++ -*-
2 * src/test/max_matching_test.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#include <iostream>
18#include <queue>
19#include <math.h>
20#include <cstdlib>
21
22#include "test_tools.h"
23#include <lemon/invalid.h>
24#include <lemon/list_graph.h>
25#include <graph_gen.h>
26#include <max_matching.h>
27
28using namespace std;
29using namespace lemon;
30
31int main() {
32
33  typedef UndirListGraph Graph;
34
35  typedef Graph::Edge Edge;
36  typedef Graph::UndirEdgeIt UndirEdgeIt;
37  typedef Graph::IncEdgeIt IncEdgeIt;
38  typedef Graph::NodeIt NodeIt;
39  typedef Graph::Node Node;
40   
41  Graph G;
42
43  random_init();
44  randomGraph(G, random(5000), random(20000) ); 
45
46  MaxMatching<Graph> max_matching(G);
47  max_matching.runEdmonds(0);
48 
49  int s=0;
50  Graph::NodeMap<Node> mate(G,INVALID);
51  max_matching.writeNMapNode(mate);
52  for(NodeIt v(G); v!=INVALID; ++v) {
53    if ( mate[v]!=INVALID ) ++s;
54  }
55  int size=(int)s/2;  //size will be used as the size of a maxmatching
56 
57  check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
58
59  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(G);
60  max_matching.writePos(pos0);
61 
62  max_matching.resetPos();
63  max_matching.resetMatching();
64  max_matching.runEdmonds(1);
65  s=0;
66  max_matching.writeNMapNode(mate);
67  for(NodeIt v(G); v!=INVALID; ++v) {
68    if ( mate[v]!=INVALID ) ++s;
69  }
70  check ( (int)s/2 == size, "The size does not equal!" );
71
72  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(G);
73  max_matching.writePos(pos1);
74
75  max_matching.resetPos();
76  max_matching.run();
77  s=0;
78  max_matching.writeNMapNode(mate);
79  for(NodeIt v(G); v!=INVALID; ++v) {
80    if ( mate[v]!=INVALID ) ++s;
81  }
82  check ( (int)s/2 == size, "The size does not equal!" );
83 
84  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(G);
85  max_matching.writePos(pos2);
86
87  max_matching.resetPos();
88  max_matching.resetMatching();
89  max_matching.run();
90  s=0;
91  max_matching.writeNMapNode(mate);
92  for(NodeIt v(G); v!=INVALID; ++v) {
93    if ( mate[v]!=INVALID ) ++s;
94  }
95  check ( (int)s/2 == size, "The size does not equal!" );
96 
97  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(G);
98  max_matching.writePos(pos);
99   
100  bool ismatching=true;
101  for(NodeIt v(G); v!=INVALID; ++v) {
102    if ( mate[v]!=INVALID ) {
103      Node u=mate[v];
104      if (mate[u]!=v) ismatching=false;
105    }
106  } 
107  check ( ismatching, "It is not a matching!" );
108
109  bool coincide=true;
110  for(NodeIt v(G); v!=INVALID; ++v) {
111   if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
112     coincide=false;
113    }
114  }
115  check ( coincide, "The decompositions do not coincide! " );
116
117  bool noedge=true;
118  for(UndirEdgeIt e(G); e!=INVALID; ++e) {
119   if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) ||
120         (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )
121      noedge=false;
122  }
123  check ( noedge, "There are edges between D and C!" );
124 
125  bool oddcomp=true;
126  Graph::NodeMap<bool> todo(G,true);
127  int num_comp=0;
128  for(NodeIt v(G); v!=INVALID; ++v) {
129   if ( pos[v]==max_matching.D && todo[v] ) {
130      int comp_size=1;
131      ++num_comp;
132      std::queue<Node> Q;
133      Q.push(v);
134      todo.set(v,false);
135      while (!Q.empty()) {
136        Node w=Q.front();       
137        Q.pop();
138        for(IncEdgeIt e(G,w); e!=INVALID; ++e) {
139          Node u=G.target(e);
140          if ( pos[u]==max_matching.D && todo[u] ) {
141            ++comp_size;
142            Q.push(u);
143            todo.set(u,false);
144          }
145        }
146      }
147      if ( !(comp_size % 2) ) oddcomp=false; 
148    }
149  }
150  check ( oddcomp, "A component of G[D] is not odd." );
151
152  int barrier=0;
153  for(NodeIt v(G); v!=INVALID; ++v) {
154    if ( pos[v]==max_matching.A ) ++barrier;
155  }
156  int expected_size=(int)( countNodes(G)-num_comp+barrier)/2;
157  check ( size==expected_size, "The size of the matching is wrong." );
158 
159  return 0;
160}
161
162
163void random_init()
164{
165  unsigned int seed = getpid();
166  seed |= seed << 15;
167  seed ^= time(0);
168 
169  srand(seed);
170}
171
172
173int random(int m)
174{
175  return int( double(m) * rand() / (RAND_MAX + 1.0) );
176}
177
178
179/// Generates a random graph with n nodes and m edges.
180/// Before generating the random graph, \c g.clear() is called.
181template<typename Graph>
182void randomGraph(Graph& g, int n, int m) {
183  g.clear();
184  std::vector<typename Graph::Node> nodes;
185  for (int i=0; i<n; ++i)
186    nodes.push_back(g.addNode());
187  for (int i=0; i<m; ++i)
188    g.addEdge(nodes[random(n)], nodes[random(n)]);
189}
Note: See TracBrowser for help on using the repository browser.