lemon-main: comparison lemon/matching.h

equal deleted inserted replaced

-:eee9d14047cc
+:e050331efcec
 TreeSet* _tree_set;
 NodeQueue _node_queue;
 int _process, _postpone, _last;
-int _node_num;
+int _node_num, _unmatched;
 private:
 void createStructures() {
 _node_num = countNodes(_graph);
 Node v = _graph.target(a);
 if ((*_status)[v] == MATCHED) {
 extendOnArc(a);
 } else if ((*_status)[v] == UNMATCHED) {
 augmentOnArc(a);
+--_unmatched;
 return;
 }
 }
 }
 Node x = _graph.target(b);
 if ((*_status)[x] == MATCHED) {
 extendOnArc(b);
 } else if ((*_status)[x] == UNMATCHED) {
 augmentOnArc(b);
+--_unmatched;
 return;
 }
 }
 }
 }
 }
 } else if ((*_status)[v] == MATCHED) {
 extendOnArc(a);
 } else if ((*_status)[v] == UNMATCHED) {
 augmentOnArc(a);
+--_unmatched;
 return;
 }
 }
 }
 }
 createStructures();
 for(NodeIt n(_graph); n != INVALID; ++n) {
 (*_matching)[n] = INVALID;
 (*_status)[n] = UNMATCHED;
 }
+_unmatched = _node_num;
 }
 /// \brief Find an initial matching in a greedy way.
 ///
 /// This function finds an initial matching in a greedy way.
 createStructures();
 for (NodeIt n(_graph); n != INVALID; ++n) {
 (*_matching)[n] = INVALID;
 (*_status)[n] = UNMATCHED;
 }
+_unmatched = _node_num;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] == INVALID) {
 for (OutArcIt a(_graph, n); a != INVALID ; ++a) {
 Node v = _graph.target(a);
 if ((*_matching)[v] == INVALID && v != n) {
 (*_matching)[n] = a;
 (*_status)[n] = MATCHED;
 (*_matching)[v] = _graph.oppositeArc(a);
 (*_status)[v] = MATCHED;
+_unmatched -= 2;
 break;
 }
 }
 }
 }
 for (NodeIt n(_graph); n != INVALID; ++n) {
 (*_matching)[n] = INVALID;
 (*_status)[n] = UNMATCHED;
 }
+_unmatched = _node_num;
 for(EdgeIt e(_graph); e!=INVALID; ++e) {
 if (matching[e]) {
 Node u = _graph.u(e);
 if ((*_matching)[u] != INVALID) return false;
 Node v = _graph.v(e);
 if ((*_matching)[v] != INVALID) return false;
 (*_matching)[v] = _graph.direct(e, false);
 (*_status)[v] = MATCHED;
+_unmatched -= 2;
 }
 }
 return true;
 }
 /// \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() {
+void startSparse(bool decomposition = true) {
-for(NodeIt n(_graph); n != INVALID; ++n) {
+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);
 }
 }
 }
 /// \brief Start Edmonds' algorithm with a heuristic improvement
 /// for dense graphs
 ///
 /// 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() {
+void startDense(bool decomposition = true) {
-for(NodeIt n(_graph); n != INVALID; ++n) {
+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);
 }
 }
 }
 /// \brief Run Edmonds' algorithm
 ///
 /// This function runs Edmonds' algorithm. An additional heuristic of
-/// postponing shrinks is used for relatively dense graphs
+/// postponing shrinks is used for relatively dense graphs (for which
-/// (for which <tt>m>=2*n</tt> holds).
+/// <tt>m>=2*n</tt> holds). If the \c decomposition parameter is set to
-void run() {
+/// 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);
 }
 }
 /// @}

changeset 1207	eba5aa390aca
parent 1092	dceba191c00d
child 1208	c6aa2cc1af04