Changeset 1423:8c567e298d7f in lemon for lemon/matching.h

Timestamp:

10/27/18 13:00:48 (6 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Children:

1426:736a341e604b, 1427:57abff252556, 1430:c6aa2cc1af04

Phase:

public

Message:

Paremeter to stop matching calculation when only single node is unmatched

File:

• lemon/matching.h (modified) (12 diffs)

lemon/matching.h

@@ -116 +116 @@
     int _process, _postpone, _last;
 
-    int _node_num;
+    int _node_num, _unmatched;
 
   private:
@@ -180 +180 @@
           } else if ((*_status)[v] == UNMATCHED) {
             augmentOnArc(a);
+            --_unmatched;
             return;
           }
@@ -205 +206 @@
               } else if ((*_status)[x] == UNMATCHED) {
                 augmentOnArc(b);
+                --_unmatched;
                 return;
               }
@@ -229 +231 @@
           } else if ((*_status)[v] == UNMATCHED) {
             augmentOnArc(a);
+            --_unmatched;
             return;
           }
@@ -438 +441 @@
         (*_status)[n] = UNMATCHED;
       }
+      _unmatched = _node_num;
     }
 
@@ -449 +453 @@
         (*_status)[n] = UNMATCHED;
       }
+      _unmatched = _node_num;
       for (NodeIt n(_graph); n != INVALID; ++n) {
         if ((*_matching)[n] == INVALID) {
@@ -458 +463 @@
               (*_matching)[v] = _graph.oppositeArc(a);
               (*_status)[v] = MATCHED;
+              _unmatched -= 2;
               break;
             }
@@ -480 +486 @@
         (*_status)[n] = UNMATCHED;
       }
+      _unmatched = _node_num;
       for(EdgeIt e(_graph); e!=INVALID; ++e) {
         if (matching[e]) {
@@ -492 +499 @@
           (*_matching)[v] = _graph.direct(e, false);
           (*_status)[v] = MATCHED;
+
+          _unmatched -= 2;
         }
       }
@@ -499 +508 @@
     /// \brief Start Edmonds' algorithm
     ///
-    /// This function runs the original Edmonds' algorithm.
+    /// This function runs the original Edmonds' algorithm. If the
+    /// \c decomposition parameter is set to false, then the Gallai-Edmonds
+    /// decomposition is not computed.
     ///
     /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
     /// called before using this function.
-    void startSparse() {
-      for(NodeIt n(_graph); n != INVALID; ++n) {
+    void startSparse(bool decomposition = true) {
+      int _unmatched_limit = decomposition ? 0 : 1;
+      for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) {
         if ((*_status)[n] == UNMATCHED) {
           (*_blossom_rep)[_blossom_set->insert(n)] = n;
           _tree_set->insert(n);
           (*_status)[n] = EVEN;
+          --_unmatched;
           processSparse(n);
         }
@@ -518 +531 @@
     ///
     /// This function runs Edmonds' algorithm with a heuristic of postponing
-    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
+    /// shrinks, therefore resulting in a faster algorithm for dense graphs.  If
+    /// the \c decomposition parameter is set to false, then the Gallai-Edmonds
+    /// decomposition is not computed.
     ///
     /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
     /// called before using this function.
-    void startDense() {
-      for(NodeIt n(_graph); n != INVALID; ++n) {
+    void startDense(bool decomposition = true) {
+      int _unmatched_limit = decomposition ? 0 : 1;
+      for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) {
         if ((*_status)[n] == UNMATCHED) {
           (*_blossom_rep)[_blossom_set->insert(n)] = n;
           _tree_set->insert(n);
           (*_status)[n] = EVEN;
+          --_unmatched;
           processDense(n);
         }
@@ -537 +554 @@
     ///
     /// This function runs Edmonds' algorithm. An additional heuristic of
-    /// postponing shrinks is used for relatively dense graphs
-    /// (for which <tt>m>=2*n</tt> holds).
-    void run() {
+    /// postponing shrinks is used for relatively dense graphs (for which
+    /// <tt>m>=2*n</tt> holds). If the \c decomposition parameter is set to
+    /// false, then the Gallai-Edmonds decomposition is not computed. In some
+    /// cases, this can speed up the algorithm significantly, especially when a
+    /// maximum matching is computed in a dense graph with odd number of nodes.
+    void run(bool decomposition = true) {
       if (countEdges(_graph) < 2 * countNodes(_graph)) {
         greedyInit();
-        startSparse();
+        startSparse(decomposition);
       } else {
         init();
-        startDense();
+        startDense(decomposition);
       }
     }