109 /// The algorithm can be executed with the run() function. After it |
109 /// The algorithm can be executed with the run() function. After it |
110 /// the matching (the primal solution) and the barrier (the dual |
110 /// the matching (the primal solution) and the barrier (the dual |
111 /// solution) can be obtained using the query functions. |
111 /// solution) can be obtained using the query functions. |
112 /// |
112 /// |
113 /// The primal solution is multiplied by |
113 /// The primal solution is multiplied by |
114 /// \ref MaxWeightedMatching::primalScale "2". |
114 /// \ref MaxFractionalMatching::primalScale "2". |
115 /// |
115 /// |
116 /// \tparam GR The undirected graph type the algorithm runs on. |
116 /// \tparam GR The undirected graph type the algorithm runs on. |
117 #ifdef DOXYGEN |
117 #ifdef DOXYGEN |
118 template <typename GR, typename TR> |
118 template <typename GR, typename TR> |
119 #else |
119 #else |
630 /// \ingroup matching |
630 /// \ingroup matching |
631 /// |
631 /// |
632 /// \brief Weighted fractional matching in general graphs |
632 /// \brief Weighted fractional matching in general graphs |
633 /// |
633 /// |
634 /// This class provides an efficient implementation of fractional |
634 /// This class provides an efficient implementation of fractional |
635 /// matching algorithm. The implementation is based on extensive use |
635 /// matching algorithm. The implementation uses priority queues and |
636 /// of priority queues and provides \f$O(nm\log n)\f$ time |
636 /// provides \f$O(nm\log n)\f$ time complexity. |
637 /// complexity. |
|
638 /// |
637 /// |
639 /// The maximum weighted fractional matching is a relaxation of the |
638 /// The maximum weighted fractional matching is a relaxation of the |
640 /// maximum weighted matching problem where the odd set constraints |
639 /// maximum weighted matching problem where the odd set constraints |
641 /// are omitted. |
640 /// are omitted. |
642 /// It can be formulated with the following linear program. |
641 /// It can be formulated with the following linear program. |
651 /// proof of the optimality. The solution of the dual problem can be |
650 /// proof of the optimality. The solution of the dual problem can be |
652 /// used to check the result of the algorithm. The dual linear |
651 /// used to check the result of the algorithm. The dual linear |
653 /// problem is the following. |
652 /// problem is the following. |
654 /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f] |
653 /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f] |
655 /// \f[y_u \ge 0 \quad \forall u \in V\f] |
654 /// \f[y_u \ge 0 \quad \forall u \in V\f] |
656 /// \f[\min \sum_{u \in V}y_u \f] /// |
655 /// \f[\min \sum_{u \in V}y_u \f] |
657 /// |
656 /// |
658 /// The algorithm can be executed with the run() function. |
657 /// The algorithm can be executed with the run() function. |
659 /// After it the matching (the primal solution) and the dual solution |
658 /// After it the matching (the primal solution) and the dual solution |
660 /// can be obtained using the query functions. |
659 /// can be obtained using the query functions. |
661 /// |
660 /// |
662 /// If the value type is integer, then the primal and the dual |
661 /// If the value type is integer, then the primal and the dual |
663 /// solutions are multiplied by |
662 /// solutions are multiplied by |
664 /// \ref MaxWeightedMatching::primalScale "2" and |
663 /// \ref MaxWeightedFractionalMatching::primalScale "2" and |
665 /// \ref MaxWeightedMatching::dualScale "4" respectively. |
664 /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively. |
666 /// |
665 /// |
667 /// \tparam GR The undirected graph type the algorithm runs on. |
666 /// \tparam GR The undirected graph type the algorithm runs on. |
668 /// \tparam WM The type edge weight map. The default type is |
667 /// \tparam WM The type edge weight map. The default type is |
669 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
668 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
670 #ifdef DOXYGEN |
669 #ifdef DOXYGEN |
1398 /// \ingroup matching |
1397 /// \ingroup matching |
1399 /// |
1398 /// |
1400 /// \brief Weighted fractional perfect matching in general graphs |
1399 /// \brief Weighted fractional perfect matching in general graphs |
1401 /// |
1400 /// |
1402 /// This class provides an efficient implementation of fractional |
1401 /// This class provides an efficient implementation of fractional |
1403 /// matching algorithm. The implementation is based on extensive use |
1402 /// matching algorithm. The implementation uses priority queues and |
1404 /// of priority queues and provides \f$O(nm\log n)\f$ time |
1403 /// provides \f$O(nm\log n)\f$ time complexity. |
1405 /// complexity. |
|
1406 /// |
1404 /// |
1407 /// The maximum weighted fractional perfect matching is a relaxation |
1405 /// The maximum weighted fractional perfect matching is a relaxation |
1408 /// of the maximum weighted perfect matching problem where the odd |
1406 /// of the maximum weighted perfect matching problem where the odd |
1409 /// set constraints are omitted. |
1407 /// set constraints are omitted. |
1410 /// It can be formulated with the following linear program. |
1408 /// It can be formulated with the following linear program. |
1418 /// The algorithm calculates an optimal fractional matching and a |
1416 /// The algorithm calculates an optimal fractional matching and a |
1419 /// proof of the optimality. The solution of the dual problem can be |
1417 /// proof of the optimality. The solution of the dual problem can be |
1420 /// used to check the result of the algorithm. The dual linear |
1418 /// used to check the result of the algorithm. The dual linear |
1421 /// problem is the following. |
1419 /// problem is the following. |
1422 /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f] |
1420 /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f] |
1423 /// \f[\min \sum_{u \in V}y_u \f] /// |
1421 /// \f[\min \sum_{u \in V}y_u \f] |
1424 /// |
1422 /// |
1425 /// The algorithm can be executed with the run() function. |
1423 /// The algorithm can be executed with the run() function. |
1426 /// After it the matching (the primal solution) and the dual solution |
1424 /// After it the matching (the primal solution) and the dual solution |
1427 /// can be obtained using the query functions. |
1425 /// can be obtained using the query functions. |
1428 |
1426 |
1429 /// If the value type is integer, then the primal and the dual |
1427 /// If the value type is integer, then the primal and the dual |
1430 /// solutions are multiplied by |
1428 /// solutions are multiplied by |
1431 /// \ref MaxWeightedMatching::primalScale "2" and |
1429 /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and |
1432 /// \ref MaxWeightedMatching::dualScale "4" respectively. |
1430 /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively. |
1433 /// |
1431 /// |
1434 /// \tparam GR The undirected graph type the algorithm runs on. |
1432 /// \tparam GR The undirected graph type the algorithm runs on. |
1435 /// \tparam WM The type edge weight map. The default type is |
1433 /// \tparam WM The type edge weight map. The default type is |
1436 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
1434 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
1437 #ifdef DOXYGEN |
1435 #ifdef DOXYGEN |