COIN-OR::LEMON - Graph Library

Changeset 1423:8c567e298d7f in lemon


Ignore:
Timestamp:
10/27/18 13:00:48 (2 weeks ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Tags:
tip
Message:

Paremeter to stop matching calculation when only single node is unmatched

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/matching.h

    r1270 r1423  
    116116    int _process, _postpone, _last;
    117117
    118     int _node_num;
     118    int _node_num, _unmatched;
    119119
    120120  private:
     
    180180          } else if ((*_status)[v] == UNMATCHED) {
    181181            augmentOnArc(a);
     182            --_unmatched;
    182183            return;
    183184          }
     
    205206              } else if ((*_status)[x] == UNMATCHED) {
    206207                augmentOnArc(b);
     208                --_unmatched;
    207209                return;
    208210              }
     
    229231          } else if ((*_status)[v] == UNMATCHED) {
    230232            augmentOnArc(a);
     233            --_unmatched;
    231234            return;
    232235          }
     
    438441        (*_status)[n] = UNMATCHED;
    439442      }
     443      _unmatched = _node_num;
    440444    }
    441445
     
    449453        (*_status)[n] = UNMATCHED;
    450454      }
     455      _unmatched = _node_num;
    451456      for (NodeIt n(_graph); n != INVALID; ++n) {
    452457        if ((*_matching)[n] == INVALID) {
     
    458463              (*_matching)[v] = _graph.oppositeArc(a);
    459464              (*_status)[v] = MATCHED;
     465              _unmatched -= 2;
    460466              break;
    461467            }
     
    480486        (*_status)[n] = UNMATCHED;
    481487      }
     488      _unmatched = _node_num;
    482489      for(EdgeIt e(_graph); e!=INVALID; ++e) {
    483490        if (matching[e]) {
     
    492499          (*_matching)[v] = _graph.direct(e, false);
    493500          (*_status)[v] = MATCHED;
     501
     502          _unmatched -= 2;
    494503        }
    495504      }
     
    499508    /// \brief Start Edmonds' algorithm
    500509    ///
    501     /// This function runs the original Edmonds' algorithm.
     510    /// This function runs the original Edmonds' algorithm. If the
     511    /// \c decomposition parameter is set to false, then the Gallai-Edmonds
     512    /// decomposition is not computed.
    502513    ///
    503514    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
    504515    /// called before using this function.
    505     void startSparse() {
    506       for(NodeIt n(_graph); n != INVALID; ++n) {
     516    void startSparse(bool decomposition = true) {
     517      int _unmatched_limit = decomposition ? 0 : 1;
     518      for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) {
    507519        if ((*_status)[n] == UNMATCHED) {
    508520          (*_blossom_rep)[_blossom_set->insert(n)] = n;
    509521          _tree_set->insert(n);
    510522          (*_status)[n] = EVEN;
     523          --_unmatched;
    511524          processSparse(n);
    512525        }
     
    518531    ///
    519532    /// This function runs Edmonds' algorithm with a heuristic of postponing
    520     /// shrinks, therefore resulting in a faster algorithm for dense graphs.
     533    /// shrinks, therefore resulting in a faster algorithm for dense graphs.  If
     534    /// the \c decomposition parameter is set to false, then the Gallai-Edmonds
     535    /// decomposition is not computed.
    521536    ///
    522537    /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
    523538    /// called before using this function.
    524     void startDense() {
    525       for(NodeIt n(_graph); n != INVALID; ++n) {
     539    void startDense(bool decomposition = true) {
     540      int _unmatched_limit = decomposition ? 0 : 1;
     541      for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) {
    526542        if ((*_status)[n] == UNMATCHED) {
    527543          (*_blossom_rep)[_blossom_set->insert(n)] = n;
    528544          _tree_set->insert(n);
    529545          (*_status)[n] = EVEN;
     546          --_unmatched;
    530547          processDense(n);
    531548        }
     
    537554    ///
    538555    /// This function runs Edmonds' algorithm. An additional heuristic of
    539     /// postponing shrinks is used for relatively dense graphs
    540     /// (for which <tt>m>=2*n</tt> holds).
    541     void run() {
     556    /// postponing shrinks is used for relatively dense graphs (for which
     557    /// <tt>m>=2*n</tt> holds). If the \c decomposition parameter is set to
     558    /// false, then the Gallai-Edmonds decomposition is not computed. In some
     559    /// cases, this can speed up the algorithm significantly, especially when a
     560    /// maximum matching is computed in a dense graph with odd number of nodes.
     561    void run(bool decomposition = true) {
    542562      if (countEdges(_graph) < 2 * countNodes(_graph)) {
    543563        greedyInit();
    544         startSparse();
     564        startSparse(decomposition);
    545565      } else {
    546566        init();
    547         startDense();
     567        startDense(decomposition);
    548568      }
    549569    }
  • test/matching_test.cc

    r1270 r1423  
    135135  mat_test.startDense();
    136136  mat_test.run();
     137  mat_test.startSparse(false);
     138  mat_test.startDense(false);
     139  mat_test.run(false);
    137140
    138141  const_mat_test.matchingSize();
     
    403406      edgeMap("weight", weight).run();
    404407
     408    int size;
    405409    bool perfect;
    406410    {
     
    408412      mm.run();
    409413      checkMatching(graph, mm);
     414      size = mm.matchingSize();
    410415      perfect = 2 * mm.matchingSize() == countNodes(graph);
     416    }
     417
     418    {
     419      MaxMatching<SmartGraph> mm(graph);
     420      mm.init();
     421      mm.startSparse();
     422      checkMatching(graph, mm);
     423      check(size == mm.matchingSize(), "Inconsistent matching size");
     424    }
     425
     426    {
     427      MaxMatching<SmartGraph> mm(graph);
     428      mm.init();
     429      mm.startDense();
     430      checkMatching(graph, mm);
     431      check(size == mm.matchingSize(), "Inconsistent matching size");
     432    }
     433
     434    {
     435      MaxMatching<SmartGraph> mm(graph);
     436      mm.greedyInit();
     437      mm.startSparse();
     438      checkMatching(graph, mm);
     439      check(size == mm.matchingSize(), "Inconsistent matching size");
     440    }
     441
     442    {
     443      MaxMatching<SmartGraph> mm(graph);
     444      mm.greedyInit();
     445      mm.startDense();
     446      checkMatching(graph, mm);
     447      check(size == mm.matchingSize(), "Inconsistent matching size");
     448    }
     449
     450    {
     451      MaxMatching<SmartGraph> mm(graph);
     452      mm.run(false);
     453      check(size == mm.matchingSize(), "Inconsistent max cardinality matching");
     454    }
     455
     456    {
     457      MaxMatching<SmartGraph> mm(graph);
     458      mm.init();
     459      mm.startSparse(false);
     460      check(size == mm.matchingSize(), "Inconsistent matching size");
     461    }
     462
     463    {
     464      MaxMatching<SmartGraph> mm(graph);
     465      mm.init();
     466      mm.startDense(false);
     467      check(size == mm.matchingSize(), "Inconsistent matching size");
     468    }
     469
     470    {
     471      MaxMatching<SmartGraph> mm(graph);
     472      mm.greedyInit();
     473      mm.startSparse(false);
     474      check(size == mm.matchingSize(), "Inconsistent matching size");
     475    }
     476
     477    {
     478      MaxMatching<SmartGraph> mm(graph);
     479      mm.greedyInit();
     480      mm.startDense(false);
     481      check(size == mm.matchingSize(), "Inconsistent matching size");
    411482    }
    412483
Note: See TracChangeset for help on using the changeset viewer.