r872:41d7ac528c3a
Thu, 04 Mar 2010 15:20:59
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -655,16 +655,17 @@ |
| 655 | 655 |
/// \f[\min \sum_{u \in V}y_u \f]
|
| 656 | 656 |
/// |
| 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>". |
| 669 | 670 |
#ifdef DOXYGEN |
| 670 | 671 |
template <typename GR, typename WM> |
| ... | ... |
@@ -685,16 +686,14 @@ |
| 685 | 686 |
/// The type of the matching map |
| 686 | 687 |
typedef typename Graph::template NodeMap<typename Graph::Arc> |
| 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 |
| 699 | 698 |
/// according to the value type. |
| 700 | 699 |
static const int dualScale = |
| ... | ... |
@@ -1326,16 +1325,15 @@ |
| 1326 | 1325 |
/// |
| 1327 | 1326 |
/// This function returns \c true if the given edge is in the |
| 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. |
| 1340 | 1338 |
/// |
| 1341 | 1339 |
/// This function returns one of the fractional matching arc (or |
| ... | ... |
@@ -1420,17 +1418,18 @@ |
| 1420 | 1418 |
/// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
|
| 1421 | 1419 |
/// \f[\min \sum_{u \in V}y_u \f]
|
| 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>". |
| 1435 | 1434 |
#ifdef DOXYGEN |
| 1436 | 1435 |
template <typename GR, typename WM> |
| ... | ... |
@@ -1451,16 +1450,14 @@ |
| 1451 | 1450 |
/// The type of the matching map |
| 1452 | 1451 |
typedef typename Graph::template NodeMap<typename Graph::Arc> |
| 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 |
| 1465 | 1462 |
/// according to the value type. |
| 1466 | 1463 |
static const int dualScale = |
| ... | ... |
@@ -2061,16 +2058,15 @@ |
| 2061 | 2058 |
/// |
| 2062 | 2059 |
/// This function returns \c true if the given edge is in the |
| 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. |
| 2075 | 2071 |
/// |
| 2076 | 2072 |
/// This function returns one of the fractional matching arc (or |
| ... | ... |
@@ -233,12 +233,18 @@ |
| 233 | 233 |
} else {
|
| 234 | 234 |
check(indeg == 0, "Invalid matching"); |
| 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; |
| 243 | 249 |
if (mfm.matching(n) == INVALID) continue; |
| 244 | 250 |
int num = 1; |
| ... | ... |
@@ -281,12 +287,17 @@ |
| 281 | 287 |
++indeg; |
| 282 | 288 |
} |
| 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) {
|
| 291 | 302 |
if (!mfm.barrier(n)) continue; |
| 292 | 303 |
++anum; |
| ... | ... |
@@ -334,12 +345,18 @@ |
| 334 | 345 |
} else {
|
| 335 | 346 |
check(mwfm.nodeValue(n) == 0, "Invalid matching"); |
| 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 |
} |
| 344 | 361 |
|
| 345 | 362 |
check(pv * mwfm.dualScale == dv * 2, "Wrong duality"); |
| ... | ... |
@@ -388,12 +405,18 @@ |
| 388 | 405 |
check(mwpfm.matching(n) != INVALID, "Invalid perfect matching"); |
| 389 | 406 |
check(indeg == 1, "Invalid perfect matching"); |
| 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 |
} |
| 398 | 421 |
|
| 399 | 422 |
check(pv * mwpfm.dualScale == dv * 2, "Wrong duality"); |
0 comments (0 inline)