1.1 --- a/lemon/matching.h Sat Feb 17 23:44:32 2018 +0100
1.2 +++ b/lemon/matching.h Sat Oct 27 13:00:48 2018 +0200
1.3 @@ -115,7 +115,7 @@
1.4 NodeQueue _node_queue;
1.5 int _process, _postpone, _last;
1.6
1.7 - int _node_num;
1.8 + int _node_num, _unmatched;
1.9
1.10 private:
1.11
1.12 @@ -179,6 +179,7 @@
1.13 extendOnArc(a);
1.14 } else if ((*_status)[v] == UNMATCHED) {
1.15 augmentOnArc(a);
1.16 + --_unmatched;
1.17 return;
1.18 }
1.19 }
1.20 @@ -204,6 +205,7 @@
1.21 extendOnArc(b);
1.22 } else if ((*_status)[x] == UNMATCHED) {
1.23 augmentOnArc(b);
1.24 + --_unmatched;
1.25 return;
1.26 }
1.27 }
1.28 @@ -228,6 +230,7 @@
1.29 extendOnArc(a);
1.30 } else if ((*_status)[v] == UNMATCHED) {
1.31 augmentOnArc(a);
1.32 + --_unmatched;
1.33 return;
1.34 }
1.35 }
1.36 @@ -437,6 +440,7 @@
1.37 (*_matching)[n] = INVALID;
1.38 (*_status)[n] = UNMATCHED;
1.39 }
1.40 + _unmatched = _node_num;
1.41 }
1.42
1.43 /// \brief Find an initial matching in a greedy way.
1.44 @@ -448,6 +452,7 @@
1.45 (*_matching)[n] = INVALID;
1.46 (*_status)[n] = UNMATCHED;
1.47 }
1.48 + _unmatched = _node_num;
1.49 for (NodeIt n(_graph); n != INVALID; ++n) {
1.50 if ((*_matching)[n] == INVALID) {
1.51 for (OutArcIt a(_graph, n); a != INVALID ; ++a) {
1.52 @@ -457,6 +462,7 @@
1.53 (*_status)[n] = MATCHED;
1.54 (*_matching)[v] = _graph.oppositeArc(a);
1.55 (*_status)[v] = MATCHED;
1.56 + _unmatched -= 2;
1.57 break;
1.58 }
1.59 }
1.60 @@ -479,6 +485,7 @@
1.61 (*_matching)[n] = INVALID;
1.62 (*_status)[n] = UNMATCHED;
1.63 }
1.64 + _unmatched = _node_num;
1.65 for(EdgeIt e(_graph); e!=INVALID; ++e) {
1.66 if (matching[e]) {
1.67
1.68 @@ -491,6 +498,8 @@
1.69 if ((*_matching)[v] != INVALID) return false;
1.70 (*_matching)[v] = _graph.direct(e, false);
1.71 (*_status)[v] = MATCHED;
1.72 +
1.73 + _unmatched -= 2;
1.74 }
1.75 }
1.76 return true;
1.77 @@ -498,16 +507,20 @@
1.78
1.79 /// \brief Start Edmonds' algorithm
1.80 ///
1.81 - /// This function runs the original Edmonds' algorithm.
1.82 + /// This function runs the original Edmonds' algorithm. If the
1.83 + /// \c decomposition parameter is set to false, then the Gallai-Edmonds
1.84 + /// decomposition is not computed.
1.85 ///
1.86 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
1.87 /// called before using this function.
1.88 - void startSparse() {
1.89 - for(NodeIt n(_graph); n != INVALID; ++n) {
1.90 + void startSparse(bool decomposition = true) {
1.91 + int _unmatched_limit = decomposition ? 0 : 1;
1.92 + for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) {
1.93 if ((*_status)[n] == UNMATCHED) {
1.94 (*_blossom_rep)[_blossom_set->insert(n)] = n;
1.95 _tree_set->insert(n);
1.96 (*_status)[n] = EVEN;
1.97 + --_unmatched;
1.98 processSparse(n);
1.99 }
1.100 }
1.101 @@ -517,16 +530,20 @@
1.102 /// for dense graphs
1.103 ///
1.104 /// This function runs Edmonds' algorithm with a heuristic of postponing
1.105 - /// shrinks, therefore resulting in a faster algorithm for dense graphs.
1.106 + /// shrinks, therefore resulting in a faster algorithm for dense graphs. If
1.107 + /// the \c decomposition parameter is set to false, then the Gallai-Edmonds
1.108 + /// decomposition is not computed.
1.109 ///
1.110 /// \pre \ref init(), \ref greedyInit() or \ref matchingInit() must be
1.111 /// called before using this function.
1.112 - void startDense() {
1.113 - for(NodeIt n(_graph); n != INVALID; ++n) {
1.114 + void startDense(bool decomposition = true) {
1.115 + int _unmatched_limit = decomposition ? 0 : 1;
1.116 + for(NodeIt n(_graph); _unmatched > _unmatched_limit; ++n) {
1.117 if ((*_status)[n] == UNMATCHED) {
1.118 (*_blossom_rep)[_blossom_set->insert(n)] = n;
1.119 _tree_set->insert(n);
1.120 (*_status)[n] = EVEN;
1.121 + --_unmatched;
1.122 processDense(n);
1.123 }
1.124 }
1.125 @@ -536,15 +553,18 @@
1.126 /// \brief Run Edmonds' algorithm
1.127 ///
1.128 /// This function runs Edmonds' algorithm. An additional heuristic of
1.129 - /// postponing shrinks is used for relatively dense graphs
1.130 - /// (for which <tt>m>=2*n</tt> holds).
1.131 - void run() {
1.132 + /// postponing shrinks is used for relatively dense graphs (for which
1.133 + /// <tt>m>=2*n</tt> holds). If the \c decomposition parameter is set to
1.134 + /// false, then the Gallai-Edmonds decomposition is not computed. In some
1.135 + /// cases, this can speed up the algorithm significantly, especially when a
1.136 + /// maximum matching is computed in a dense graph with odd number of nodes.
1.137 + void run(bool decomposition = true) {
1.138 if (countEdges(_graph) < 2 * countNodes(_graph)) {
1.139 greedyInit();
1.140 - startSparse();
1.141 + startSparse(decomposition);
1.142 } else {
1.143 init();
1.144 - startDense();
1.145 + startDense(decomposition);
1.146 }
1.147 }
1.148
2.1 --- a/test/matching_test.cc Sat Feb 17 23:44:32 2018 +0100
2.2 +++ b/test/matching_test.cc Sat Oct 27 13:00:48 2018 +0200
2.3 @@ -134,6 +134,9 @@
2.4 mat_test.startSparse();
2.5 mat_test.startDense();
2.6 mat_test.run();
2.7 + mat_test.startSparse(false);
2.8 + mat_test.startDense(false);
2.9 + mat_test.run(false);
2.10
2.11 const_mat_test.matchingSize();
2.12 const_mat_test.matching(e);
2.13 @@ -402,15 +405,83 @@
2.14 graphReader(graph, lgfs).
2.15 edgeMap("weight", weight).run();
2.16
2.17 + int size;
2.18 bool perfect;
2.19 {
2.20 MaxMatching<SmartGraph> mm(graph);
2.21 mm.run();
2.22 checkMatching(graph, mm);
2.23 + size = mm.matchingSize();
2.24 perfect = 2 * mm.matchingSize() == countNodes(graph);
2.25 }
2.26
2.27 {
2.28 + MaxMatching<SmartGraph> mm(graph);
2.29 + mm.init();
2.30 + mm.startSparse();
2.31 + checkMatching(graph, mm);
2.32 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.33 + }
2.34 +
2.35 + {
2.36 + MaxMatching<SmartGraph> mm(graph);
2.37 + mm.init();
2.38 + mm.startDense();
2.39 + checkMatching(graph, mm);
2.40 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.41 + }
2.42 +
2.43 + {
2.44 + MaxMatching<SmartGraph> mm(graph);
2.45 + mm.greedyInit();
2.46 + mm.startSparse();
2.47 + checkMatching(graph, mm);
2.48 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.49 + }
2.50 +
2.51 + {
2.52 + MaxMatching<SmartGraph> mm(graph);
2.53 + mm.greedyInit();
2.54 + mm.startDense();
2.55 + checkMatching(graph, mm);
2.56 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.57 + }
2.58 +
2.59 + {
2.60 + MaxMatching<SmartGraph> mm(graph);
2.61 + mm.run(false);
2.62 + check(size == mm.matchingSize(), "Inconsistent max cardinality matching");
2.63 + }
2.64 +
2.65 + {
2.66 + MaxMatching<SmartGraph> mm(graph);
2.67 + mm.init();
2.68 + mm.startSparse(false);
2.69 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.70 + }
2.71 +
2.72 + {
2.73 + MaxMatching<SmartGraph> mm(graph);
2.74 + mm.init();
2.75 + mm.startDense(false);
2.76 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.77 + }
2.78 +
2.79 + {
2.80 + MaxMatching<SmartGraph> mm(graph);
2.81 + mm.greedyInit();
2.82 + mm.startSparse(false);
2.83 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.84 + }
2.85 +
2.86 + {
2.87 + MaxMatching<SmartGraph> mm(graph);
2.88 + mm.greedyInit();
2.89 + mm.startDense(false);
2.90 + check(size == mm.matchingSize(), "Inconsistent matching size");
2.91 + }
2.92 +
2.93 + {
2.94 MaxWeightedMatching<SmartGraph> mwm(graph, weight);
2.95 mwm.run();
2.96 checkWeightedMatching(graph, weight, mwm);