1.1 --- a/src/test/max_matching_test.cc Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,183 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/test/max_matching_test.cc -
1.6 - * Part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.9 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.10 - *
1.11 - * Permission to use, modify and distribute this software is granted
1.12 - * provided that this copyright notice appears in all copies. For
1.13 - * precise terms see the accompanying LICENSE file.
1.14 - *
1.15 - * This software is provided "AS IS" with no warranty of any kind,
1.16 - * express or implied, and with no claim as to its suitability for any
1.17 - * purpose.
1.18 - *
1.19 - */
1.20 -
1.21 -#include <iostream>
1.22 -#include <vector>
1.23 -#include <queue>
1.24 -#include <math.h>
1.25 -#include <cstdlib>
1.26 -
1.27 -#include "test_tools.h"
1.28 -#include <lemon/invalid.h>
1.29 -#include <lemon/list_graph.h>
1.30 -#include <lemon/max_matching.h>
1.31 -
1.32 -using namespace std;
1.33 -using namespace lemon;
1.34 -
1.35 -int main() {
1.36 -
1.37 - typedef UndirListGraph Graph;
1.38 -
1.39 - typedef Graph::Edge Edge;
1.40 - typedef Graph::UndirEdgeIt UndirEdgeIt;
1.41 - typedef Graph::IncEdgeIt IncEdgeIt;
1.42 - typedef Graph::NodeIt NodeIt;
1.43 - typedef Graph::Node Node;
1.44 -
1.45 - Graph g;
1.46 - g.clear();
1.47 -
1.48 - std::vector<Graph::Node> nodes;
1.49 - for (int i=0; i<13; ++i)
1.50 - nodes.push_back(g.addNode());
1.51 -
1.52 - g.addEdge(nodes[0], nodes[0]);
1.53 - g.addEdge(nodes[6], nodes[10]);
1.54 - g.addEdge(nodes[5], nodes[10]);
1.55 - g.addEdge(nodes[4], nodes[10]);
1.56 - g.addEdge(nodes[3], nodes[11]);
1.57 - g.addEdge(nodes[1], nodes[6]);
1.58 - g.addEdge(nodes[4], nodes[7]);
1.59 - g.addEdge(nodes[1], nodes[8]);
1.60 - g.addEdge(nodes[0], nodes[8]);
1.61 - g.addEdge(nodes[3], nodes[12]);
1.62 - g.addEdge(nodes[6], nodes[9]);
1.63 - g.addEdge(nodes[9], nodes[11]);
1.64 - g.addEdge(nodes[2], nodes[10]);
1.65 - g.addEdge(nodes[10], nodes[8]);
1.66 - g.addEdge(nodes[5], nodes[8]);
1.67 - g.addEdge(nodes[6], nodes[3]);
1.68 - g.addEdge(nodes[0], nodes[5]);
1.69 - g.addEdge(nodes[6], nodes[12]);
1.70 -
1.71 - MaxMatching<Graph> max_matching(g);
1.72 - max_matching.runEdmonds(0);
1.73 -
1.74 - int s=0;
1.75 - Graph::NodeMap<Node> mate(g,INVALID);
1.76 - max_matching.writeNMapNode(mate);
1.77 - for(NodeIt v(g); v!=INVALID; ++v) {
1.78 - if ( mate[v]!=INVALID ) ++s;
1.79 - }
1.80 - int size=(int)s/2; //size will be used as the size of a maxmatching
1.81 -
1.82 - for(NodeIt v(g); v!=INVALID; ++v) {
1.83 - max_matching.mate(v);
1.84 - }
1.85 -
1.86 - check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
1.87 -
1.88 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
1.89 - max_matching.writePos(pos0);
1.90 -
1.91 - max_matching.resetMatching();
1.92 - max_matching.runEdmonds(1);
1.93 - s=0;
1.94 - max_matching.writeNMapNode(mate);
1.95 - for(NodeIt v(g); v!=INVALID; ++v) {
1.96 - if ( mate[v]!=INVALID ) ++s;
1.97 - }
1.98 - check ( (int)s/2 == size, "The size does not equal!" );
1.99 -
1.100 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
1.101 - max_matching.writePos(pos1);
1.102 -
1.103 - max_matching.run();
1.104 - s=0;
1.105 - max_matching.writeNMapNode(mate);
1.106 - for(NodeIt v(g); v!=INVALID; ++v) {
1.107 - if ( mate[v]!=INVALID ) ++s;
1.108 - }
1.109 - check ( (int)s/2 == size, "The size does not equal!" );
1.110 -
1.111 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
1.112 - max_matching.writePos(pos2);
1.113 -
1.114 - max_matching.resetMatching();
1.115 - max_matching.run();
1.116 - s=0;
1.117 - max_matching.writeNMapNode(mate);
1.118 - for(NodeIt v(g); v!=INVALID; ++v) {
1.119 - if ( mate[v]!=INVALID ) ++s;
1.120 - }
1.121 - check ( (int)s/2 == size, "The size does not equal!" );
1.122 -
1.123 - Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
1.124 - max_matching.writePos(pos);
1.125 -
1.126 - bool ismatching=true;
1.127 - for(NodeIt v(g); v!=INVALID; ++v) {
1.128 - if ( mate[v]!=INVALID ) {
1.129 - Node u=mate[v];
1.130 - if (mate[u]!=v) ismatching=false;
1.131 - }
1.132 - }
1.133 - check ( ismatching, "It is not a matching!" );
1.134 -
1.135 - bool coincide=true;
1.136 - for(NodeIt v(g); v!=INVALID; ++v) {
1.137 - if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
1.138 - coincide=false;
1.139 - }
1.140 - }
1.141 - check ( coincide, "The decompositions do not coincide! " );
1.142 -
1.143 - bool noedge=true;
1.144 - for(UndirEdgeIt e(g); e!=INVALID; ++e) {
1.145 - if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) ||
1.146 - (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
1.147 - noedge=false;
1.148 - }
1.149 - check ( noedge, "There are edges between D and C!" );
1.150 -
1.151 - bool oddcomp=true;
1.152 - Graph::NodeMap<bool> todo(g,true);
1.153 - int num_comp=0;
1.154 - for(NodeIt v(g); v!=INVALID; ++v) {
1.155 - if ( pos[v]==max_matching.D && todo[v] ) {
1.156 - int comp_size=1;
1.157 - ++num_comp;
1.158 - std::queue<Node> Q;
1.159 - Q.push(v);
1.160 - todo.set(v,false);
1.161 - while (!Q.empty()) {
1.162 - Node w=Q.front();
1.163 - Q.pop();
1.164 - for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
1.165 - Node u=g.runningNode(e);
1.166 - if ( pos[u]==max_matching.D && todo[u] ) {
1.167 - ++comp_size;
1.168 - Q.push(u);
1.169 - todo.set(u,false);
1.170 - }
1.171 - }
1.172 - }
1.173 - if ( !(comp_size % 2) ) oddcomp=false;
1.174 - }
1.175 - }
1.176 - check ( oddcomp, "A component of g[D] is not odd." );
1.177 -
1.178 - int barrier=0;
1.179 - for(NodeIt v(g); v!=INVALID; ++v) {
1.180 - if ( pos[v]==max_matching.A ) ++barrier;
1.181 - }
1.182 - int expected_size=(int)( countNodes(g)-num_comp+barrier)/2;
1.183 - check ( size==expected_size, "The size of the matching is wrong." );
1.184 -
1.185 - return 0;
1.186 -}