r872:41d7ac528c3a
Thu, 04 Mar 2010 15:20:59
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -653,20 +653,21 @@ |
| 653 | 653 |
/// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]
|
| 654 | 654 |
/// \f[y_u \ge 0 \quad \forall u \in V\f] |
| 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> |
| 671 | 672 |
#else |
| 672 | 673 |
template <typename GR, |
| ... | ... |
@@ -683,20 +684,18 @@ |
| 683 | 684 |
typedef typename WeightMap::Value Value; |
| 684 | 685 |
|
| 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 = |
| 701 | 700 |
std::numeric_limits<Value>::is_integer ? 4 : 1; |
| 702 | 701 |
|
| ... | ... |
@@ -1324,20 +1323,19 @@ |
| 1324 | 1323 |
|
| 1325 | 1324 |
/// \brief Return \c true if the given edge is in the matching. |
| 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 |
| 1342 | 1340 |
/// edge) incident to the given node in the found matching or \c |
| 1343 | 1341 |
/// INVALID if the node is not covered by the matching or if the |
| ... | ... |
@@ -1418,21 +1416,22 @@ |
| 1418 | 1416 |
/// used to check the result of the algorithm. The dual linear |
| 1419 | 1417 |
/// problem is the following. |
| 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> |
| 1437 | 1436 |
#else |
| 1438 | 1437 |
template <typename GR, |
| ... | ... |
@@ -1449,20 +1448,18 @@ |
| 1449 | 1448 |
typedef typename WeightMap::Value Value; |
| 1450 | 1449 |
|
| 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 = |
| 1467 | 1464 |
std::numeric_limits<Value>::is_integer ? 4 : 1; |
| 1468 | 1465 |
|
| ... | ... |
@@ -2059,20 +2056,19 @@ |
| 2059 | 2056 |
|
| 2060 | 2057 |
/// \brief Return \c true if the given edge is in the matching. |
| 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 |
| 2077 | 2073 |
/// edge) incident to the given node in the found matching or \c |
| 2078 | 2074 |
/// INVALID if the node is not covered by the matching or if the |
| ... | ... |
@@ -231,16 +231,22 @@ |
| 231 | 231 |
check(indeg == 1, "Invalid matching"); |
| 232 | 232 |
++pv; |
| 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; |
| 245 | 251 |
Node v = graph.target(mfm.matching(n)); |
| 246 | 252 |
while (v != n) {
|
| ... | ... |
@@ -279,16 +285,21 @@ |
| 279 | 285 |
for (InArcIt a(graph, n); a != INVALID; ++a) {
|
| 280 | 286 |
if (mfm.matching(graph.source(a)) == a) {
|
| 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; |
| 293 | 304 |
for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
|
| 294 | 305 |
Node u = graph.source(a); |
| ... | ... |
@@ -332,16 +343,22 @@ |
| 332 | 343 |
pv += weight[mwfm.matching(n)]; |
| 333 | 344 |
SmartGraph::Node o = graph.target(mwfm.matching(n)); |
| 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"); |
| 346 | 363 |
|
| 347 | 364 |
SmartGraph::NodeMap<bool> processed(graph, false); |
| ... | ... |
@@ -386,16 +403,22 @@ |
| 386 | 403 |
} |
| 387 | 404 |
} |
| 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"); |
| 400 | 423 |
|
| 401 | 424 |
SmartGraph::NodeMap<bool> processed(graph, false); |
0 comments (0 inline)