lemon-1.3: comparison lemon/matching.h

equal deleted inserted replaced

-:3c0fd91544ab
+:4fa2e7cacf26
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */
-#ifndef LEMON_MAX_MATCHING_H
+#ifndef LEMON_MATCHING_H
-#define LEMON_MAX_MATCHING_H
+#define LEMON_MATCHING_H
 #include <vector>
 #include <queue>
 #include <set>
 #include <limits>
 ///
 /// \brief Maximum cardinality matching in general graphs
 ///
 /// This class implements Edmonds' alternating forest matching algorithm
 /// for finding a maximum cardinality matching in a general undirected graph.
 /// It can be started from an arbitrary initial matching
 /// (the default is the empty one).
 ///
 /// The dual solution of the problem is a map of the nodes to
 /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D),
 /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds
 typedef typename Graph::template NodeMap<typename Graph::Arc>
 MatchingMap;
 ///\brief Status constants for Gallai-Edmonds decomposition.
 ///
 ///These constants are used for indicating the Gallai-Edmonds
 ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
 ///induce a subgraph with factor-critical components, the nodes with
 ///status \c ODD (or \c A) form the canonical barrier, and the nodes
 ///with status \c MATCHED (or \c C) induce a subgraph having a
 ///perfect matching.
 enum Status {
 EVEN = 1,       ///< = 1. (\c D is an alias for \c EVEN.)
 D = 1,
 MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.)
 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.
 ///
 }
 /// \brief Run Edmonds' algorithm
 ///
 /// 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() {
 if (countEdges(_graph) < 2 * countNodes(_graph)) {
 greedyInit();
 startSparse();
 /// @{
 /// \brief Return the size (cardinality) of the matching.
 ///
 /// This function returns the size (cardinality) of the current matching.
 /// After run() it returns the size of the maximum matching in the graph.
 int matchingSize() const {
 int size = 0;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 return size / 2;
 }
 /// \brief Return \c true if the given edge is in the matching.
 ///
 /// This function returns \c true if the given edge is in the current
 /// matching.
 bool matching(const Edge& edge) const {
 return edge == (*_matching)[_graph.u(edge)];
 }
 /// \brief Return the matching arc (or edge) incident to the given node.
 ///
 /// This function returns the matching arc (or edge) incident to the
 /// given node in the current matching or \c INVALID if the node is
 /// not covered by the matching.
 Arc matching(const Node& n) const {
 return (*_matching)[n];
 }
 return *_matching;
 }
 /// \brief Return the mate of the given node.
 ///
 /// This function returns the mate of the given node in the current
 /// matching or \c INVALID if the node is not covered by the matching.
 Node mate(const Node& n) const {
 return (*_matching)[n] != INVALID ?
 _graph.target((*_matching)[n]) : INVALID;
 }
 /// @}
 /// \name Dual Solution
 /// Functions to get the dual solution, i.e. the Gallai-Edmonds
 /// decomposition.
 /// @{
 /// \brief Return the status of the given node in the Edmonds-Gallai
 /// This class provides an efficient implementation of Edmond's
 /// maximum weighted matching algorithm. The implementation is based
 /// on extensive use of priority queues and provides
 /// \f$O(nm\log n)\f$ time complexity.
 ///
 /// The maximum weighted matching problem is to find a subset of the
 /// edges in an undirected graph with maximum overall weight for which
 /// each node has at most one incident edge.
 /// It can be formulated with the following linear program.
 /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
 \quad \forall B\in\mathcal{O}\f] */
 /// \f[y_u \ge 0 \quad \forall u \in V\f]
 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 \frac{\vert B \vert - 1}{2}z_B\f] */
 ///
 /// The algorithm can be executed with the run() function.
 /// After it the matching (the primal solution) and the dual solution
 /// can be obtained using the query functions and the
 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
 /// which is able to iterate on the nodes of a blossom.
 /// If the value type is integer, then the dual solution is multiplied
 /// by \ref MaxWeightedMatching::dualScale "4".
 ///
 /// \tparam GR The undirected graph type the algorithm runs on.
 /// \tparam WM The type edge weight map. The default type is
 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename WM>
 #else
 template <typename GR,
 int _blossom_num;
 typedef RangeMap<int> IntIntMap;
 enum Status {
-EVEN = -1, MATCHED = 0, ODD = 1, UNMATCHED = -2
+EVEN = -1, MATCHED = 0, ODD = 1
 };
 typedef HeapUnionFind<Value, IntNodeMap> BlossomSet;
 struct BlossomData {
 int tree;
 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
 }
 }
 void destroyStructures() {
-_node_num = countNodes(_graph);
-_blossom_num = _node_num * 3 / 2;
 if (_matching) {
 delete _matching;
 }
 if (_node_potential) {
 delete _node_potential;
 dualScale * _weight[e];
 if ((*_blossom_data)[vb].status == EVEN) {
 if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 _delta3->push(e, rw / 2);
-}
-} else if ((*_blossom_data)[vb].status == UNMATCHED) {
-if (_delta3->state(e) != _delta3->IN_HEAP) {
-_delta3->push(e, rw);
 }
 } else {
 typename std::map<int, Arc>::iterator it =
 (*_node_data)[vi].heap_index.find(tree);
 if ((*_blossom_data)[vb].status == MATCHED) {
 if (_delta2->state(vb) != _delta2->IN_HEAP) {
 _delta2->push(vb, _blossom_set->classPrio(vb) -
 (*_blossom_data)[vb].offset);
 } else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) -
-(*_blossom_data)[vb].offset){
+(*_blossom_data)[vb].offset) {
 _delta2->decrease(vb, _blossom_set->classPrio(vb) -
 (*_blossom_data)[vb].offset);
 }
 }
 }
 _delta2->erase(blossom);
 }
 (*_blossom_data)[blossom].offset += _delta_sum;
 if (!_blossom_set->trivial(blossom)) {
 _delta4->push(blossom, (*_blossom_data)[blossom].pot / 2 +
 (*_blossom_data)[blossom].offset);
 }
 }
 void evenToMatched(int blossom, int tree) {
 if (!_blossom_set->trivial(blossom)) {
 _delta2->decrease(blossom, _blossom_set->classPrio(blossom) -
 (*_blossom_data)[blossom].offset);
 }
 }
 }
