equal
deleted
inserted
replaced
656 /// |
656 /// |
657 /// The algorithm can be executed with the run() function. |
657 /// The algorithm can be executed with the run() function. |
658 /// After it the matching (the primal solution) and the dual solution |
658 /// After it the matching (the primal solution) and the dual solution |
659 /// can be obtained using the query functions. |
659 /// can be obtained using the query functions. |
660 /// |
660 /// |
661 /// If the value type is integer, then the primal and the dual |
661 /// The primal solution is multiplied by |
662 /// solutions are multiplied by |
662 /// \ref MaxWeightedFractionalMatching::primalScale "2". |
663 /// \ref MaxWeightedFractionalMatching::primalScale "2" and |
663 /// If the value type is integer, then the dual |
664 /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively. |
664 /// solution is scaled by |
|
665 /// \ref MaxWeightedFractionalMatching::dualScale "4". |
665 /// |
666 /// |
666 /// \tparam GR The undirected graph type the algorithm runs on. |
667 /// \tparam GR The undirected graph type the algorithm runs on. |
667 /// \tparam WM The type edge weight map. The default type is |
668 /// \tparam WM The type edge weight map. The default type is |
668 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
669 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
669 #ifdef DOXYGEN |
670 #ifdef DOXYGEN |
686 typedef typename Graph::template NodeMap<typename Graph::Arc> |
687 typedef typename Graph::template NodeMap<typename Graph::Arc> |
687 MatchingMap; |
688 MatchingMap; |
688 |
689 |
689 /// \brief Scaling factor for primal solution |
690 /// \brief Scaling factor for primal solution |
690 /// |
691 /// |
691 /// Scaling factor for primal solution. It is equal to 2 or 1 |
692 /// Scaling factor for primal solution. |
692 /// according to the value type. |
693 static const int primalScale = 2; |
693 static const int primalScale = |
|
694 std::numeric_limits<Value>::is_integer ? 2 : 1; |
|
695 |
694 |
696 /// \brief Scaling factor for dual solution |
695 /// \brief Scaling factor for dual solution |
697 /// |
696 /// |
698 /// Scaling factor for dual solution. It is equal to 4 or 1 |
697 /// Scaling factor for dual solution. It is equal to 4 or 1 |
699 /// according to the value type. |
698 /// according to the value type. |
1327 /// This function returns \c true if the given edge is in the |
1326 /// This function returns \c true if the given edge is in the |
1328 /// found matching. The result is scaled by \ref primalScale |
1327 /// found matching. The result is scaled by \ref primalScale |
1329 /// "primal scale". |
1328 /// "primal scale". |
1330 /// |
1329 /// |
1331 /// \pre Either run() or start() must be called before using this function. |
1330 /// \pre Either run() or start() must be called before using this function. |
1332 Value matching(const Edge& edge) const { |
1331 int matching(const Edge& edge) const { |
1333 return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0) |
1332 return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0) |
1334 * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0) |
1333 + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0); |
1335 * primalScale / 2; |
|
1336 } |
1334 } |
1337 |
1335 |
1338 /// \brief Return the fractional matching arc (or edge) incident |
1336 /// \brief Return the fractional matching arc (or edge) incident |
1339 /// to the given node. |
1337 /// to the given node. |
1340 /// |
1338 /// |
1421 /// \f[\min \sum_{u \in V}y_u \f] |
1419 /// \f[\min \sum_{u \in V}y_u \f] |
1422 /// |
1420 /// |
1423 /// The algorithm can be executed with the run() function. |
1421 /// The algorithm can be executed with the run() function. |
1424 /// After it the matching (the primal solution) and the dual solution |
1422 /// After it the matching (the primal solution) and the dual solution |
1425 /// can be obtained using the query functions. |
1423 /// can be obtained using the query functions. |
1426 |
1424 /// |
1427 /// If the value type is integer, then the primal and the dual |
1425 /// The primal solution is multiplied by |
1428 /// solutions are multiplied by |
1426 /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2". |
1429 /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and |
1427 /// If the value type is integer, then the dual |
1430 /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively. |
1428 /// solution is scaled by |
|
1429 /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4". |
1431 /// |
1430 /// |
1432 /// \tparam GR The undirected graph type the algorithm runs on. |
1431 /// \tparam GR The undirected graph type the algorithm runs on. |
1433 /// \tparam WM The type edge weight map. The default type is |
1432 /// \tparam WM The type edge weight map. The default type is |
1434 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
1433 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
1435 #ifdef DOXYGEN |
1434 #ifdef DOXYGEN |
1452 typedef typename Graph::template NodeMap<typename Graph::Arc> |
1451 typedef typename Graph::template NodeMap<typename Graph::Arc> |
1453 MatchingMap; |
1452 MatchingMap; |
1454 |
1453 |
1455 /// \brief Scaling factor for primal solution |
1454 /// \brief Scaling factor for primal solution |
1456 /// |
1455 /// |
1457 /// Scaling factor for primal solution. It is equal to 2 or 1 |
1456 /// Scaling factor for primal solution. |
1458 /// according to the value type. |
1457 static const int primalScale = 2; |
1459 static const int primalScale = |
|
1460 std::numeric_limits<Value>::is_integer ? 2 : 1; |
|
1461 |
1458 |
1462 /// \brief Scaling factor for dual solution |
1459 /// \brief Scaling factor for dual solution |
1463 /// |
1460 /// |
1464 /// Scaling factor for dual solution. It is equal to 4 or 1 |
1461 /// Scaling factor for dual solution. It is equal to 4 or 1 |
1465 /// according to the value type. |
1462 /// according to the value type. |
2062 /// This function returns \c true if the given edge is in the |
2059 /// This function returns \c true if the given edge is in the |
2063 /// found matching. The result is scaled by \ref primalScale |
2060 /// found matching. The result is scaled by \ref primalScale |
2064 /// "primal scale". |
2061 /// "primal scale". |
2065 /// |
2062 /// |
2066 /// \pre Either run() or start() must be called before using this function. |
2063 /// \pre Either run() or start() must be called before using this function. |
2067 Value matching(const Edge& edge) const { |
2064 int matching(const Edge& edge) const { |
2068 return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0) |
2065 return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0) |
2069 * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0) |
2066 + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0); |
2070 * primalScale / 2; |
|
2071 } |
2067 } |
2072 |
2068 |
2073 /// \brief Return the fractional matching arc (or edge) incident |
2069 /// \brief Return the fractional matching arc (or edge) incident |
2074 /// to the given node. |
2070 /// to the given node. |
2075 /// |
2071 /// |