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