-} else if ((*_blossom_data)[vb].status == UNMATCHED) {
-if (_delta3->state(e) == _delta3->IN_HEAP) {
-_delta3->erase(e);
-}
 } else {
 typename std::map<int, Arc>::iterator it =
 (*_node_data)[vi].heap_index.find(tree);
 (*_blossom_data)[blossom].offset -= _delta_sum;
 if (_blossom_set->classPrio(blossom) !=
 std::numeric_limits<Value>::max()) {
 _delta2->push(blossom, _blossom_set->classPrio(blossom) -
 (*_blossom_data)[blossom].offset);
 }
 if (!_blossom_set->trivial(blossom)) {
 _delta4->erase(blossom);
 }
 dualScale * _weight[e];
 if ((*_blossom_data)[vb].status == EVEN) {
 if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 _delta3->push(e, rw / 2);
-}
-} else if ((*_blossom_data)[vb].status == UNMATCHED) {
-if (_delta3->state(e) != _delta3->IN_HEAP) {
-_delta3->push(e, rw);
 }
 } else {
 typename std::map<int, Arc>::iterator it =
 (*_node_data)[vi].heap_index.find(tree);
 }
 }
 (*_blossom_data)[blossom].offset = 0;
 }
-void matchedToUnmatched(int blossom) {
-if (_delta2->state(blossom) == _delta2->IN_HEAP) {
-_delta2->erase(blossom);
-}
-for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
-n != INVALID; ++n) {
-int ni = (*_node_index)[n];
-_blossom_set->increase(n, std::numeric_limits<Value>::max());
-(*_node_data)[ni].heap.clear();
-(*_node_data)[ni].heap_index.clear();
-for (OutArcIt e(_graph, n); e != INVALID; ++e) {
-Node v = _graph.target(e);
-int vb = _blossom_set->find(v);
-int vi = (*_node_index)[v];
-Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
-dualScale * _weight[e];
-if ((*_blossom_data)[vb].status == EVEN) {
-if (_delta3->state(e) != _delta3->IN_HEAP) {
-_delta3->push(e, rw);
-}
-}
-}
-}
-}
-void unmatchedToMatched(int blossom) {
-for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
-n != INVALID; ++n) {
-int ni = (*_node_index)[n];
-for (InArcIt e(_graph, n); e != INVALID; ++e) {
-Node v = _graph.source(e);
-int vb = _blossom_set->find(v);
-int vi = (*_node_index)[v];
-Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
-dualScale * _weight[e];
-if (vb == blossom) {
-if (_delta3->state(e) == _delta3->IN_HEAP) {
-_delta3->erase(e);
-}
-} else if ((*_blossom_data)[vb].status == EVEN) {
-if (_delta3->state(e) == _delta3->IN_HEAP) {
-_delta3->erase(e);
-}
-int vt = _tree_set->find(vb);
-Arc r = _graph.oppositeArc(e);
-typename std::map<int, Arc>::iterator it =
-(*_node_data)[ni].heap_index.find(vt);
-if (it != (*_node_data)[ni].heap_index.end()) {
-if ((*_node_data)[ni].heap[it->second] > rw) {
-(*_node_data)[ni].heap.replace(it->second, r);
-(*_node_data)[ni].heap.decrease(r, rw);
-it->second = r;
-}
-} else {
-(*_node_data)[ni].heap.push(r, rw);
-(*_node_data)[ni].heap_index.insert(std::make_pair(vt, r));
-}
-if ((*_blossom_set)[n] > (*_node_data)[ni].heap.prio()) {
-_blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
-if (_delta2->state(blossom) != _delta2->IN_HEAP) {
-_delta2->push(blossom, _blossom_set->classPrio(blossom) -
-(*_blossom_data)[blossom].offset);
-} else if ((*_delta2)[blossom] > _blossom_set->classPrio(blossom)-
-(*_blossom_data)[blossom].offset){
-_delta2->decrease(blossom, _blossom_set->classPrio(blossom) -
-(*_blossom_data)[blossom].offset);
-}
-}
-} else if ((*_blossom_data)[vb].status == UNMATCHED) {
-if (_delta3->state(e) == _delta3->IN_HEAP) {
-_delta3->erase(e);
-}
-}
-}
-}
-}
 void alternatePath(int even, int tree) {
 int odd;
 evenToMatched(even, tree);
 (*_blossom_data)[even].status = MATCHED;
 int tree = _tree_set->find(blossom);
 alternatePath(blossom, tree);
 destroyTree(tree);
-(*_blossom_data)[blossom].status = UNMATCHED;
 (*_blossom_data)[blossom].base = node;
-matchedToUnmatched(blossom);
+(*_blossom_data)[blossom].next = INVALID;
 }
 void augmentOnEdge(const Edge& edge) {
 int left = _blossom_set->find(_graph.u(edge));
 int right = _blossom_set->find(_graph.v(edge));
-if ((*_blossom_data)[left].status == EVEN) {
+int left_tree = _tree_set->find(left);
-int left_tree = _tree_set->find(left);
+alternatePath(left, left_tree);
-alternatePath(left, left_tree);
+destroyTree(left_tree);
-destroyTree(left_tree);
-} else {
+int right_tree = _tree_set->find(right);
-(*_blossom_data)[left].status = MATCHED;
+alternatePath(right, right_tree);
-unmatchedToMatched(left);
+destroyTree(right_tree);
-}
-if ((*_blossom_data)[right].status == EVEN) {
-int right_tree = _tree_set->find(right);
-alternatePath(right, right_tree);
-destroyTree(right_tree);
-} else {
-(*_blossom_data)[right].status = MATCHED;
-unmatchedToMatched(right);
-}
 (*_blossom_data)[left].next = _graph.direct(edge, true);
 (*_blossom_data)[right].next = _graph.direct(edge, false);
+}
+void augmentOnArc(const Arc& arc) {
+int left = _blossom_set->find(_graph.source(arc));
+int right = _blossom_set->find(_graph.target(arc));
+(*_blossom_data)[left].status = MATCHED;
+int right_tree = _tree_set->find(right);
+alternatePath(right, right_tree);
+destroyTree(right_tree);
+(*_blossom_data)[left].next = arc;
+(*_blossom_data)[right].next = _graph.oppositeArc(arc);
 }
 void extendOnArc(const Arc& arc) {
 int base = _blossom_set->find(_graph.target(arc));
 int tree = _tree_set->find(base);
 (*_blossom_data)[sb].status = ODD;
 matchedToOdd(sb);
 _tree_set->insert(sb, tree);
 (*_blossom_data)[sb].pred = pred;
 (*_blossom_data)[sb].next =
 _graph.oppositeArc((*_blossom_data)[tb].next);
 pred = (*_blossom_data)[ub].next;
 (*_blossom_data)[tb].status = EVEN;
 matchedToEven(tb, tree);
 for (typename BlossomSet::ClassIt c(*_blossom_set); c != INVALID; ++c) {
 blossoms.push_back(c);
 }
 for (int i = 0; i < int(blossoms.size()); ++i) {
-if ((*_blossom_data)[blossoms[i]].status == MATCHED) {
+if ((*_blossom_data)[blossoms[i]].next != INVALID) {
 Value offset = (*_blossom_data)[blossoms[i]].offset;
 (*_blossom_data)[blossoms[i]].pot += 2 * offset;
 for (typename BlossomSet::ItemIt n(*_blossom_set, blossoms[i]);
 n != INVALID; ++n) {
 _delta3->prio() : std::numeric_limits<Value>::max();
 Value d4 = !_delta4->empty() ?
 _delta4->prio() : std::numeric_limits<Value>::max();
-_delta_sum = d1; OpType ot = D1;
+_delta_sum = d3; OpType ot = D3;
+if (d1 < _delta_sum) { _delta_sum = d1; ot = D1; }
 if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
-if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }
 if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
 switch (ot) {
 case D1:
 {
 Node n = _delta1->top();
 break;
 case D2:
 {
 int blossom = _delta2->top();
 Node n = _blossom_set->classTop(blossom);
-Arc e = (*_node_data)[(*_node_index)[n]].heap.top();
+Arc a = (*_node_data)[(*_node_index)[n]].heap.top();
-extendOnArc(e);
+if ((*_blossom_data)[blossom].next == INVALID) {
+augmentOnArc(a);
+--unmatched;
+} else {
+extendOnArc(a);
+}
 }
 break;
 case D3:
 {
 Edge e = _delta3->top();
 int right_blossom = _blossom_set->find(_graph.v(e));
 if (left_blossom == right_blossom) {
 _delta3->pop();
 } else {
-int left_tree;
+int left_tree = _tree_set->find(left_blossom);
-if ((*_blossom_data)[left_blossom].status == EVEN) {
+int right_tree = _tree_set->find(right_blossom);
-left_tree = _tree_set->find(left_blossom);
-} else {
-left_tree = -1;
-++unmatched;
-}
-int right_tree;
-if ((*_blossom_data)[right_blossom].status == EVEN) {
-right_tree = _tree_set->find(right_blossom);
-} else {
-right_tree = -1;
-++unmatched;
-}
 if (left_tree == right_tree) {
 shrinkOnEdge(e, left_tree);
 } else {
 augmentOnEdge(e);
 }
 /// @}
 /// \name Primal Solution
 /// Functions to get the primal solution, i.e. the maximum weighted
 /// matching.\n
 /// Either \ref run() or \ref start() function should be called before
 /// using them.
 /// @{
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 sum += _weight[(*_matching)[n]];
 }
 }
-return sum /= 2;
+return sum / 2;
 }
 /// \brief Return the size (cardinality) of the matching.
 ///
 /// This function returns the size (cardinality) of the found matching.
 return num /= 2;
 }
 /// \brief Return \c true if the given edge is in the matching.
 ///
 /// This function returns \c true if the given edge is in the found
 /// matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 bool matching(const Edge& edge) const {
 return edge == (*_matching)[_graph.u(edge)];
 }
 /// \brief Return the matching arc (or edge) incident to the given node.
 ///
 /// This function returns the matching arc (or edge) incident to the
 /// given node in the found matching or \c INVALID if the node is
 /// not covered by the matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 Arc matching(const Node& node) const {
 return (*_matching)[node];
 return *_matching;
 }
 /// \brief Return the mate of the given node.
 ///
 /// This function returns the mate of the given node in the found
 /// matching or \c INVALID if the node is not covered by the matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 Node mate(const Node& node) const {
 return (*_matching)[node] != INVALID ?
 /// @{
 /// \brief Return the value of the dual solution.
 ///
 /// This function returns the value of the dual solution.
 /// It should be equal to the primal value scaled by \ref dualScale
 /// "dual scale".
 ///
 /// \pre Either run() or start() must be called before using this function.
 Value dualValue() const {
 Value sum = 0;
 return _blossom_potential[k].value;
 }
 /// \brief Iterator for obtaining the nodes of a blossom.
 ///
 /// This class provides an iterator for obtaining the nodes of the
 /// given blossom. It lists a subset of the nodes.
 /// Before using this iterator, you must allocate a
 /// MaxWeightedMatching class and execute it.
 class BlossomIt {
 public:
 /// \brief Constructor.
 ///
 /// Constructor to get the nodes of the given variable.
 ///
 /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
 /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
 /// called before initializing this iterator.
 BlossomIt(const MaxWeightedMatching& algorithm, int variable)
 : _algorithm(&algorithm)
 {
 _index = _algorithm->_blossom_potential[variable].begin;
 /// This class provides an efficient implementation of Edmond's
 /// maximum weighted perfect matching algorithm. The implementation
 /// is based on extensive use of priority queues and provides
 /// \f$O(nm\log n)\f$ time complexity.
 ///
 /// The maximum weighted perfect matching problem is to find a subset of
 /// the edges in an undirected graph with maximum overall weight for which
 /// each node has exactly one incident edge.
 /// It can be formulated with the following linear program.
 /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
 \quad \forall B\in\mathcal{O}\f] */
 w_{uv} \quad \forall uv\in E\f] */
 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 \frac{\vert B \vert - 1}{2}z_B\f] */
 ///
 /// The algorithm can be executed with the run() function.
 /// After it the matching (the primal solution) and the dual solution
 /// can be obtained using the query functions and the
 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
 /// which is able to iterate on the nodes of a blossom.
 /// If the value type is integer, then the dual solution is multiplied
 /// by \ref MaxWeightedMatching::dualScale "4".
 ///
 /// \tparam GR The undirected graph type the algorithm runs on.
 /// \tparam WM The type edge weight map. The default type is
 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
 template <typename GR, typename WM>
 #else
 template <typename GR,
 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
 }
 }
 void destroyStructures() {
-_node_num = countNodes(_graph);
-_blossom_num = _node_num * 3 / 2;
 if (_matching) {
 delete _matching;
 }
 if (_node_potential) {
 delete _node_potential;
 _delta3->prio() : std::numeric_limits<Value>::max();
 Value d4 = !_delta4->empty() ?
 _delta4->prio() : std::numeric_limits<Value>::max();
-_delta_sum = d2; OpType ot = D2;
+_delta_sum = d3; OpType ot = D3;
-if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }
+if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
 if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
 if (_delta_sum == std::numeric_limits<Value>::max()) {
 return false;
 }
 }
 /// @}
 /// \name Primal Solution
 /// Functions to get the primal solution, i.e. the maximum weighted
 /// perfect matching.\n
 /// Either \ref run() or \ref start() function should be called before
 /// using them.
 /// @{
 for (NodeIt n(_graph); n != INVALID; ++n) {
 if ((*_matching)[n] != INVALID) {
 sum += _weight[(*_matching)[n]];
 }
 }
