r872:41d7ac528c3a
Thu, 04 Mar 2010 15:20:59
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -657,12 +657,13 @@ |
| 657 | 657 |
/// The algorithm can be executed with the run() function. |
| 658 | 658 |
/// After it the matching (the primal solution) and the dual solution |
| 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. |
| 667 | 668 |
/// \tparam WM The type edge weight map. The default type is |
| 668 | 669 |
/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
| ... | ... |
@@ -687,12 +688,10 @@ |
| 687 | 688 |
MatchingMap; |
| 688 | 689 |
|
| 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 |
| 697 | 696 |
/// |
| 698 | 697 |
/// Scaling factor for dual solution. It is equal to 4 or 1 |
| ... | ... |
@@ -1328,12 +1327,11 @@ |
| 1328 | 1327 |
/// found matching. The result is scaled by \ref primalScale |
| 1329 | 1328 |
/// "primal scale". |
| 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 |
|
| 1338 | 1336 |
/// \brief Return the fractional matching arc (or edge) incident |
| 1339 | 1337 |
/// to the given node. |
| ... | ... |
@@ -1422,13 +1420,14 @@ |
| 1422 | 1420 |
/// |
| 1423 | 1421 |
/// The algorithm can be executed with the run() function. |
| 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 |
/// |
|
| 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. |
| 1433 | 1432 |
/// \tparam WM The type edge weight map. The default type is |
| 1434 | 1433 |
/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
| ... | ... |
@@ -1453,12 +1452,10 @@ |
| 1453 | 1452 |
MatchingMap; |
| 1454 | 1453 |
|
| 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 |
| 1463 | 1460 |
/// |
| 1464 | 1461 |
/// Scaling factor for dual solution. It is equal to 4 or 1 |
| ... | ... |
@@ -2063,12 +2060,11 @@ |
| 2063 | 2060 |
/// found matching. The result is scaled by \ref primalScale |
| 2064 | 2061 |
/// "primal scale". |
| 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 |
|
| 2073 | 2069 |
/// \brief Return the fractional matching arc (or edge) incident |
| 2074 | 2070 |
/// to the given node. |
| ... | ... |
@@ -235,8 +235,14 @@ |
| 235 | 235 |
} |
| 236 | 236 |
} |
| 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) {
|
| 241 | 247 |
if (processed[n]) continue; |
| 242 | 248 |
processed[n] = true; |
| ... | ... |
@@ -283,8 +289,13 @@ |
| 283 | 289 |
} |
| 284 | 290 |
check(mfm.matching(n) != INVALID, "Invalid matching"); |
| 285 | 291 |
check(indeg == 1, "Invalid matching"); |
| 286 | 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"); |
|
| 297 |
} |
|
| 287 | 298 |
} else {
|
| 288 | 299 |
int anum = 0, bnum = 0; |
| 289 | 300 |
SmartGraph::NodeMap<bool> neighbours(graph, false); |
| 290 | 301 |
for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
|
| ... | ... |
@@ -336,8 +347,14 @@ |
| 336 | 347 |
check(indeg == 0, "Invalid matching"); |
| 337 | 348 |
} |
| 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) {
|
| 342 | 359 |
dv += mwfm.nodeValue(n); |
| 343 | 360 |
} |
| ... | ... |
@@ -390,8 +407,14 @@ |
| 390 | 407 |
pv += weight[mwpfm.matching(n)]; |
| 391 | 408 |
SmartGraph::Node o = graph.target(mwpfm.matching(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) {
|
| 396 | 419 |
dv += mwpfm.nodeValue(n); |
| 397 | 420 |
} |
0 comments (0 inline)