COIN-OR::LEMON - Graph Library

Changeset 327:91d63b8b1a4c in lemon-main for test/max_matching_test.cc


Ignore:
Timestamp:
10/13/08 14:00:11 (16 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Several improvements in maximum matching algorithms

  • The interface of MaxMatching? is changed to be similar to the weighted algorithms
  • The internal data structure (the queue implementation and the matching map) is changed in the MaxMatching? algorithm, which provides better runtime properties
  • The Blossom iterators are changed slightly in the weighted matching algorithms
  • Several documentation improvments
  • The test files are merged
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/max_matching_test.cc

    r326 r327  
    1818
    1919#include <iostream>
     20#include <sstream>
    2021#include <vector>
    2122#include <queue>
     
    2324#include <cstdlib>
    2425
     26#include <lemon/max_matching.h>
     27#include <lemon/smart_graph.h>
     28#include <lemon/lgf_reader.h>
     29
    2530#include "test_tools.h"
    26 #include <lemon/list_graph.h>
    27 #include <lemon/max_matching.h>
    2831
    2932using namespace std;
    3033using namespace lemon;
    3134
     35GRAPH_TYPEDEFS(SmartGraph);
     36
     37
     38const int lgfn = 3;
     39const std::string lgf[lgfn] = {
     40  "@nodes\n"
     41  "label\n"
     42  "0\n"
     43  "1\n"
     44  "2\n"
     45  "3\n"
     46  "4\n"
     47  "5\n"
     48  "6\n"
     49  "7\n"
     50  "@edges\n"
     51  "     label  weight\n"
     52  "7 4  0      984\n"
     53  "0 7  1      73\n"
     54  "7 1  2      204\n"
     55  "2 3  3      583\n"
     56  "2 7  4      565\n"
     57  "2 1  5      582\n"
     58  "0 4  6      551\n"
     59  "2 5  7      385\n"
     60  "1 5  8      561\n"
     61  "5 3  9      484\n"
     62  "7 5  10     904\n"
     63  "3 6  11     47\n"
     64  "7 6  12     888\n"
     65  "3 0  13     747\n"
     66  "6 1  14     310\n",
     67
     68  "@nodes\n"
     69  "label\n"
     70  "0\n"
     71  "1\n"
     72  "2\n"
     73  "3\n"
     74  "4\n"
     75  "5\n"
     76  "6\n"
     77  "7\n"
     78  "@edges\n"
     79  "     label  weight\n"
     80  "2 5  0      710\n"
     81  "0 5  1      241\n"
     82  "2 4  2      856\n"
     83  "2 6  3      762\n"
     84  "4 1  4      747\n"
     85  "6 1  5      962\n"
     86  "4 7  6      723\n"
     87  "1 7  7      661\n"
     88  "2 3  8      376\n"
     89  "1 0  9      416\n"
     90  "6 7  10     391\n",
     91
     92  "@nodes\n"
     93  "label\n"
     94  "0\n"
     95  "1\n"
     96  "2\n"
     97  "3\n"
     98  "4\n"
     99  "5\n"
     100  "6\n"
     101  "7\n"
     102  "@edges\n"
     103  "     label  weight\n"
     104  "6 2  0      553\n"
     105  "0 7  1      653\n"
     106  "6 3  2      22\n"
     107  "4 7  3      846\n"
     108  "7 2  4      981\n"
     109  "7 6  5      250\n"
     110  "5 2  6      539\n",
     111};
     112
     113void checkMatching(const SmartGraph& graph,
     114                   const MaxMatching<SmartGraph>& mm) {
     115  int num = 0;
     116
     117  IntNodeMap comp_index(graph);
     118  UnionFind<IntNodeMap> comp(comp_index);
     119
     120  int barrier_num = 0;
     121
     122  for (NodeIt n(graph); n != INVALID; ++n) {
     123    check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
     124          mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
     125    if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
     126      ++barrier_num;
     127    } else {
     128      comp.insert(n);
     129    }
     130  }
     131
     132  for (EdgeIt e(graph); e != INVALID; ++e) {
     133    if (mm.matching(e)) {
     134      check(e == mm.matching(graph.u(e)), "Wrong matching");
     135      check(e == mm.matching(graph.v(e)), "Wrong matching");
     136      ++num;
     137    }
     138    check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
     139          mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
     140          "Wrong Gallai-Edmonds decomposition");
     141
     142    check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
     143          mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
     144          "Wrong Gallai-Edmonds decomposition");
     145
     146    if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
     147        mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
     148      comp.join(graph.u(e), graph.v(e));
     149    }
     150  }
     151
     152  std::set<int> comp_root;
     153  int odd_comp_num = 0;
     154  for (NodeIt n(graph); n != INVALID; ++n) {
     155    if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
     156      int root = comp.find(n);
     157      if (comp_root.find(root) == comp_root.end()) {
     158        comp_root.insert(root);
     159        if (comp.size(n) % 2 == 1) {
     160          ++odd_comp_num;
     161        }
     162      }
     163    }
     164  }
     165
     166  check(mm.matchingSize() == num, "Wrong matching");
     167  check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num),
     168         "Wrong matching");
     169  return;
     170}
     171
     172void checkWeightedMatching(const SmartGraph& graph,
     173                   const SmartGraph::EdgeMap<int>& weight,
     174                   const MaxWeightedMatching<SmartGraph>& mwm) {
     175  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
     176    if (graph.u(e) == graph.v(e)) continue;
     177    int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
     178
     179    for (int i = 0; i < mwm.blossomNum(); ++i) {
     180      bool s = false, t = false;
     181      for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
     182           n != INVALID; ++n) {
     183        if (graph.u(e) == n) s = true;
     184        if (graph.v(e) == n) t = true;
     185      }
     186      if (s == true && t == true) {
     187        rw += mwm.blossomValue(i);
     188      }
     189    }
     190    rw -= weight[e] * mwm.dualScale;
     191
     192    check(rw >= 0, "Negative reduced weight");
     193    check(rw == 0 || !mwm.matching(e),
     194          "Non-zero reduced weight on matching edge");
     195  }
     196
     197  int pv = 0;
     198  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
     199    if (mwm.matching(n) != INVALID) {
     200      check(mwm.nodeValue(n) >= 0, "Invalid node value");
     201      pv += weight[mwm.matching(n)];
     202      SmartGraph::Node o = graph.target(mwm.matching(n));
     203      check(mwm.mate(n) == o, "Invalid matching");
     204      check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
     205            "Invalid matching");
     206    } else {
     207      check(mwm.mate(n) == INVALID, "Invalid matching");
     208      check(mwm.nodeValue(n) == 0, "Invalid matching");
     209    }
     210  }
     211
     212  int dv = 0;
     213  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
     214    dv += mwm.nodeValue(n);
     215  }
     216
     217  for (int i = 0; i < mwm.blossomNum(); ++i) {
     218    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
     219    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
     220    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
     221  }
     222
     223  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
     224
     225  return;
     226}
     227
     228void checkWeightedPerfectMatching(const SmartGraph& graph,
     229                          const SmartGraph::EdgeMap<int>& weight,
     230                          const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
     231  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
     232    if (graph.u(e) == graph.v(e)) continue;
     233    int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
     234
     235    for (int i = 0; i < mwpm.blossomNum(); ++i) {
     236      bool s = false, t = false;
     237      for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
     238           n != INVALID; ++n) {
     239        if (graph.u(e) == n) s = true;
     240        if (graph.v(e) == n) t = true;
     241      }
     242      if (s == true && t == true) {
     243        rw += mwpm.blossomValue(i);
     244      }
     245    }
     246    rw -= weight[e] * mwpm.dualScale;
     247
     248    check(rw >= 0, "Negative reduced weight");
     249    check(rw == 0 || !mwpm.matching(e),
     250          "Non-zero reduced weight on matching edge");
     251  }
     252
     253  int pv = 0;
     254  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
     255    check(mwpm.matching(n) != INVALID, "Non perfect");
     256    pv += weight[mwpm.matching(n)];
     257    SmartGraph::Node o = graph.target(mwpm.matching(n));
     258    check(mwpm.mate(n) == o, "Invalid matching");
     259    check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
     260          "Invalid matching");
     261  }
     262
     263  int dv = 0;
     264  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
     265    dv += mwpm.nodeValue(n);
     266  }
     267
     268  for (int i = 0; i < mwpm.blossomNum(); ++i) {
     269    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
     270    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
     271    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
     272  }
     273
     274  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
     275
     276  return;
     277}
     278
     279
    32280int main() {
    33281
    34   typedef ListGraph Graph;
    35 
    36   GRAPH_TYPEDEFS(Graph);
    37 
    38   Graph g;
    39   g.clear();
    40 
    41   std::vector<Graph::Node> nodes;
    42   for (int i=0; i<13; ++i)
    43       nodes.push_back(g.addNode());
    44 
    45   g.addEdge(nodes[0], nodes[0]);
    46   g.addEdge(nodes[6], nodes[10]);
    47   g.addEdge(nodes[5], nodes[10]);
    48   g.addEdge(nodes[4], nodes[10]);
    49   g.addEdge(nodes[3], nodes[11]);
    50   g.addEdge(nodes[1], nodes[6]);
    51   g.addEdge(nodes[4], nodes[7]);
    52   g.addEdge(nodes[1], nodes[8]);
    53   g.addEdge(nodes[0], nodes[8]);
    54   g.addEdge(nodes[3], nodes[12]);
    55   g.addEdge(nodes[6], nodes[9]);
    56   g.addEdge(nodes[9], nodes[11]);
    57   g.addEdge(nodes[2], nodes[10]);
    58   g.addEdge(nodes[10], nodes[8]);
    59   g.addEdge(nodes[5], nodes[8]);
    60   g.addEdge(nodes[6], nodes[3]);
    61   g.addEdge(nodes[0], nodes[5]);
    62   g.addEdge(nodes[6], nodes[12]);
    63 
    64   MaxMatching<Graph> max_matching(g);
    65   max_matching.init();
    66   max_matching.startDense();
    67 
    68   int s=0;
    69   Graph::NodeMap<Node> mate(g,INVALID);
    70   max_matching.mateMap(mate);
    71   for(NodeIt v(g); v!=INVALID; ++v) {
    72     if ( mate[v]!=INVALID ) ++s;
    73   }
    74   int size=int(s/2);  //size will be used as the size of a maxmatching
    75 
    76   for(NodeIt v(g); v!=INVALID; ++v) {
    77     max_matching.mate(v);
    78   }
    79 
    80   check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
    81 
    82   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g);
    83   max_matching.decomposition(pos0);
    84 
    85   max_matching.init();
    86   max_matching.startSparse();
    87   s=0;
    88   max_matching.mateMap(mate);
    89   for(NodeIt v(g); v!=INVALID; ++v) {
    90     if ( mate[v]!=INVALID ) ++s;
    91   }
    92   check ( int(s/2) == size, "The size does not equal!" );
    93 
    94   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g);
    95   max_matching.decomposition(pos1);
    96 
    97   max_matching.run();
    98   s=0;
    99   max_matching.mateMap(mate);
    100   for(NodeIt v(g); v!=INVALID; ++v) {
    101     if ( mate[v]!=INVALID ) ++s;
    102   }
    103   check ( int(s/2) == size, "The size does not equal!" );
    104 
    105   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g);
    106   max_matching.decomposition(pos2);
    107 
    108   max_matching.run();
    109   s=0;
    110   max_matching.mateMap(mate);
    111   for(NodeIt v(g); v!=INVALID; ++v) {
    112     if ( mate[v]!=INVALID ) ++s;
    113   }
    114   check ( int(s/2) == size, "The size does not equal!" );
    115 
    116   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g);
    117   max_matching.decomposition(pos);
    118 
    119   bool ismatching=true;
    120   for(NodeIt v(g); v!=INVALID; ++v) {
    121     if ( mate[v]!=INVALID ) {
    122       Node u=mate[v];
    123       if (mate[u]!=v) ismatching=false;
    124     }
    125   }
    126   check ( ismatching, "It is not a matching!" );
    127 
    128   bool coincide=true;
    129   for(NodeIt v(g); v!=INVALID; ++v) {
    130    if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
    131      coincide=false;
    132     }
    133   }
    134   check ( coincide, "The decompositions do not coincide! " );
    135 
    136   bool noarc=true;
    137   for(EdgeIt e(g); e!=INVALID; ++e) {
    138    if ( (pos[g.v(e)]==max_matching.C &&
    139          pos[g.u(e)]==max_matching.D) ||
    140          (pos[g.v(e)]==max_matching.D &&
    141           pos[g.u(e)]==max_matching.C) )
    142       noarc=false;
    143   }
    144   check ( noarc, "There are arcs between D and C!" );
    145 
    146   bool oddcomp=true;
    147   Graph::NodeMap<bool> todo(g,true);
    148   int num_comp=0;
    149   for(NodeIt v(g); v!=INVALID; ++v) {
    150    if ( pos[v]==max_matching.D && todo[v] ) {
    151       int comp_size=1;
    152       ++num_comp;
    153       std::queue<Node> Q;
    154       Q.push(v);
    155       todo.set(v,false);
    156       while (!Q.empty()) {
    157         Node w=Q.front();
    158         Q.pop();
    159         for(IncEdgeIt e(g,w); e!=INVALID; ++e) {
    160           Node u=g.runningNode(e);
    161           if ( pos[u]==max_matching.D && todo[u] ) {
    162             ++comp_size;
    163             Q.push(u);
    164             todo.set(u,false);
    165           }
    166         }
    167       }
    168       if ( !(comp_size % 2) ) oddcomp=false;
    169     }
    170   }
    171   check ( oddcomp, "A component of g[D] is not odd." );
    172 
    173   int barrier=0;
    174   for(NodeIt v(g); v!=INVALID; ++v) {
    175     if ( pos[v]==max_matching.A ) ++barrier;
    176   }
    177   int expected_size=int( countNodes(g)-num_comp+barrier)/2;
    178   check ( size==expected_size, "The size of the matching is wrong." );
     282  for (int i = 0; i < lgfn; ++i) {
     283    SmartGraph graph;
     284    SmartGraph::EdgeMap<int> weight(graph);
     285
     286    istringstream lgfs(lgf[i]);
     287    graphReader(graph, lgfs).
     288      edgeMap("weight", weight).run();
     289
     290    MaxMatching<SmartGraph> mm(graph);
     291    mm.run();
     292    checkMatching(graph, mm);
     293
     294    MaxWeightedMatching<SmartGraph> mwm(graph, weight);
     295    mwm.run();
     296    checkWeightedMatching(graph, weight, mwm);
     297
     298    MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
     299    bool perfect = mwpm.run();
     300
     301    check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
     302          "Perfect matching found");
     303
     304    if (perfect) {
     305      checkWeightedPerfectMatching(graph, weight, mwpm);
     306    }
     307  }
    179308
    180309  return 0;
Note: See TracChangeset for help on using the changeset viewer.