COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/max_matching_test.cc @ 1092:36284b2500c3

Last change on this file since 1092:36284b2500c3 was 1092:36284b2500c3, checked in by jacint, 15 years ago

following the changes of max_matching.h

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 <lemon/max_matching.h>
26//temporarily
27#include <work/jacint/graph_gen.h>
28
29using namespace std;
30using namespace lemon;
31
32int main() {
33
34  typedef UndirListGraph Graph;
35
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;
41   
42  Graph G;
43
44  random_init();
45  randomGraph(G, random(5000), random(20000) ); 
46
47  MaxMatching<Graph> max_matching(G);
48  max_matching.runEdmonds(0);
49 
50  int s=0;
51  Graph::NodeMap<Node> mate(G,INVALID);
52  max_matching.writeNMapNode(mate);
53  for(NodeIt v(G); v!=INVALID; ++v) {
54    if ( mate[v]!=INVALID ) ++s;
55  }
56  int size=(int)s/2;  //size will be used as the size of a maxmatching
57
58  for(NodeIt v(G); v!=INVALID; ++v) {
59    max_matching.mate(v);
60  }
61
62  check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
63
64  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(G);
65  max_matching.writePos(pos0);
66 
67  max_matching.resetMatching();
68  max_matching.runEdmonds(1);
69  s=0;
70  max_matching.writeNMapNode(mate);
71  for(NodeIt v(G); v!=INVALID; ++v) {
72    if ( mate[v]!=INVALID ) ++s;
73  }
74  check ( (int)s/2 == size, "The size does not equal!" );
75
76  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(G);
77  max_matching.writePos(pos1);
78
79  max_matching.run();
80  s=0;
81  max_matching.writeNMapNode(mate);
82  for(NodeIt v(G); v!=INVALID; ++v) {
83    if ( mate[v]!=INVALID ) ++s;
84  }
85  check ( (int)s/2 == size, "The size does not equal!" );
86 
87  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(G);
88  max_matching.writePos(pos2);
89
90  max_matching.resetMatching();
91  max_matching.run();
92  s=0;
93  max_matching.writeNMapNode(mate);
94  for(NodeIt v(G); v!=INVALID; ++v) {
95    if ( mate[v]!=INVALID ) ++s;
96  }
97  check ( (int)s/2 == size, "The size does not equal!" );
98 
99  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(G);
100  max_matching.writePos(pos);
101   
102  bool ismatching=true;
103  for(NodeIt v(G); v!=INVALID; ++v) {
104    if ( mate[v]!=INVALID ) {
105      Node u=mate[v];
106      if (mate[u]!=v) ismatching=false;
107    }
108  } 
109  check ( ismatching, "It is not a matching!" );
110
111  bool coincide=true;
112  for(NodeIt v(G); v!=INVALID; ++v) {
113   if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
114     coincide=false;
115    }
116  }
117  check ( coincide, "The decompositions do not coincide! " );
118
119  bool noedge=true;
120  for(UndirEdgeIt e(G); e!=INVALID; ++e) {
121   if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) ||
122         (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )
123      noedge=false;
124  }
125  check ( noedge, "There are edges between D and C!" );
126 
127  bool oddcomp=true;
128  Graph::NodeMap<bool> todo(G,true);
129  int num_comp=0;
130  for(NodeIt v(G); v!=INVALID; ++v) {
131   if ( pos[v]==max_matching.D && todo[v] ) {
132      int comp_size=1;
133      ++num_comp;
134      std::queue<Node> Q;
135      Q.push(v);
136      todo.set(v,false);
137      while (!Q.empty()) {
138        Node w=Q.front();       
139        Q.pop();
140        for(IncEdgeIt e(G,w); e!=INVALID; ++e) {
141          Node u=G.target(e);
142          if ( pos[u]==max_matching.D && todo[u] ) {
143            ++comp_size;
144            Q.push(u);
145            todo.set(u,false);
146          }
147        }
148      }
149      if ( !(comp_size % 2) ) oddcomp=false; 
150    }
151  }
152  check ( oddcomp, "A component of G[D] is not odd." );
153
154  int barrier=0;
155  for(NodeIt v(G); v!=INVALID; ++v) {
156    if ( pos[v]==max_matching.A ) ++barrier;
157  }
158  int expected_size=(int)( countNodes(G)-num_comp+barrier)/2;
159  check ( size==expected_size, "The size of the matching is wrong." );
160 
161  return 0;
162}
163
164
165void random_init()
166{
167  unsigned int seed = getpid();
168  seed |= seed << 15;
169  seed ^= time(0);
170 
171  srand(seed);
172}
173
174
175int random(int m)
176{
177  return int( double(m) * rand() / (RAND_MAX + 1.0) );
178}
179
180
181/// Generates a random graph with n nodes and m edges.
182/// Before generating the random graph, \c g.clear() is called.
183template<typename Graph>
184void randomGraph(Graph& g, int n, int m) {
185  g.clear();
186  std::vector<typename Graph::Node> nodes;
187  for (int i=0; i<n; ++i)
188    nodes.push_back(g.addNode());
189  for (int i=0; i<m; ++i)
190    g.addEdge(nodes[random(n)], nodes[random(n)]);
191}
Note: See TracBrowser for help on using the repository browser.