35 |
35 |
36 namespace lemon { |
36 namespace lemon { |
37 |
37 |
38 /// \ingroup matching |
38 /// \ingroup matching |
39 /// |
39 /// |
40 /// \brief Edmonds' alternating forest maximum matching algorithm. |
40 /// \brief Maximum cardinality matching in general graphs |
41 /// |
41 /// |
42 /// This class implements Edmonds' alternating forest matching |
42 /// This class implements Edmonds' alternating forest matching algorithm |
43 /// algorithm. The algorithm can be started from an arbitrary initial |
43 /// for finding a maximum cardinality matching in a general graph. |
44 /// matching (the default is the empty one) |
44 /// It can be started from an arbitrary initial matching |
|
45 /// (the default is the empty one). |
45 /// |
46 /// |
46 /// The dual solution of the problem is a map of the nodes to |
47 /// The dual solution of the problem is a map of the nodes to |
47 /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c |
48 /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), |
48 /// MATCHED/C showing the Gallai-Edmonds decomposition of the |
49 /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds |
49 /// graph. The nodes in \c EVEN/D induce a graph with |
50 /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph |
50 /// factor-critical components, the nodes in \c ODD/A form the |
51 /// with factor-critical components, the nodes in \c ODD/A form the |
51 /// barrier, and the nodes in \c MATCHED/C induce a graph having a |
52 /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having |
52 /// perfect matching. The number of the factor-critical components |
53 /// a perfect matching. The number of the factor-critical components |
53 /// minus the number of barrier nodes is a lower bound on the |
54 /// minus the number of barrier nodes is a lower bound on the |
54 /// unmatched nodes, and the matching is optimal if and only if this bound is |
55 /// unmatched nodes, and the matching is optimal if and only if this bound is |
55 /// tight. This decomposition can be attained by calling \c |
56 /// tight. This decomposition can be obtained by calling \c |
56 /// decomposition() after running the algorithm. |
57 /// decomposition() after running the algorithm. |
57 /// |
58 /// |
58 /// \param GR The graph type the algorithm runs on. |
59 /// \tparam GR The graph type the algorithm runs on. |
59 template <typename GR> |
60 template <typename GR> |
60 class MaxMatching { |
61 class MaxMatching { |
61 public: |
62 public: |
62 |
63 |
|
64 /// The graph type of the algorithm |
63 typedef GR Graph; |
65 typedef GR Graph; |
64 typedef typename Graph::template NodeMap<typename Graph::Arc> |
66 typedef typename Graph::template NodeMap<typename Graph::Arc> |
65 MatchingMap; |
67 MatchingMap; |
66 |
68 |
67 ///\brief Indicates the Gallai-Edmonds decomposition of the graph. |
69 ///\brief Status constants for Gallai-Edmonds decomposition. |
68 /// |
70 /// |
69 ///Indicates the Gallai-Edmonds decomposition of the graph. The |
71 ///These constants are used for indicating the Gallai-Edmonds |
70 ///nodes with Status \c EVEN/D induce a graph with factor-critical |
72 ///decomposition of a graph. The nodes with status \c EVEN (or \c D) |
71 ///components, the nodes in \c ODD/A form the canonical barrier, |
73 ///induce a subgraph with factor-critical components, the nodes with |
72 ///and the nodes in \c MATCHED/C induce a graph having a perfect |
74 ///status \c ODD (or \c A) form the canonical barrier, and the nodes |
73 ///matching. |
75 ///with status \c MATCHED (or \c C) induce a subgraph having a |
|
76 ///perfect matching. |
74 enum Status { |
77 enum Status { |
75 EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2 |
78 EVEN = 1, ///< = 1. (\c D is an alias for \c EVEN.) |
|
79 D = 1, |
|
80 MATCHED = 0, ///< = 0. (\c C is an alias for \c MATCHED.) |
|
81 C = 0, |
|
82 ODD = -1, ///< = -1. (\c A is an alias for \c ODD.) |
|
83 A = -1, |
|
84 UNMATCHED = -2 ///< = -2. |
76 }; |
85 }; |
77 |
86 |
78 typedef typename Graph::template NodeMap<Status> StatusMap; |
87 typedef typename Graph::template NodeMap<Status> StatusMap; |
79 |
88 |
80 private: |
89 private: |
406 |
413 |
407 ~MaxMatching() { |
414 ~MaxMatching() { |
408 destroyStructures(); |
415 destroyStructures(); |
409 } |
416 } |
410 |
417 |
411 /// \name Execution control |
418 /// \name Execution Control |
412 /// The simplest way to execute the algorithm is to use the |
419 /// The simplest way to execute the algorithm is to use the |
413 /// \c run() member function. |
420 /// \c run() member function.\n |
414 /// \n |
421 /// If you need better control on the execution, you have to call |
415 |
422 /// one of the functions \ref init(), \ref greedyInit() or |
416 /// If you need better control on the execution, you must call |
423 /// \ref matchingInit() first, then you can start the algorithm with |
417 /// \ref init(), \ref greedyInit() or \ref matchingInit() |
424 /// \ref startSparse() or \ref startDense(). |
418 /// functions first, then you can start the algorithm with the \ref |
|
419 /// startSparse() or startDense() functions. |
|
420 |
425 |
421 ///@{ |
426 ///@{ |
422 |
427 |
423 /// \brief Sets the actual matching to the empty matching. |
428 /// \brief Set the initial matching to the empty matching. |
424 /// |
429 /// |
425 /// Sets the actual matching to the empty matching. |
430 /// This function sets the initial matching to the empty matching. |
426 /// |
|
427 void init() { |
431 void init() { |
428 createStructures(); |
432 createStructures(); |
429 for(NodeIt n(_graph); n != INVALID; ++n) { |
433 for(NodeIt n(_graph); n != INVALID; ++n) { |
430 (*_matching)[n] = INVALID; |
434 (*_matching)[n] = INVALID; |
431 (*_status)[n] = UNMATCHED; |
435 (*_status)[n] = UNMATCHED; |
432 } |
436 } |
433 } |
437 } |
434 |
438 |
435 ///\brief Finds an initial matching in a greedy way |
439 /// \brief Find an initial matching in a greedy way. |
436 /// |
440 /// |
437 ///It finds an initial matching in a greedy way. |
441 /// This function finds an initial matching in a greedy way. |
438 void greedyInit() { |
442 void greedyInit() { |
439 createStructures(); |
443 createStructures(); |
440 for (NodeIt n(_graph); n != INVALID; ++n) { |
444 for (NodeIt n(_graph); n != INVALID; ++n) { |
441 (*_matching)[n] = INVALID; |
445 (*_matching)[n] = INVALID; |
442 (*_status)[n] = UNMATCHED; |
446 (*_status)[n] = UNMATCHED; |
501 processSparse(n); |
508 processSparse(n); |
502 } |
509 } |
503 } |
510 } |
504 } |
511 } |
505 |
512 |
506 /// \brief Starts Edmonds' algorithm. |
513 /// \brief Start Edmonds' algorithm with a heuristic improvement |
507 /// |
514 /// for dense graphs |
508 /// It runs Edmonds' algorithm with a heuristic of postponing |
515 /// |
|
516 /// This function runs Edmonds' algorithm with a heuristic of postponing |
509 /// shrinks, therefore resulting in a faster algorithm for dense graphs. |
517 /// shrinks, therefore resulting in a faster algorithm for dense graphs. |
|
518 /// |
|
519 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be |
|
520 /// called before using this function. |
510 void startDense() { |
521 void startDense() { |
511 for(NodeIt n(_graph); n != INVALID; ++n) { |
522 for(NodeIt n(_graph); n != INVALID; ++n) { |
512 if ((*_status)[n] == UNMATCHED) { |
523 if ((*_status)[n] == UNMATCHED) { |
513 (*_blossom_rep)[_blossom_set->insert(n)] = n; |
524 (*_blossom_rep)[_blossom_set->insert(n)] = n; |
514 _tree_set->insert(n); |
525 _tree_set->insert(n); |
534 } |
545 } |
535 } |
546 } |
536 |
547 |
537 /// @} |
548 /// @} |
538 |
549 |
539 /// \name Primal solution |
550 /// \name Primal Solution |
540 /// Functions to get the primal solution, ie. the matching. |
551 /// Functions to get the primal solution, i.e. the maximum matching. |
541 |
552 |
542 /// @{ |
553 /// @{ |
543 |
554 |
544 ///\brief Returns the size of the current matching. |
555 /// \brief Return the size (cardinality) of the matching. |
545 /// |
556 /// |
546 ///Returns the size of the current matching. After \ref |
557 /// This function returns the size (cardinality) of the current matching. |
547 ///run() it returns the size of the maximum matching in the graph. |
558 /// After run() it returns the size of the maximum matching in the graph. |
548 int matchingSize() const { |
559 int matchingSize() const { |
549 int size = 0; |
560 int size = 0; |
550 for (NodeIt n(_graph); n != INVALID; ++n) { |
561 for (NodeIt n(_graph); n != INVALID; ++n) { |
551 if ((*_matching)[n] != INVALID) { |
562 if ((*_matching)[n] != INVALID) { |
552 ++size; |
563 ++size; |
553 } |
564 } |
554 } |
565 } |
555 return size / 2; |
566 return size / 2; |
556 } |
567 } |
557 |
568 |
558 /// \brief Returns true when the edge is in the matching. |
569 /// \brief Return \c true if the given edge is in the matching. |
559 /// |
570 /// |
560 /// Returns true when the edge is in the matching. |
571 /// This function returns \c true if the given edge is in the current |
|
572 /// matching. |
561 bool matching(const Edge& edge) const { |
573 bool matching(const Edge& edge) const { |
562 return edge == (*_matching)[_graph.u(edge)]; |
574 return edge == (*_matching)[_graph.u(edge)]; |
563 } |
575 } |
564 |
576 |
565 /// \brief Returns the matching edge incident to the given node. |
577 /// \brief Return the matching arc (or edge) incident to the given node. |
566 /// |
578 /// |
567 /// Returns the matching edge of a \c node in the actual matching or |
579 /// This function returns the matching arc (or edge) incident to the |
568 /// INVALID if the \c node is not covered by the actual matching. |
580 /// given node in the current matching or \c INVALID if the node is |
|
581 /// not covered by the matching. |
569 Arc matching(const Node& n) const { |
582 Arc matching(const Node& n) const { |
570 return (*_matching)[n]; |
583 return (*_matching)[n]; |
571 } |
584 } |
572 |
585 |
573 ///\brief Returns the mate of a node in the actual matching. |
586 /// \brief Return the mate of the given node. |
574 /// |
587 /// |
575 ///Returns the mate of a \c node in the actual matching or |
588 /// This function returns the mate of the given node in the current |
576 ///INVALID if the \c node is not covered by the actual matching. |
589 /// matching or \c INVALID if the node is not covered by the matching. |
577 Node mate(const Node& n) const { |
590 Node mate(const Node& n) const { |
578 return (*_matching)[n] != INVALID ? |
591 return (*_matching)[n] != INVALID ? |
579 _graph.target((*_matching)[n]) : INVALID; |
592 _graph.target((*_matching)[n]) : INVALID; |
580 } |
593 } |
581 |
594 |
582 /// @} |
595 /// @} |
583 |
596 |
584 /// \name Dual solution |
597 /// \name Dual Solution |
585 /// Functions to get the dual solution, ie. the decomposition. |
598 /// Functions to get the dual solution, i.e. the Gallai-Edmonds |
|
599 /// decomposition. |
586 |
600 |
587 /// @{ |
601 /// @{ |
588 |
602 |
589 /// \brief Returns the class of the node in the Edmonds-Gallai |
603 /// \brief Return the status of the given node in the Edmonds-Gallai |
590 /// decomposition. |
604 /// decomposition. |
591 /// |
605 /// |
592 /// Returns the class of the node in the Edmonds-Gallai |
606 /// This function returns the \ref Status "status" of the given node |
593 /// decomposition. |
607 /// in the Edmonds-Gallai decomposition. |
594 Status decomposition(const Node& n) const { |
608 Status decomposition(const Node& n) const { |
595 return (*_status)[n]; |
609 return (*_status)[n]; |
596 } |
610 } |
597 |
611 |
598 /// \brief Returns true when the node is in the barrier. |
612 /// \brief Return \c true if the given node is in the barrier. |
599 /// |
613 /// |
600 /// Returns true when the node is in the barrier. |
614 /// This function returns \c true if the given node is in the barrier. |
601 bool barrier(const Node& n) const { |
615 bool barrier(const Node& n) const { |
602 return (*_status)[n] == ODD; |
616 return (*_status)[n] == ODD; |
603 } |
617 } |
604 |
618 |
605 /// @} |
619 /// @} |
613 /// This class provides an efficient implementation of Edmond's |
627 /// This class provides an efficient implementation of Edmond's |
614 /// maximum weighted matching algorithm. The implementation is based |
628 /// maximum weighted matching algorithm. The implementation is based |
615 /// on extensive use of priority queues and provides |
629 /// on extensive use of priority queues and provides |
616 /// \f$O(nm\log n)\f$ time complexity. |
630 /// \f$O(nm\log n)\f$ time complexity. |
617 /// |
631 /// |
618 /// The maximum weighted matching problem is to find undirected |
632 /// The maximum weighted matching problem is to find a subset of the |
619 /// edges in the graph with maximum overall weight and no two of |
633 /// edges in an undirected graph with maximum overall weight for which |
620 /// them shares their ends. The problem can be formulated with the |
634 /// each node has at most one incident edge. |
621 /// following linear program. |
635 /// It can be formulated with the following linear program. |
622 /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f] |
636 /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f] |
623 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} |
637 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} |
624 \quad \forall B\in\mathcal{O}\f] */ |
638 \quad \forall B\in\mathcal{O}\f] */ |
625 /// \f[x_e \ge 0\quad \forall e\in E\f] |
639 /// \f[x_e \ge 0\quad \forall e\in E\f] |
626 /// \f[\max \sum_{e\in E}x_ew_e\f] |
640 /// \f[\max \sum_{e\in E}x_ew_e\f] |
630 /// subsets of the nodes. |
644 /// subsets of the nodes. |
631 /// |
645 /// |
632 /// The algorithm calculates an optimal matching and a proof of the |
646 /// The algorithm calculates an optimal matching and a proof of the |
633 /// optimality. The solution of the dual problem can be used to check |
647 /// optimality. The solution of the dual problem can be used to check |
634 /// the result of the algorithm. The dual linear problem is the |
648 /// the result of the algorithm. The dual linear problem is the |
|
649 /// following. |
635 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)} |
650 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)} |
636 z_B \ge w_{uv} \quad \forall uv\in E\f] */ |
651 z_B \ge w_{uv} \quad \forall uv\in E\f] */ |
637 /// \f[y_u \ge 0 \quad \forall u \in V\f] |
652 /// \f[y_u \ge 0 \quad \forall u \in V\f] |
638 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f] |
653 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f] |
639 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} |
654 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} |
640 \frac{\vert B \vert - 1}{2}z_B\f] */ |
655 \frac{\vert B \vert - 1}{2}z_B\f] */ |
641 /// |
656 /// |
642 /// The algorithm can be executed with \c run() or the \c init() and |
657 /// The algorithm can be executed with the run() function. |
643 /// then the \c start() member functions. After it the matching can |
658 /// After it the matching (the primal solution) and the dual solution |
644 /// be asked with \c matching() or mate() functions. The dual |
659 /// can be obtained using the query functions and the |
645 /// solution can be get with \c nodeValue(), \c blossomNum() and \c |
660 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, |
646 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt |
661 /// which is able to iterate on the nodes of a blossom. |
647 /// "BlossomIt" nested class, which is able to iterate on the nodes |
662 /// If the value type is integer, then the dual solution is multiplied |
648 /// of a blossom. If the value type is integral then the dual |
663 /// by \ref MaxWeightedMatching::dualScale "4". |
649 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". |
664 /// |
|
665 /// \tparam GR The graph type the algorithm runs on. |
|
666 /// \tparam WM The type edge weight map. The default type is |
|
667 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
|
668 #ifdef DOXYGEN |
|
669 template <typename GR, typename WM> |
|
670 #else |
650 template <typename GR, |
671 template <typename GR, |
651 typename WM = typename GR::template EdgeMap<int> > |
672 typename WM = typename GR::template EdgeMap<int> > |
|
673 #endif |
652 class MaxWeightedMatching { |
674 class MaxWeightedMatching { |
653 public: |
675 public: |
654 |
676 |
655 ///\e |
677 /// The graph type of the algorithm |
656 typedef GR Graph; |
678 typedef GR Graph; |
657 ///\e |
679 /// The type of the edge weight map |
658 typedef WM WeightMap; |
680 typedef WM WeightMap; |
659 ///\e |
681 /// The value type of the edge weights |
660 typedef typename WeightMap::Value Value; |
682 typedef typename WeightMap::Value Value; |
661 |
683 |
|
684 typedef typename Graph::template NodeMap<typename Graph::Arc> |
|
685 MatchingMap; |
|
686 |
662 /// \brief Scaling factor for dual solution |
687 /// \brief Scaling factor for dual solution |
663 /// |
688 /// |
664 /// Scaling factor for dual solution, it is equal to 4 or 1 |
689 /// Scaling factor for dual solution. It is equal to 4 or 1 |
665 /// according to the value type. |
690 /// according to the value type. |
666 static const int dualScale = |
691 static const int dualScale = |
667 std::numeric_limits<Value>::is_integer ? 4 : 1; |
692 std::numeric_limits<Value>::is_integer ? 4 : 1; |
668 |
|
669 typedef typename Graph::template NodeMap<typename Graph::Arc> |
|
670 MatchingMap; |
|
671 |
693 |
672 private: |
694 private: |
673 |
695 |
674 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
696 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
675 |
697 |
1629 |
1651 |
1630 ~MaxWeightedMatching() { |
1652 ~MaxWeightedMatching() { |
1631 destroyStructures(); |
1653 destroyStructures(); |
1632 } |
1654 } |
1633 |
1655 |
1634 /// \name Execution control |
1656 /// \name Execution Control |
1635 /// The simplest way to execute the algorithm is to use the |
1657 /// The simplest way to execute the algorithm is to use the |
1636 /// \c run() member function. |
1658 /// \ref run() member function. |
1637 |
1659 |
1638 ///@{ |
1660 ///@{ |
1639 |
1661 |
1640 /// \brief Initialize the algorithm |
1662 /// \brief Initialize the algorithm |
1641 /// |
1663 /// |
1642 /// Initialize the algorithm |
1664 /// This function initializes the algorithm. |
1643 void init() { |
1665 void init() { |
1644 createStructures(); |
1666 createStructures(); |
1645 |
1667 |
1646 for (ArcIt e(_graph); e != INVALID; ++e) { |
1668 for (ArcIt e(_graph); e != INVALID; ++e) { |
1647 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
1669 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
1790 start(); |
1814 start(); |
1791 } |
1815 } |
1792 |
1816 |
1793 /// @} |
1817 /// @} |
1794 |
1818 |
1795 /// \name Primal solution |
1819 /// \name Primal Solution |
1796 /// Functions to get the primal solution, ie. the matching. |
1820 /// Functions to get the primal solution, i.e. the maximum weighted |
|
1821 /// matching.\n |
|
1822 /// Either \ref run() or \ref start() function should be called before |
|
1823 /// using them. |
1797 |
1824 |
1798 /// @{ |
1825 /// @{ |
1799 |
1826 |
1800 /// \brief Returns the weight of the matching. |
1827 /// \brief Return the weight of the matching. |
1801 /// |
1828 /// |
1802 /// Returns the weight of the matching. |
1829 /// This function returns the weight of the found matching. |
|
1830 /// |
|
1831 /// \pre Either run() or start() must be called before using this function. |
1803 Value matchingValue() const { |
1832 Value matchingValue() const { |
1804 Value sum = 0; |
1833 Value sum = 0; |
1805 for (NodeIt n(_graph); n != INVALID; ++n) { |
1834 for (NodeIt n(_graph); n != INVALID; ++n) { |
1806 if ((*_matching)[n] != INVALID) { |
1835 if ((*_matching)[n] != INVALID) { |
1807 sum += _weight[(*_matching)[n]]; |
1836 sum += _weight[(*_matching)[n]]; |
1808 } |
1837 } |
1809 } |
1838 } |
1810 return sum /= 2; |
1839 return sum /= 2; |
1811 } |
1840 } |
1812 |
1841 |
1813 /// \brief Returns the cardinality of the matching. |
1842 /// \brief Return the size (cardinality) of the matching. |
1814 /// |
1843 /// |
1815 /// Returns the cardinality of the matching. |
1844 /// This function returns the size (cardinality) of the found matching. |
|
1845 /// |
|
1846 /// \pre Either run() or start() must be called before using this function. |
1816 int matchingSize() const { |
1847 int matchingSize() const { |
1817 int num = 0; |
1848 int num = 0; |
1818 for (NodeIt n(_graph); n != INVALID; ++n) { |
1849 for (NodeIt n(_graph); n != INVALID; ++n) { |
1819 if ((*_matching)[n] != INVALID) { |
1850 if ((*_matching)[n] != INVALID) { |
1820 ++num; |
1851 ++num; |
1821 } |
1852 } |
1822 } |
1853 } |
1823 return num /= 2; |
1854 return num /= 2; |
1824 } |
1855 } |
1825 |
1856 |
1826 /// \brief Returns true when the edge is in the matching. |
1857 /// \brief Return \c true if the given edge is in the matching. |
1827 /// |
1858 /// |
1828 /// Returns true when the edge is in the matching. |
1859 /// This function returns \c true if the given edge is in the found |
|
1860 /// matching. |
|
1861 /// |
|
1862 /// \pre Either run() or start() must be called before using this function. |
1829 bool matching(const Edge& edge) const { |
1863 bool matching(const Edge& edge) const { |
1830 return edge == (*_matching)[_graph.u(edge)]; |
1864 return edge == (*_matching)[_graph.u(edge)]; |
1831 } |
1865 } |
1832 |
1866 |
1833 /// \brief Returns the incident matching arc. |
1867 /// \brief Return the matching arc (or edge) incident to the given node. |
1834 /// |
1868 /// |
1835 /// Returns the incident matching arc from given node. If the |
1869 /// This function returns the matching arc (or edge) incident to the |
1836 /// node is not matched then it gives back \c INVALID. |
1870 /// given node in the found matching or \c INVALID if the node is |
|
1871 /// not covered by the matching. |
|
1872 /// |
|
1873 /// \pre Either run() or start() must be called before using this function. |
1837 Arc matching(const Node& node) const { |
1874 Arc matching(const Node& node) const { |
1838 return (*_matching)[node]; |
1875 return (*_matching)[node]; |
1839 } |
1876 } |
1840 |
1877 |
1841 /// \brief Returns the mate of the node. |
1878 /// \brief Return the mate of the given node. |
1842 /// |
1879 /// |
1843 /// Returns the adjancent node in a mathcing arc. If the node is |
1880 /// This function returns the mate of the given node in the found |
1844 /// not matched then it gives back \c INVALID. |
1881 /// matching or \c INVALID if the node is not covered by the matching. |
|
1882 /// |
|
1883 /// \pre Either run() or start() must be called before using this function. |
1845 Node mate(const Node& node) const { |
1884 Node mate(const Node& node) const { |
1846 return (*_matching)[node] != INVALID ? |
1885 return (*_matching)[node] != INVALID ? |
1847 _graph.target((*_matching)[node]) : INVALID; |
1886 _graph.target((*_matching)[node]) : INVALID; |
1848 } |
1887 } |
1849 |
1888 |
1850 /// @} |
1889 /// @} |
1851 |
1890 |
1852 /// \name Dual solution |
1891 /// \name Dual Solution |
1853 /// Functions to get the dual solution. |
1892 /// Functions to get the dual solution.\n |
|
1893 /// Either \ref run() or \ref start() function should be called before |
|
1894 /// using them. |
1854 |
1895 |
1855 /// @{ |
1896 /// @{ |
1856 |
1897 |
1857 /// \brief Returns the value of the dual solution. |
1898 /// \brief Return the value of the dual solution. |
1858 /// |
1899 /// |
1859 /// Returns the value of the dual solution. It should be equal to |
1900 /// This function returns the value of the dual solution. |
1860 /// the primal value scaled by \ref dualScale "dual scale". |
1901 /// It should be equal to the primal value scaled by \ref dualScale |
|
1902 /// "dual scale". |
|
1903 /// |
|
1904 /// \pre Either run() or start() must be called before using this function. |
1861 Value dualValue() const { |
1905 Value dualValue() const { |
1862 Value sum = 0; |
1906 Value sum = 0; |
1863 for (NodeIt n(_graph); n != INVALID; ++n) { |
1907 for (NodeIt n(_graph); n != INVALID; ++n) { |
1864 sum += nodeValue(n); |
1908 sum += nodeValue(n); |
1865 } |
1909 } |
1867 sum += blossomValue(i) * (blossomSize(i) / 2); |
1911 sum += blossomValue(i) * (blossomSize(i) / 2); |
1868 } |
1912 } |
1869 return sum; |
1913 return sum; |
1870 } |
1914 } |
1871 |
1915 |
1872 /// \brief Returns the value of the node. |
1916 /// \brief Return the dual value (potential) of the given node. |
1873 /// |
1917 /// |
1874 /// Returns the the value of the node. |
1918 /// This function returns the dual value (potential) of the given node. |
|
1919 /// |
|
1920 /// \pre Either run() or start() must be called before using this function. |
1875 Value nodeValue(const Node& n) const { |
1921 Value nodeValue(const Node& n) const { |
1876 return (*_node_potential)[n]; |
1922 return (*_node_potential)[n]; |
1877 } |
1923 } |
1878 |
1924 |
1879 /// \brief Returns the number of the blossoms in the basis. |
1925 /// \brief Return the number of the blossoms in the basis. |
1880 /// |
1926 /// |
1881 /// Returns the number of the blossoms in the basis. |
1927 /// This function returns the number of the blossoms in the basis. |
|
1928 /// |
|
1929 /// \pre Either run() or start() must be called before using this function. |
1882 /// \see BlossomIt |
1930 /// \see BlossomIt |
1883 int blossomNum() const { |
1931 int blossomNum() const { |
1884 return _blossom_potential.size(); |
1932 return _blossom_potential.size(); |
1885 } |
1933 } |
1886 |
1934 |
1887 |
1935 /// \brief Return the number of the nodes in the given blossom. |
1888 /// \brief Returns the number of the nodes in the blossom. |
1936 /// |
1889 /// |
1937 /// This function returns the number of the nodes in the given blossom. |
1890 /// Returns the number of the nodes in the blossom. |
1938 /// |
|
1939 /// \pre Either run() or start() must be called before using this function. |
|
1940 /// \see BlossomIt |
1891 int blossomSize(int k) const { |
1941 int blossomSize(int k) const { |
1892 return _blossom_potential[k].end - _blossom_potential[k].begin; |
1942 return _blossom_potential[k].end - _blossom_potential[k].begin; |
1893 } |
1943 } |
1894 |
1944 |
1895 /// \brief Returns the value of the blossom. |
1945 /// \brief Return the dual value (ptential) of the given blossom. |
1896 /// |
1946 /// |
1897 /// Returns the the value of the blossom. |
1947 /// This function returns the dual value (ptential) of the given blossom. |
1898 /// \see BlossomIt |
1948 /// |
|
1949 /// \pre Either run() or start() must be called before using this function. |
1899 Value blossomValue(int k) const { |
1950 Value blossomValue(int k) const { |
1900 return _blossom_potential[k].value; |
1951 return _blossom_potential[k].value; |
1901 } |
1952 } |
1902 |
1953 |
1903 /// \brief Iterator for obtaining the nodes of the blossom. |
1954 /// \brief Iterator for obtaining the nodes of a blossom. |
1904 /// |
1955 /// |
1905 /// Iterator for obtaining the nodes of the blossom. This class |
1956 /// This class provides an iterator for obtaining the nodes of the |
1906 /// provides a common lemon style iterator for listing a |
1957 /// given blossom. It lists a subset of the nodes. |
1907 /// subset of the nodes. |
1958 /// Before using this iterator, you must allocate a |
|
1959 /// MaxWeightedMatching class and execute it. |
1908 class BlossomIt { |
1960 class BlossomIt { |
1909 public: |
1961 public: |
1910 |
1962 |
1911 /// \brief Constructor. |
1963 /// \brief Constructor. |
1912 /// |
1964 /// |
1913 /// Constructor to get the nodes of the variable. |
1965 /// Constructor to get the nodes of the given variable. |
|
1966 /// |
|
1967 /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or |
|
1968 /// \ref MaxWeightedMatching::start() "algorithm.start()" must be |
|
1969 /// called before initializing this iterator. |
1914 BlossomIt(const MaxWeightedMatching& algorithm, int variable) |
1970 BlossomIt(const MaxWeightedMatching& algorithm, int variable) |
1915 : _algorithm(&algorithm) |
1971 : _algorithm(&algorithm) |
1916 { |
1972 { |
1917 _index = _algorithm->_blossom_potential[variable].begin; |
1973 _index = _algorithm->_blossom_potential[variable].begin; |
1918 _last = _algorithm->_blossom_potential[variable].end; |
1974 _last = _algorithm->_blossom_potential[variable].end; |
1919 } |
1975 } |
1920 |
1976 |
1921 /// \brief Conversion to node. |
1977 /// \brief Conversion to \c Node. |
1922 /// |
1978 /// |
1923 /// Conversion to node. |
1979 /// Conversion to \c Node. |
1924 operator Node() const { |
1980 operator Node() const { |
1925 return _algorithm->_blossom_node_list[_index]; |
1981 return _algorithm->_blossom_node_list[_index]; |
1926 } |
1982 } |
1927 |
1983 |
1928 /// \brief Increment operator. |
1984 /// \brief Increment operator. |
1960 /// This class provides an efficient implementation of Edmond's |
2016 /// This class provides an efficient implementation of Edmond's |
1961 /// maximum weighted perfect matching algorithm. The implementation |
2017 /// maximum weighted perfect matching algorithm. The implementation |
1962 /// is based on extensive use of priority queues and provides |
2018 /// is based on extensive use of priority queues and provides |
1963 /// \f$O(nm\log n)\f$ time complexity. |
2019 /// \f$O(nm\log n)\f$ time complexity. |
1964 /// |
2020 /// |
1965 /// The maximum weighted matching problem is to find undirected |
2021 /// The maximum weighted perfect matching problem is to find a subset of |
1966 /// edges in the graph with maximum overall weight and no two of |
2022 /// the edges in an undirected graph with maximum overall weight for which |
1967 /// them shares their ends and covers all nodes. The problem can be |
2023 /// each node has exactly one incident edge. |
1968 /// formulated with the following linear program. |
2024 /// It can be formulated with the following linear program. |
1969 /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f] |
2025 /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f] |
1970 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} |
2026 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} |
1971 \quad \forall B\in\mathcal{O}\f] */ |
2027 \quad \forall B\in\mathcal{O}\f] */ |
1972 /// \f[x_e \ge 0\quad \forall e\in E\f] |
2028 /// \f[x_e \ge 0\quad \forall e\in E\f] |
1973 /// \f[\max \sum_{e\in E}x_ew_e\f] |
2029 /// \f[\max \sum_{e\in E}x_ew_e\f] |
1977 /// subsets of the nodes. |
2033 /// subsets of the nodes. |
1978 /// |
2034 /// |
1979 /// The algorithm calculates an optimal matching and a proof of the |
2035 /// The algorithm calculates an optimal matching and a proof of the |
1980 /// optimality. The solution of the dual problem can be used to check |
2036 /// optimality. The solution of the dual problem can be used to check |
1981 /// the result of the algorithm. The dual linear problem is the |
2037 /// the result of the algorithm. The dual linear problem is the |
|
2038 /// following. |
1982 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge |
2039 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge |
1983 w_{uv} \quad \forall uv\in E\f] */ |
2040 w_{uv} \quad \forall uv\in E\f] */ |
1984 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f] |
2041 /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f] |
1985 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} |
2042 /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}} |
1986 \frac{\vert B \vert - 1}{2}z_B\f] */ |
2043 \frac{\vert B \vert - 1}{2}z_B\f] */ |
1987 /// |
2044 /// |
1988 /// The algorithm can be executed with \c run() or the \c init() and |
2045 /// The algorithm can be executed with the run() function. |
1989 /// then the \c start() member functions. After it the matching can |
2046 /// After it the matching (the primal solution) and the dual solution |
1990 /// be asked with \c matching() or mate() functions. The dual |
2047 /// can be obtained using the query functions and the |
1991 /// solution can be get with \c nodeValue(), \c blossomNum() and \c |
2048 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, |
1992 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt |
2049 /// which is able to iterate on the nodes of a blossom. |
1993 /// "BlossomIt" nested class which is able to iterate on the nodes |
2050 /// If the value type is integer, then the dual solution is multiplied |
1994 /// of a blossom. If the value type is integral then the dual |
2051 /// by \ref MaxWeightedMatching::dualScale "4". |
1995 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". |
2052 /// |
|
2053 /// \tparam GR The graph type the algorithm runs on. |
|
2054 /// \tparam WM The type edge weight map. The default type is |
|
2055 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
|
2056 #ifdef DOXYGEN |
|
2057 template <typename GR, typename WM> |
|
2058 #else |
1996 template <typename GR, |
2059 template <typename GR, |
1997 typename WM = typename GR::template EdgeMap<int> > |
2060 typename WM = typename GR::template EdgeMap<int> > |
|
2061 #endif |
1998 class MaxWeightedPerfectMatching { |
2062 class MaxWeightedPerfectMatching { |
1999 public: |
2063 public: |
2000 |
2064 |
|
2065 /// The graph type of the algorithm |
2001 typedef GR Graph; |
2066 typedef GR Graph; |
|
2067 /// The type of the edge weight map |
2002 typedef WM WeightMap; |
2068 typedef WM WeightMap; |
|
2069 /// The value type of the edge weights |
2003 typedef typename WeightMap::Value Value; |
2070 typedef typename WeightMap::Value Value; |
2004 |
2071 |
2005 /// \brief Scaling factor for dual solution |
2072 /// \brief Scaling factor for dual solution |
2006 /// |
2073 /// |
2007 /// Scaling factor for dual solution, it is equal to 4 or 1 |
2074 /// Scaling factor for dual solution, it is equal to 4 or 1 |
2816 |
2883 |
2817 ~MaxWeightedPerfectMatching() { |
2884 ~MaxWeightedPerfectMatching() { |
2818 destroyStructures(); |
2885 destroyStructures(); |
2819 } |
2886 } |
2820 |
2887 |
2821 /// \name Execution control |
2888 /// \name Execution Control |
2822 /// The simplest way to execute the algorithm is to use the |
2889 /// The simplest way to execute the algorithm is to use the |
2823 /// \c run() member function. |
2890 /// \ref run() member function. |
2824 |
2891 |
2825 ///@{ |
2892 ///@{ |
2826 |
2893 |
2827 /// \brief Initialize the algorithm |
2894 /// \brief Initialize the algorithm |
2828 /// |
2895 /// |
2829 /// Initialize the algorithm |
2896 /// This function initializes the algorithm. |
2830 void init() { |
2897 void init() { |
2831 createStructures(); |
2898 createStructures(); |
2832 |
2899 |
2833 for (ArcIt e(_graph); e != INVALID; ++e) { |
2900 for (ArcIt e(_graph); e != INVALID; ++e) { |
2834 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
2901 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
2938 } |
3007 } |
2939 extractMatching(); |
3008 extractMatching(); |
2940 return true; |
3009 return true; |
2941 } |
3010 } |
2942 |
3011 |
2943 /// \brief Runs %MaxWeightedPerfectMatching algorithm. |
3012 /// \brief Run the algorithm. |
2944 /// |
3013 /// |
2945 /// This method runs the %MaxWeightedPerfectMatching algorithm. |
3014 /// This method runs the \c %MaxWeightedPerfectMatching algorithm. |
2946 /// |
3015 /// |
2947 /// \note mwm.run() is just a shortcut of the following code. |
3016 /// \note mwpm.run() is just a shortcut of the following code. |
2948 /// \code |
3017 /// \code |
2949 /// mwm.init(); |
3018 /// mwpm.init(); |
2950 /// mwm.start(); |
3019 /// mwpm.start(); |
2951 /// \endcode |
3020 /// \endcode |
2952 bool run() { |
3021 bool run() { |
2953 init(); |
3022 init(); |
2954 return start(); |
3023 return start(); |
2955 } |
3024 } |
2956 |
3025 |
2957 /// @} |
3026 /// @} |
2958 |
3027 |
2959 /// \name Primal solution |
3028 /// \name Primal Solution |
2960 /// Functions to get the primal solution, ie. the matching. |
3029 /// Functions to get the primal solution, i.e. the maximum weighted |
|
3030 /// perfect matching.\n |
|
3031 /// Either \ref run() or \ref start() function should be called before |
|
3032 /// using them. |
2961 |
3033 |
2962 /// @{ |
3034 /// @{ |
2963 |
3035 |
2964 /// \brief Returns the matching value. |
3036 /// \brief Return the weight of the matching. |
2965 /// |
3037 /// |
2966 /// Returns the matching value. |
3038 /// This function returns the weight of the found matching. |
|
3039 /// |
|
3040 /// \pre Either run() or start() must be called before using this function. |
2967 Value matchingValue() const { |
3041 Value matchingValue() const { |
2968 Value sum = 0; |
3042 Value sum = 0; |
2969 for (NodeIt n(_graph); n != INVALID; ++n) { |
3043 for (NodeIt n(_graph); n != INVALID; ++n) { |
2970 if ((*_matching)[n] != INVALID) { |
3044 if ((*_matching)[n] != INVALID) { |
2971 sum += _weight[(*_matching)[n]]; |
3045 sum += _weight[(*_matching)[n]]; |
2972 } |
3046 } |
2973 } |
3047 } |
2974 return sum /= 2; |
3048 return sum /= 2; |
2975 } |
3049 } |
2976 |
3050 |
2977 /// \brief Returns true when the edge is in the matching. |
3051 /// \brief Return \c true if the given edge is in the matching. |
2978 /// |
3052 /// |
2979 /// Returns true when the edge is in the matching. |
3053 /// This function returns \c true if the given edge is in the found |
|
3054 /// matching. |
|
3055 /// |
|
3056 /// \pre Either run() or start() must be called before using this function. |
2980 bool matching(const Edge& edge) const { |
3057 bool matching(const Edge& edge) const { |
2981 return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge; |
3058 return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge; |
2982 } |
3059 } |
2983 |
3060 |
2984 /// \brief Returns the incident matching edge. |
3061 /// \brief Return the matching arc (or edge) incident to the given node. |
2985 /// |
3062 /// |
2986 /// Returns the incident matching arc from given edge. |
3063 /// This function returns the matching arc (or edge) incident to the |
|
3064 /// given node in the found matching or \c INVALID if the node is |
|
3065 /// not covered by the matching. |
|
3066 /// |
|
3067 /// \pre Either run() or start() must be called before using this function. |
2987 Arc matching(const Node& node) const { |
3068 Arc matching(const Node& node) const { |
2988 return (*_matching)[node]; |
3069 return (*_matching)[node]; |
2989 } |
3070 } |
2990 |
3071 |
2991 /// \brief Returns the mate of the node. |
3072 /// \brief Return the mate of the given node. |
2992 /// |
3073 /// |
2993 /// Returns the adjancent node in a mathcing arc. |
3074 /// This function returns the mate of the given node in the found |
|
3075 /// matching or \c INVALID if the node is not covered by the matching. |
|
3076 /// |
|
3077 /// \pre Either run() or start() must be called before using this function. |
2994 Node mate(const Node& node) const { |
3078 Node mate(const Node& node) const { |
2995 return _graph.target((*_matching)[node]); |
3079 return _graph.target((*_matching)[node]); |
2996 } |
3080 } |
2997 |
3081 |
2998 /// @} |
3082 /// @} |
2999 |
3083 |
3000 /// \name Dual solution |
3084 /// \name Dual Solution |
3001 /// Functions to get the dual solution. |
3085 /// Functions to get the dual solution.\n |
|
3086 /// Either \ref run() or \ref start() function should be called before |
|
3087 /// using them. |
3002 |
3088 |
3003 /// @{ |
3089 /// @{ |
3004 |
3090 |
3005 /// \brief Returns the value of the dual solution. |
3091 /// \brief Return the value of the dual solution. |
3006 /// |
3092 /// |
3007 /// Returns the value of the dual solution. It should be equal to |
3093 /// This function returns the value of the dual solution. |
3008 /// the primal value scaled by \ref dualScale "dual scale". |
3094 /// It should be equal to the primal value scaled by \ref dualScale |
|
3095 /// "dual scale". |
|
3096 /// |
|
3097 /// \pre Either run() or start() must be called before using this function. |
3009 Value dualValue() const { |
3098 Value dualValue() const { |
3010 Value sum = 0; |
3099 Value sum = 0; |
3011 for (NodeIt n(_graph); n != INVALID; ++n) { |
3100 for (NodeIt n(_graph); n != INVALID; ++n) { |
3012 sum += nodeValue(n); |
3101 sum += nodeValue(n); |
3013 } |
3102 } |
3015 sum += blossomValue(i) * (blossomSize(i) / 2); |
3104 sum += blossomValue(i) * (blossomSize(i) / 2); |
3016 } |
3105 } |
3017 return sum; |
3106 return sum; |
3018 } |
3107 } |
3019 |
3108 |
3020 /// \brief Returns the value of the node. |
3109 /// \brief Return the dual value (potential) of the given node. |
3021 /// |
3110 /// |
3022 /// Returns the the value of the node. |
3111 /// This function returns the dual value (potential) of the given node. |
|
3112 /// |
|
3113 /// \pre Either run() or start() must be called before using this function. |
3023 Value nodeValue(const Node& n) const { |
3114 Value nodeValue(const Node& n) const { |
3024 return (*_node_potential)[n]; |
3115 return (*_node_potential)[n]; |
3025 } |
3116 } |
3026 |
3117 |
3027 /// \brief Returns the number of the blossoms in the basis. |
3118 /// \brief Return the number of the blossoms in the basis. |
3028 /// |
3119 /// |
3029 /// Returns the number of the blossoms in the basis. |
3120 /// This function returns the number of the blossoms in the basis. |
|
3121 /// |
|
3122 /// \pre Either run() or start() must be called before using this function. |
3030 /// \see BlossomIt |
3123 /// \see BlossomIt |
3031 int blossomNum() const { |
3124 int blossomNum() const { |
3032 return _blossom_potential.size(); |
3125 return _blossom_potential.size(); |
3033 } |
3126 } |
3034 |
3127 |
3035 |
3128 /// \brief Return the number of the nodes in the given blossom. |
3036 /// \brief Returns the number of the nodes in the blossom. |
3129 /// |
3037 /// |
3130 /// This function returns the number of the nodes in the given blossom. |
3038 /// Returns the number of the nodes in the blossom. |
3131 /// |
|
3132 /// \pre Either run() or start() must be called before using this function. |
|
3133 /// \see BlossomIt |
3039 int blossomSize(int k) const { |
3134 int blossomSize(int k) const { |
3040 return _blossom_potential[k].end - _blossom_potential[k].begin; |
3135 return _blossom_potential[k].end - _blossom_potential[k].begin; |
3041 } |
3136 } |
3042 |
3137 |
3043 /// \brief Returns the value of the blossom. |
3138 /// \brief Return the dual value (ptential) of the given blossom. |
3044 /// |
3139 /// |
3045 /// Returns the the value of the blossom. |
3140 /// This function returns the dual value (ptential) of the given blossom. |
3046 /// \see BlossomIt |
3141 /// |
|
3142 /// \pre Either run() or start() must be called before using this function. |
3047 Value blossomValue(int k) const { |
3143 Value blossomValue(int k) const { |
3048 return _blossom_potential[k].value; |
3144 return _blossom_potential[k].value; |
3049 } |
3145 } |
3050 |
3146 |
3051 /// \brief Iterator for obtaining the nodes of the blossom. |
3147 /// \brief Iterator for obtaining the nodes of a blossom. |
3052 /// |
3148 /// |
3053 /// Iterator for obtaining the nodes of the blossom. This class |
3149 /// This class provides an iterator for obtaining the nodes of the |
3054 /// provides a common lemon style iterator for listing a |
3150 /// given blossom. It lists a subset of the nodes. |
3055 /// subset of the nodes. |
3151 /// Before using this iterator, you must allocate a |
|
3152 /// MaxWeightedPerfectMatching class and execute it. |
3056 class BlossomIt { |
3153 class BlossomIt { |
3057 public: |
3154 public: |
3058 |
3155 |
3059 /// \brief Constructor. |
3156 /// \brief Constructor. |
3060 /// |
3157 /// |
3061 /// Constructor to get the nodes of the variable. |
3158 /// Constructor to get the nodes of the given variable. |
|
3159 /// |
|
3160 /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" |
|
3161 /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" |
|
3162 /// must be called before initializing this iterator. |
3062 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) |
3163 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) |
3063 : _algorithm(&algorithm) |
3164 : _algorithm(&algorithm) |
3064 { |
3165 { |
3065 _index = _algorithm->_blossom_potential[variable].begin; |
3166 _index = _algorithm->_blossom_potential[variable].begin; |
3066 _last = _algorithm->_blossom_potential[variable].end; |
3167 _last = _algorithm->_blossom_potential[variable].end; |
3067 } |
3168 } |
3068 |
3169 |
3069 /// \brief Conversion to node. |
3170 /// \brief Conversion to \c Node. |
3070 /// |
3171 /// |
3071 /// Conversion to node. |
3172 /// Conversion to \c Node. |
3072 operator Node() const { |
3173 operator Node() const { |
3073 return _algorithm->_blossom_node_list[_index]; |
3174 return _algorithm->_blossom_node_list[_index]; |
3074 } |
3175 } |
3075 |
3176 |
3076 /// \brief Increment operator. |
3177 /// \brief Increment operator. |