test/max_matching_test.cc
author deba
Thu, 23 Feb 2006 08:55:54 +0000
changeset 1980 a954b780e3ab
parent 1909 2d806130e700
child 1993 2115143eceea
permissions -rw-r--r--
Renaming to be convient to the naming of the adaptors
Concept checking of the ugraph adaptors
jacint@1078
     1
/* -*- C++ -*-
jacint@1078
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@1956
     5
 * Copyright (C) 2003-2006
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
jacint@1078
     8
 *
jacint@1078
     9
 * Permission to use, modify and distribute this software is granted
jacint@1078
    10
 * provided that this copyright notice appears in all copies. For
jacint@1078
    11
 * precise terms see the accompanying LICENSE file.
jacint@1078
    12
 *
jacint@1078
    13
 * This software is provided "AS IS" with no warranty of any kind,
jacint@1078
    14
 * express or implied, and with no claim as to its suitability for any
jacint@1078
    15
 * purpose.
jacint@1078
    16
 *
jacint@1078
    17
 */
jacint@1078
    18
jacint@1078
    19
#include <iostream>
jacint@1098
    20
#include <vector>
jacint@1078
    21
#include <queue>
alpar@1494
    22
#include <cmath>
jacint@1078
    23
#include <cstdlib>
jacint@1078
    24
jacint@1078
    25
#include "test_tools.h"
jacint@1078
    26
#include <lemon/invalid.h>
jacint@1078
    27
#include <lemon/list_graph.h>
jacint@1092
    28
#include <lemon/max_matching.h>
jacint@1078
    29
jacint@1078
    30
using namespace std;
jacint@1078
    31
using namespace lemon;
jacint@1078
    32
jacint@1078
    33
int main() {
jacint@1078
    34
klao@1909
    35
  typedef ListUGraph Graph;
jacint@1078
    36
jacint@1078
    37
  typedef Graph::Edge Edge;
klao@1909
    38
  typedef Graph::UEdgeIt UEdgeIt;
jacint@1078
    39
  typedef Graph::IncEdgeIt IncEdgeIt;
jacint@1078
    40
  typedef Graph::NodeIt NodeIt;
jacint@1078
    41
  typedef Graph::Node Node;
jacint@1078
    42
   
jacint@1098
    43
  Graph g;
jacint@1098
    44
  g.clear();
jacint@1078
    45
jacint@1098
    46
  std::vector<Graph::Node> nodes;
jacint@1098
    47
  for (int i=0; i<13; ++i)
jacint@1098
    48
      nodes.push_back(g.addNode());
jacint@1078
    49
jacint@1098
    50
  g.addEdge(nodes[0], nodes[0]);
jacint@1098
    51
  g.addEdge(nodes[6], nodes[10]);
jacint@1098
    52
  g.addEdge(nodes[5], nodes[10]);
jacint@1098
    53
  g.addEdge(nodes[4], nodes[10]);
jacint@1098
    54
  g.addEdge(nodes[3], nodes[11]);  
jacint@1098
    55
  g.addEdge(nodes[1], nodes[6]);
jacint@1098
    56
  g.addEdge(nodes[4], nodes[7]);  
jacint@1098
    57
  g.addEdge(nodes[1], nodes[8]);
jacint@1098
    58
  g.addEdge(nodes[0], nodes[8]);
jacint@1098
    59
  g.addEdge(nodes[3], nodes[12]);
jacint@1098
    60
  g.addEdge(nodes[6], nodes[9]);
jacint@1098
    61
  g.addEdge(nodes[9], nodes[11]);
jacint@1098
    62
  g.addEdge(nodes[2], nodes[10]);
jacint@1098
    63
  g.addEdge(nodes[10], nodes[8]);
jacint@1098
    64
  g.addEdge(nodes[5], nodes[8]);
jacint@1098
    65
  g.addEdge(nodes[6], nodes[3]);
jacint@1098
    66
  g.addEdge(nodes[0], nodes[5]);
jacint@1098
    67
  g.addEdge(nodes[6], nodes[12]);
jacint@1098
    68
  
jacint@1098
    69
  MaxMatching<Graph> max_matching(g);
jacint@1078
    70
  max_matching.runEdmonds(0);
jacint@1078
    71
  
jacint@1078
    72
  int s=0;
jacint@1098
    73
  Graph::NodeMap<Node> mate(g,INVALID);
jacint@1078
    74
  max_matching.writeNMapNode(mate);
jacint@1098
    75
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
    76
    if ( mate[v]!=INVALID ) ++s;
jacint@1078
    77
  }
jacint@1078
    78
  int size=(int)s/2;  //size will be used as the size of a maxmatching
jacint@1092
    79
jacint@1098
    80
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1092
    81
    max_matching.mate(v);
jacint@1092
    82
  }
jacint@1092
    83
jacint@1078
    84
  check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
jacint@1078
    85
jacint@1098
    86
  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
