113 |
113 |
114 /// \brief Initalize the data structures with an initial matching. |
114 /// \brief Initalize the data structures with an initial matching. |
115 /// |
115 /// |
116 /// It initalizes the data structures with an initial matching. |
116 /// It initalizes the data structures with an initial matching. |
117 template <typename MatchingMap> |
117 template <typename MatchingMap> |
118 void matchingInit(const MatchingMap& matching) { |
118 void matchingInit(const MatchingMap& mm) { |
119 for (ANodeIt it(*graph); it != INVALID; ++it) { |
119 for (ANodeIt it(*graph); it != INVALID; ++it) { |
120 anode_matching[it] = INVALID; |
120 anode_matching[it] = INVALID; |
121 } |
121 } |
122 for (BNodeIt it(*graph); it != INVALID; ++it) { |
122 for (BNodeIt it(*graph); it != INVALID; ++it) { |
123 bnode_matching[it] = INVALID; |
123 bnode_matching[it] = INVALID; |
124 } |
124 } |
125 matching_size = 0; |
125 matching_size = 0; |
126 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
126 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
127 if (matching[it]) { |
127 if (mm[it]) { |
128 ++matching_size; |
128 ++matching_size; |
129 anode_matching[graph->aNode(it)] = it; |
129 anode_matching[graph->aNode(it)] = it; |
130 bnode_matching[graph->bNode(it)] = it; |
130 bnode_matching[graph->bNode(it)] = it; |
131 } |
131 } |
132 } |
132 } |
135 /// \brief Initalize the data structures with an initial matching. |
135 /// \brief Initalize the data structures with an initial matching. |
136 /// |
136 /// |
137 /// It initalizes the data structures with an initial matching. |
137 /// It initalizes the data structures with an initial matching. |
138 /// \return %True when the given map contains really a matching. |
138 /// \return %True when the given map contains really a matching. |
139 template <typename MatchingMap> |
139 template <typename MatchingMap> |
140 void checkedMatchingInit(const MatchingMap& matching) { |
140 void checkedMatchingInit(const MatchingMap& mm) { |
141 for (ANodeIt it(*graph); it != INVALID; ++it) { |
141 for (ANodeIt it(*graph); it != INVALID; ++it) { |
142 anode_matching[it] = INVALID; |
142 anode_matching[it] = INVALID; |
143 } |
143 } |
144 for (BNodeIt it(*graph); it != INVALID; ++it) { |
144 for (BNodeIt it(*graph); it != INVALID; ++it) { |
145 bnode_matching[it] = INVALID; |
145 bnode_matching[it] = INVALID; |
146 } |
146 } |
147 matching_size = 0; |
147 matching_size = 0; |
148 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
148 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
149 if (matching[it]) { |
149 if (mm[it]) { |
150 ++matching_size; |
150 ++matching_size; |
151 if (anode_matching[graph->aNode(it)] != INVALID) { |
151 if (anode_matching[graph->aNode(it)] != INVALID) { |
152 return false; |
152 return false; |
153 } |
153 } |
154 anode_matching[graph->aNode(it)] = it; |
154 anode_matching[graph->aNode(it)] = it; |
185 |
185 |
186 bool success = false; |
186 bool success = false; |
187 |
187 |
188 while (!success && !queue.empty()) { |
188 while (!success && !queue.empty()) { |
189 std::vector<Node> newqueue; |
189 std::vector<Node> newqueue; |
190 for (int i = 0; i < (int)queue.size(); ++i) { |
190 for (int i = 0; i < int(queue.size()); ++i) { |
191 Node anode = queue[i]; |
191 Node anode = queue[i]; |
192 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
192 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
193 Node bnode = graph->bNode(jt); |
193 Node bnode = graph->bNode(jt); |
194 if (breached[bnode]) continue; |
194 if (breached[bnode]) continue; |
195 breached[bnode] = true; |
195 breached[bnode] = true; |
277 } |
277 } |
278 } |
278 } |
279 |
279 |
280 while (!queue.empty()) { |
280 while (!queue.empty()) { |
281 std::vector<Node> newqueue; |
281 std::vector<Node> newqueue; |
282 for (int i = 0; i < (int)queue.size(); ++i) { |
282 for (int i = 0; i < int(queue.size()); ++i) { |
283 Node anode = queue[i]; |
283 Node anode = queue[i]; |
284 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
284 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
285 Node bnode = graph->bNode(jt); |
285 Node bnode = graph->bNode(jt); |
286 if (breached[bnode]) continue; |
286 if (breached[bnode]) continue; |
287 breached[bnode] = true; |
287 breached[bnode] = true; |
361 } |
361 } |
362 } |
362 } |
363 |
363 |
364 while (!queue.empty()) { |
364 while (!queue.empty()) { |
365 std::vector<Node> newqueue; |
365 std::vector<Node> newqueue; |
366 for (int i = 0; i < (int)queue.size(); ++i) { |
366 for (int i = 0; i < int(queue.size()); ++i) { |
367 Node anode = queue[i]; |
367 Node anode = queue[i]; |
368 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
368 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
369 Node bnode = graph->bNode(jt); |
369 Node bnode = graph->bNode(jt); |
370 if (breached[bnode]) continue; |
370 if (breached[bnode]) continue; |
371 breached[bnode] = true; |
371 breached[bnode] = true; |
401 /// |
401 /// |
402 /// Set true all matching uedge in the map. It does not change the |
402 /// Set true all matching uedge in the map. It does not change the |
403 /// value mapped to the other uedges. |
403 /// value mapped to the other uedges. |
404 /// \return The number of the matching edges. |
404 /// \return The number of the matching edges. |
405 template <typename MatchingMap> |
405 template <typename MatchingMap> |
406 int quickMatching(MatchingMap& matching) const { |
406 int quickMatching(MatchingMap& mm) const { |
407 for (ANodeIt it(*graph); it != INVALID; ++it) { |
407 for (ANodeIt it(*graph); it != INVALID; ++it) { |
408 if (anode_matching[it] != INVALID) { |
408 if (anode_matching[it] != INVALID) { |
409 matching[anode_matching[it]] = true; |
409 mm[anode_matching[it]] = true; |
410 } |
410 } |
411 } |
411 } |
412 return matching_size; |
412 return matching_size; |
413 } |
413 } |
414 |
414 |
415 /// \brief Set true all matching uedge in the map and the others to false. |
415 /// \brief Set true all matching uedge in the map and the others to false. |
416 /// |
416 /// |
417 /// Set true all matching uedge in the map and the others to false. |
417 /// Set true all matching uedge in the map and the others to false. |
418 /// \return The number of the matching edges. |
418 /// \return The number of the matching edges. |
419 template <typename MatchingMap> |
419 template <typename MatchingMap> |
420 int matching(MatchingMap& matching) const { |
420 int matching(MatchingMap& mm) const { |
421 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
421 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
422 matching[it] = it == anode_matching[graph->aNode(it)]; |
422 mm[it] = it == anode_matching[graph->aNode(it)]; |
423 } |
423 } |
424 return matching_size; |
424 return matching_size; |
425 } |
425 } |
426 |
426 |
427 |
427 |
681 /// Sets the heap and the cross reference used by algorithm. |
681 /// Sets the heap and the cross reference used by algorithm. |
682 /// If you don't use this function before calling \ref run(), |
682 /// If you don't use this function before calling \ref run(), |
683 /// it will allocate one. The destuctor deallocates this |
683 /// it will allocate one. The destuctor deallocates this |
684 /// automatically allocated map, of course. |
684 /// automatically allocated map, of course. |
685 /// \return \c (*this) |
685 /// \return \c (*this) |
686 MaxWeightedBipartiteMatching& heap(Heap& heap, HeapCrossRef &crossRef) { |
686 MaxWeightedBipartiteMatching& heap(Heap& hp, HeapCrossRef &cr) { |
687 if(local_heap_cross_ref) { |
687 if(local_heap_cross_ref) { |
688 delete _heap_cross_ref; |
688 delete _heap_cross_ref; |
689 local_heap_cross_ref = false; |
689 local_heap_cross_ref = false; |
690 } |
690 } |
691 _heap_cross_ref = &crossRef; |
691 _heap_cross_ref = &cr; |
692 if(local_heap) { |
692 if(local_heap) { |
693 delete _heap; |
693 delete _heap; |
694 local_heap = false; |
694 local_heap = false; |
695 } |
695 } |
696 _heap = &heap; |
696 _heap = &hp; |
697 return *this; |
697 return *this; |
698 } |
698 } |
699 |
699 |
700 /// \name Execution control |
700 /// \name Execution control |
701 /// The simplest way to execute the algorithm is to use |
701 /// The simplest way to execute the algorithm is to use |
887 /// Gives back the potential in the NodeMap. The matching is optimal |
887 /// Gives back the potential in the NodeMap. The matching is optimal |
888 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$ |
888 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$ |
889 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ |
889 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ |
890 /// for each edges. |
890 /// for each edges. |
891 template <typename PotentialMap> |
891 template <typename PotentialMap> |
892 void potential(PotentialMap& potential) const { |
892 void potential(PotentialMap& pt) const { |
893 for (ANodeIt it(*graph); it != INVALID; ++it) { |
893 for (ANodeIt it(*graph); it != INVALID; ++it) { |
894 potential[it] = anode_potential[it]; |
894 pt[it] = anode_potential[it]; |
895 } |
895 } |
896 for (BNodeIt it(*graph); it != INVALID; ++it) { |
896 for (BNodeIt it(*graph); it != INVALID; ++it) { |
897 potential[it] = bnode_potential[it]; |
897 pt[it] = bnode_potential[it]; |
898 } |
898 } |
899 } |
899 } |
900 |
900 |
901 /// \brief Set true all matching uedge in the map. |
901 /// \brief Set true all matching uedge in the map. |
902 /// |
902 /// |
903 /// Set true all matching uedge in the map. It does not change the |
903 /// Set true all matching uedge in the map. It does not change the |
904 /// value mapped to the other uedges. |
904 /// value mapped to the other uedges. |
905 /// \return The number of the matching edges. |
905 /// \return The number of the matching edges. |
906 template <typename MatchingMap> |
906 template <typename MatchingMap> |
907 int quickMatching(MatchingMap& matching) const { |
907 int quickMatching(MatchingMap& mm) const { |
908 for (ANodeIt it(*graph); it != INVALID; ++it) { |
908 for (ANodeIt it(*graph); it != INVALID; ++it) { |
909 if (anode_matching[it] != INVALID) { |
909 if (anode_matching[it] != INVALID) { |
910 matching[anode_matching[it]] = true; |
910 mm[anode_matching[it]] = true; |
911 } |
911 } |
912 } |
912 } |
913 return matching_size; |
913 return matching_size; |
914 } |
914 } |
915 |
915 |
916 /// \brief Set true all matching uedge in the map and the others to false. |
916 /// \brief Set true all matching uedge in the map and the others to false. |
917 /// |
917 /// |
918 /// Set true all matching uedge in the map and the others to false. |
918 /// Set true all matching uedge in the map and the others to false. |
919 /// \return The number of the matching edges. |
919 /// \return The number of the matching edges. |
920 template <typename MatchingMap> |
920 template <typename MatchingMap> |
921 int matching(MatchingMap& matching) const { |
921 int matching(MatchingMap& mm) const { |
922 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
922 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
923 matching[it] = it == anode_matching[graph->aNode(it)]; |
923 mm[it] = it == anode_matching[graph->aNode(it)]; |
924 } |
924 } |
925 return matching_size; |
925 return matching_size; |
926 } |
926 } |
927 |
927 |
928 |
928 |
1252 /// Sets the heap and the cross reference used by algorithm. |
1252 /// Sets the heap and the cross reference used by algorithm. |
1253 /// If you don't use this function before calling \ref run(), |
1253 /// If you don't use this function before calling \ref run(), |
1254 /// it will allocate one. The destuctor deallocates this |
1254 /// it will allocate one. The destuctor deallocates this |
1255 /// automatically allocated map, of course. |
1255 /// automatically allocated map, of course. |
1256 /// \return \c (*this) |
1256 /// \return \c (*this) |
1257 MinCostMaxBipartiteMatching& heap(Heap& heap, HeapCrossRef &crossRef) { |
1257 MinCostMaxBipartiteMatching& heap(Heap& hp, HeapCrossRef &cr) { |
1258 if(local_heap_cross_ref) { |
1258 if(local_heap_cross_ref) { |
1259 delete _heap_cross_ref; |
1259 delete _heap_cross_ref; |
1260 local_heap_cross_ref = false; |
1260 local_heap_cross_ref = false; |
1261 } |
1261 } |
1262 _heap_cross_ref = &crossRef; |
1262 _heap_cross_ref = &cr; |
1263 if(local_heap) { |
1263 if(local_heap) { |
1264 delete _heap; |
1264 delete _heap; |
1265 local_heap = false; |
1265 local_heap = false; |
1266 } |
1266 } |
1267 _heap = &heap; |
1267 _heap = &hp; |
1268 return *this; |
1268 return *this; |
1269 } |
1269 } |
1270 |
1270 |
1271 /// \name Execution control |
1271 /// \name Execution control |
1272 /// The simplest way to execute the algorithm is to use |
1272 /// The simplest way to execute the algorithm is to use |
1440 /// Gives back the potential in the NodeMap. The potential is optimal with |
1440 /// Gives back the potential in the NodeMap. The potential is optimal with |
1441 /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for |
1441 /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for |
1442 /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$ |
1442 /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$ |
1443 /// for each edges. |
1443 /// for each edges. |
1444 template <typename PotentialMap> |
1444 template <typename PotentialMap> |
1445 void potential(PotentialMap& potential) const { |
1445 void potential(PotentialMap& pt) const { |
1446 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1446 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1447 potential[it] = anode_potential[it]; |
1447 pt[it] = anode_potential[it]; |
1448 } |
1448 } |
1449 for (BNodeIt it(*graph); it != INVALID; ++it) { |
1449 for (BNodeIt it(*graph); it != INVALID; ++it) { |
1450 potential[it] = bnode_potential[it]; |
1450 pt[it] = bnode_potential[it]; |
1451 } |
1451 } |
1452 } |
1452 } |
1453 |
1453 |
1454 /// \brief Set true all matching uedge in the map. |
1454 /// \brief Set true all matching uedge in the map. |
1455 /// |
1455 /// |
1456 /// Set true all matching uedge in the map. It does not change the |
1456 /// Set true all matching uedge in the map. It does not change the |
1457 /// value mapped to the other uedges. |
1457 /// value mapped to the other uedges. |
1458 /// \return The number of the matching edges. |
1458 /// \return The number of the matching edges. |
1459 template <typename MatchingMap> |
1459 template <typename MatchingMap> |
1460 int quickMatching(MatchingMap& matching) const { |
1460 int quickMatching(MatchingMap& mm) const { |
1461 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1461 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1462 if (anode_matching[it] != INVALID) { |
1462 if (anode_matching[it] != INVALID) { |
1463 matching[anode_matching[it]] = true; |
1463 mm[anode_matching[it]] = true; |
1464 } |
1464 } |
1465 } |
1465 } |
1466 return matching_size; |
1466 return matching_size; |
1467 } |
1467 } |
1468 |
1468 |
1469 /// \brief Set true all matching uedge in the map and the others to false. |
1469 /// \brief Set true all matching uedge in the map and the others to false. |
1470 /// |
1470 /// |
1471 /// Set true all matching uedge in the map and the others to false. |
1471 /// Set true all matching uedge in the map and the others to false. |
1472 /// \return The number of the matching edges. |
1472 /// \return The number of the matching edges. |
1473 template <typename MatchingMap> |
1473 template <typename MatchingMap> |
1474 int matching(MatchingMap& matching) const { |
1474 int matching(MatchingMap& mm) const { |
1475 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
1475 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
1476 matching[it] = it == anode_matching[graph->aNode(it)]; |
1476 mm[it] = it == anode_matching[graph->aNode(it)]; |
1477 } |
1477 } |
1478 return matching_size; |
1478 return matching_size; |
1479 } |
1479 } |
1480 |
1480 |
1481 |
1481 |