Changeset 951:41d7ac528c3a in lemon
- Timestamp:
- 03/04/10 15:20:59 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/fractional_matching.h
r950 r951 659 659 /// can be obtained using the query functions. 660 660 /// 661 /// If the value type is integer, then the primal and the dual 662 /// solutions are multiplied by 663 /// \ref MaxWeightedFractionalMatching::primalScale "2" and 664 /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively. 661 /// The primal solution is multiplied by 662 /// \ref MaxWeightedFractionalMatching::primalScale "2". 663 /// If the value type is integer, then the dual 664 /// solution is scaled by 665 /// \ref MaxWeightedFractionalMatching::dualScale "4". 665 666 /// 666 667 /// \tparam GR The undirected graph type the algorithm runs on. … … 689 690 /// \brief Scaling factor for primal solution 690 691 /// 691 /// Scaling factor for primal solution. It is equal to 2 or 1 692 /// according to the value type. 693 static const int primalScale = 694 std::numeric_limits<Value>::is_integer ? 2 : 1; 692 /// Scaling factor for primal solution. 693 static const int primalScale = 2; 695 694 696 695 /// \brief Scaling factor for dual solution … … 1330 1329 /// 1331 1330 /// \pre Either run() or start() must be called before using this function. 1332 Value matching(const Edge& edge) const { 1333 return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0) 1334 * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0) 1335 * primalScale / 2; 1331 int matching(const Edge& edge) const { 1332 return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0) 1333 + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0); 1336 1334 } 1337 1335 … … 1424 1422 /// After it the matching (the primal solution) and the dual solution 1425 1423 /// can be obtained using the query functions. 1426 1427 /// If the value type is integer, then the primal and the dual 1428 /// solutions are multiplied by 1429 /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and 1430 /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively. 1424 /// 1425 /// The primal solution is multiplied by 1426 /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2". 1427 /// If the value type is integer, then the dual 1428 /// solution is scaled by 1429 /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4". 1431 1430 /// 1432 1431 /// \tparam GR The undirected graph type the algorithm runs on. … … 1455 1454 /// \brief Scaling factor for primal solution 1456 1455 /// 1457 /// Scaling factor for primal solution. It is equal to 2 or 1 1458 /// according to the value type. 1459 static const int primalScale = 1460 std::numeric_limits<Value>::is_integer ? 2 : 1; 1456 /// Scaling factor for primal solution. 1457 static const int primalScale = 2; 1461 1458 1462 1459 /// \brief Scaling factor for dual solution … … 2065 2062 /// 2066 2063 /// \pre Either run() or start() must be called before using this function. 2067 Value matching(const Edge& edge) const { 2068 return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0) 2069 * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0) 2070 * primalScale / 2; 2064 int matching(const Edge& edge) const { 2065 return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0) 2066 + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0); 2071 2067 } 2072 2068 -
test/fractional_matching_test.cc
r948 r951 237 237 check(pv == mfm.matchingSize(), "Wrong matching size"); 238 238 239 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { 240 check((e == mfm.matching(graph.u(e)) ? 1 : 0) + 241 (e == mfm.matching(graph.v(e)) ? 1 : 0) == 242 mfm.matching(e), "Invalid matching"); 243 } 244 239 245 SmartGraph::NodeMap<bool> processed(graph, false); 240 246 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { … … 284 290 check(mfm.matching(n) != INVALID, "Invalid matching"); 285 291 check(indeg == 1, "Invalid matching"); 292 } 293 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { 294 check((e == mfm.matching(graph.u(e)) ? 1 : 0) + 295 (e == mfm.matching(graph.v(e)) ? 1 : 0) == 296 mfm.matching(e), "Invalid matching"); 286 297 } 287 298 } else { … … 338 349 } 339 350 351 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { 352 check((e == mwfm.matching(graph.u(e)) ? 1 : 0) + 353 (e == mwfm.matching(graph.v(e)) ? 1 : 0) == 354 mwfm.matching(e), "Invalid matching"); 355 } 356 340 357 int dv = 0; 341 358 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { … … 392 409 } 393 410 411 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { 412 check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) + 413 (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == 414 mwpfm.matching(e), "Invalid matching"); 415 } 416 394 417 int dv = 0; 395 418 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
Note: See TracChangeset
for help on using the changeset viewer.