jacint@1078
    87
  max_matching.writePos(pos0);
jacint@1078
    88
  
jacint@1078
    89
  max_matching.resetMatching();
jacint@1078
    90
  max_matching.runEdmonds(1);
jacint@1078
    91
  s=0;
jacint@1078
    92
  max_matching.writeNMapNode(mate);
jacint@1098
    93
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
    94
    if ( mate[v]!=INVALID ) ++s;
jacint@1078
    95
  }
jacint@1078
    96
  check ( (int)s/2 == size, "The size does not equal!" );
jacint@1078
    97
jacint@1098
    98
  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
jacint@1078
    99
  max_matching.writePos(pos1);
jacint@1078
   100
jacint@1078
   101
  max_matching.run();
jacint@1078
   102
  s=0;
jacint@1078
   103
  max_matching.writeNMapNode(mate);
jacint@1098
   104
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
   105
    if ( mate[v]!=INVALID ) ++s;
jacint@1078
   106
  }
jacint@1078
   107
  check ( (int)s/2 == size, "The size does not equal!" ); 
jacint@1078
   108
  
jacint@1098
   109
  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
jacint@1078
   110
  max_matching.writePos(pos2);
jacint@1078
   111
jacint@1078
   112
  max_matching.resetMatching();
jacint@1078
   113
  max_matching.run();
jacint@1078
   114
  s=0;
jacint@1078
   115
  max_matching.writeNMapNode(mate);
jacint@1098
   116
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
   117
    if ( mate[v]!=INVALID ) ++s;
jacint@1078
   118
  }
jacint@1078
   119
  check ( (int)s/2 == size, "The size does not equal!" ); 
jacint@1078
   120
  
jacint@1098
   121
  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
jacint@1078
   122
  max_matching.writePos(pos);
jacint@1078
   123
   
jacint@1078
   124
  bool ismatching=true;
jacint@1098
   125
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
   126
    if ( mate[v]!=INVALID ) {
jacint@1078
   127
      Node u=mate[v];
jacint@1078
   128
      if (mate[u]!=v) ismatching=false; 
jacint@1078
   129
    }
jacint@1078
   130
  }  
jacint@1078
   131
  check ( ismatching, "It is not a matching!" );
jacint@1078
   132
jacint@1078
   133
  bool coincide=true;
jacint@1098
   134
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
   135
   if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
jacint@1078
   136
     coincide=false;
jacint@1078
   137
    }
jacint@1078
   138
  }
jacint@1078
   139
  check ( coincide, "The decompositions do not coincide! " );
jacint@1078
   140
jacint@1078
   141
  bool noedge=true;
klao@1909
   142
  for(UEdgeIt e(g); e!=INVALID; ++e) {
jacint@1098
   143
   if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) || 
jacint@1098
   144
	 (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
jacint@1078
   145
      noedge=false; 
jacint@1078
   146
  }
jacint@1078
   147
  check ( noedge, "There are edges between D and C!" );
jacint@1078
   148
  
jacint@1078
   149
  bool oddcomp=true;
jacint@1098
   150
  Graph::NodeMap<bool> todo(g,true);
jacint@1078
   151
  int num_comp=0;
jacint@1098
   152
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
   153
   if ( pos[v]==max_matching.D && todo[v] ) {
jacint@1078
   154
      int comp_size=1;
jacint@1078
   155
      ++num_comp;
jacint@1078
   156
      std::queue<Node> Q;
jacint@1078
   157
      Q.push(v);
jacint@1078
   158
      todo.set(v,false);
jacint@1078
   159
      while (!Q.empty()) {
jacint@1078
   160
	Node w=Q.front();	
jacint@1078
   161
	Q.pop();
jacint@1098
   162
	for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
klao@1158
   163
	  Node u=g.runningNode(e);
jacint@1078
   164
	  if ( pos[u]==max_matching.D && todo[u] ) {
jacint@1078
   165
	    ++comp_size;
jacint@1078
   166
	    Q.push(u);
jacint@1078
   167
	    todo.set(u,false);
jacint@1078
   168
	  }
jacint@1078
   169
	}
jacint@1078
   170
      }
jacint@1078
   171
      if ( !(comp_size % 2) ) oddcomp=false;  
jacint@1078
   172
    }
jacint@1078
   173
  }
jacint@1098
   174
  check ( oddcomp, "A component of g[D] is not odd." );
jacint@1078
   175
jacint@1078
   176
  int barrier=0;
jacint@1098
   177
  for(NodeIt v(g); v!=INVALID; ++v) {
jacint@1078
   178
    if ( pos[v]==max_matching.A ) ++barrier;
jacint@1078
   179
  }
jacint@1098
   180
  int expected_size=(int)( countNodes(g)-num_comp+barrier)/2;
jacint@1078
   181
  check ( size==expected_size, "The size of the matching is wrong." );
jacint@1078
   182
  
jacint@1078
   183
  return 0;
jacint@1078
   184
}