-return sum /= 2;
+return sum / 2;
 }
 /// \brief Return \c true if the given edge is in the matching.
 ///
 /// This function returns \c true if the given edge is in the found
 /// matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 bool matching(const Edge& edge) const {
 return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge;
 }
 /// \brief Return the matching arc (or edge) incident to the given node.
 ///
 /// This function returns the matching arc (or edge) incident to the
 /// given node in the found matching or \c INVALID if the node is
 /// not covered by the matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 Arc matching(const Node& node) const {
 return (*_matching)[node];
 return *_matching;
 }
 /// \brief Return the mate of the given node.
 ///
 /// This function returns the mate of the given node in the found
 /// matching or \c INVALID if the node is not covered by the matching.
 ///
 /// \pre Either run() or start() must be called before using this function.
 Node mate(const Node& node) const {
 return _graph.target((*_matching)[node]);
 /// @{
 /// \brief Return the value of the dual solution.
 ///
 /// This function returns the value of the dual solution.
 /// It should be equal to the primal value scaled by \ref dualScale
 /// "dual scale".
 ///
 /// \pre Either run() or start() must be called before using this function.
 Value dualValue() const {
 Value sum = 0;
 return _blossom_potential[k].value;
 }
 /// \brief Iterator for obtaining the nodes of a blossom.
 ///
 /// This class provides an iterator for obtaining the nodes of the
 /// given blossom. It lists a subset of the nodes.
 /// Before using this iterator, you must allocate a
 /// MaxWeightedPerfectMatching class and execute it.
 class BlossomIt {
 public:
 /// \brief Constructor.
 ///
 /// Constructor to get the nodes of the given variable.
 ///
 /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
 /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
 /// must be called before initializing this iterator.
 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
 : _algorithm(&algorithm)
 {
 _index = _algorithm->_blossom_potential[variable].begin;
 };
 } //END OF NAMESPACE LEMON
-#endif //LEMON_MAX_MATCHING_H
+#endif //LEMON_MATCHING_H

changeset 868	0513ccfea967
parent 651	3adf5e2d1e62
child 870	61120524af27