Changeset 1203:8c567e298d7f in lemon-main

Timestamp:

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

Author:

Balazs Dezso <deba@…>

Branch:

default

Children:

1204:736a341e604b, 1205:57abff252556, 1208:c6aa2cc1af04

Phase:

public

Message:

Paremeter to stop matching calculation when only single node is unmatched

Files:

• lemon/matching.h (modified) (12 diffs)
• test/matching_test.cc (modified) (3 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);
       }
     }

test/matching_test.cc

@@ -135 +135 @@
   mat_test.startDense();
   mat_test.run();
+  mat_test.startSparse(false);
+  mat_test.startDense(false);
+  mat_test.run(false);
 
   const_mat_test.matchingSize();
@@ -403 +406 @@
       edgeMap("weight", weight).run();
 
+    int size;
     bool perfect;
     {
@@ -408 +412 @@
       mm.run();
       checkMatching(graph, mm);
+      size = mm.matchingSize();
       perfect = 2 * mm.matchingSize() == countNodes(graph);
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.init();
+      mm.startSparse();
+      checkMatching(graph, mm);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.init();
+      mm.startDense();
+      checkMatching(graph, mm);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.greedyInit();
+      mm.startSparse();
+      checkMatching(graph, mm);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.greedyInit();
+      mm.startDense();
+      checkMatching(graph, mm);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.run(false);
+      check(size == mm.matchingSize(), "Inconsistent max cardinality matching");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.init();
+      mm.startSparse(false);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.init();
+      mm.startDense(false);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.greedyInit();
+      mm.startSparse(false);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
+    }
+
+    {
+      MaxMatching<SmartGraph> mm(graph);
+      mm.greedyInit();
+      mm.startDense(false);
+      check(size == mm.matchingSize(), "Inconsistent matching size");
     }