3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BIPARTITE_MATCHING
20 #define LEMON_BIPARTITE_MATCHING
24 #include <lemon/bin_heap.h>
25 #include <lemon/maps.h>
31 ///\brief Maximum matching algorithms in bipartite graphs.
33 ///\note The pr_bipartite_matching.h file also contains algorithms to
34 ///solve maximum cardinality bipartite matching problems.
40 /// \brief Bipartite Max Cardinality Matching algorithm
42 /// Bipartite Max Cardinality Matching algorithm. This class implements
43 /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time
46 /// \note In several cases the push-relabel based algorithms have
47 /// better runtime performance than the augmenting path based ones.
49 /// \see PrBipartiteMatching
50 template <typename BpUGraph>
51 class MaxBipartiteMatching {
54 typedef BpUGraph Graph;
56 typedef typename Graph::Node Node;
57 typedef typename Graph::ANodeIt ANodeIt;
58 typedef typename Graph::BNodeIt BNodeIt;
59 typedef typename Graph::UEdge UEdge;
60 typedef typename Graph::UEdgeIt UEdgeIt;
61 typedef typename Graph::IncEdgeIt IncEdgeIt;
63 typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
64 typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;
69 /// \brief Constructor.
71 /// Constructor of the algorithm.
72 MaxBipartiteMatching(const BpUGraph& _graph)
73 : anode_matching(_graph), bnode_matching(_graph), graph(&_graph) {}
75 /// \name Execution control
76 /// The simplest way to execute the algorithm is to use
77 /// one of the member functions called \c run().
79 /// If you need more control on the execution,
80 /// first you must call \ref init() or one alternative for it.
81 /// Finally \ref start() will perform the matching computation or
82 /// with step-by-step execution you can augment the solution.
86 /// \brief Initalize the data structures.
88 /// It initalizes the data structures and creates an empty matching.
90 for (ANodeIt it(*graph); it != INVALID; ++it) {
91 anode_matching[it] = INVALID;
93 for (BNodeIt it(*graph); it != INVALID; ++it) {
94 bnode_matching[it] = INVALID;
99 /// \brief Initalize the data structures.
101 /// It initalizes the data structures and creates a greedy
102 /// matching. From this matching sometimes it is faster to get
103 /// the matching than from the initial empty matching.
106 for (BNodeIt it(*graph); it != INVALID; ++it) {
107 bnode_matching[it] = INVALID;
109 for (ANodeIt it(*graph); it != INVALID; ++it) {
110 anode_matching[it] = INVALID;
111 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
112 if (bnode_matching[graph->bNode(jt)] == INVALID) {
113 anode_matching[it] = jt;
114 bnode_matching[graph->bNode(jt)] = jt;
122 /// \brief Initalize the data structures with an initial matching.
124 /// It initalizes the data structures with an initial matching.
125 template <typename MatchingMap>
126 void matchingInit(const MatchingMap& mm) {
127 for (ANodeIt it(*graph); it != INVALID; ++it) {
128 anode_matching[it] = INVALID;
130 for (BNodeIt it(*graph); it != INVALID; ++it) {
131 bnode_matching[it] = INVALID;
134 for (UEdgeIt it(*graph); it != INVALID; ++it) {
137 anode_matching[graph->aNode(it)] = it;
138 bnode_matching[graph->bNode(it)] = it;
143 /// \brief Initalize the data structures with an initial matching.
145 /// It initalizes the data structures with an initial matching.
146 /// \return %True when the given map contains really a matching.
147 template <typename MatchingMap>
148 void checkedMatchingInit(const MatchingMap& mm) {
149 for (ANodeIt it(*graph); it != INVALID; ++it) {
150 anode_matching[it] = INVALID;
152 for (BNodeIt it(*graph); it != INVALID; ++it) {
153 bnode_matching[it] = INVALID;
156 for (UEdgeIt it(*graph); it != INVALID; ++it) {
159 if (anode_matching[graph->aNode(it)] != INVALID) {
162 anode_matching[graph->aNode(it)] = it;
163 if (bnode_matching[graph->aNode(it)] != INVALID) {
166 bnode_matching[graph->bNode(it)] = it;
172 /// \brief An augmenting phase of the Hopcroft-Karp algorithm
174 /// It runs an augmenting phase of the Hopcroft-Karp
175 /// algorithm. This phase finds maximum count of edge disjoint
176 /// augmenting paths and augments on these paths. The algorithm
177 /// consists at most of \f$ O(\sqrt{n}) \f$ phase and one phase is
178 /// \f$ O(e) \f$ long.
181 typename Graph::template ANodeMap<bool> areached(*graph, false);
182 typename Graph::template BNodeMap<bool> breached(*graph, false);
184 typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
186 std::vector<Node> queue, bqueue;
187 for (ANodeIt it(*graph); it != INVALID; ++it) {
188 if (anode_matching[it] == INVALID) {
194 bool success = false;
196 while (!success && !queue.empty()) {
197 std::vector<Node> newqueue;
198 for (int i = 0; i < int(queue.size()); ++i) {
199 Node anode = queue[i];
200 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
201 Node bnode = graph->bNode(jt);
202 if (breached[bnode]) continue;
203 breached[bnode] = true;
205 if (bnode_matching[bnode] == INVALID) {
206 bqueue.push_back(bnode);
209 Node newanode = graph->aNode(bnode_matching[bnode]);
210 if (!areached[newanode]) {
211 areached[newanode] = true;
212 newqueue.push_back(newanode);
217 queue.swap(newqueue);
222 typename Graph::template ANodeMap<bool> aused(*graph, false);
224 for (int i = 0; i < int(bqueue.size()); ++i) {
225 Node bnode = bqueue[i];
229 while (bnode != INVALID) {
230 UEdge uedge = bpred[bnode];
231 Node anode = graph->aNode(uedge);
238 bnode = anode_matching[anode] != INVALID ?
239 graph->bNode(anode_matching[anode]) : INVALID;
246 while (bnode != INVALID) {
247 UEdge uedge = bpred[bnode];
248 Node anode = graph->aNode(uedge);
250 bnode_matching[bnode] = uedge;
252 bnode = anode_matching[anode] != INVALID ?
253 graph->bNode(anode_matching[anode]) : INVALID;
255 anode_matching[anode] = uedge;
266 /// \brief An augmenting phase of the Ford-Fulkerson algorithm
268 /// It runs an augmenting phase of the Ford-Fulkerson
269 /// algorithm. This phase finds only one augmenting path and
270 /// augments only on this paths. The algorithm consists at most
271 /// of \f$ O(n) \f$ simple phase and one phase is at most
272 /// \f$ O(e) \f$ long.
273 bool simpleAugment() {
275 typename Graph::template ANodeMap<bool> areached(*graph, false);
276 typename Graph::template BNodeMap<bool> breached(*graph, false);
278 typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
280 std::vector<Node> queue;
281 for (ANodeIt it(*graph); it != INVALID; ++it) {
282 if (anode_matching[it] == INVALID) {
288 while (!queue.empty()) {
289 std::vector<Node> newqueue;
290 for (int i = 0; i < int(queue.size()); ++i) {
291 Node anode = queue[i];
292 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
293 Node bnode = graph->bNode(jt);
294 if (breached[bnode]) continue;
295 breached[bnode] = true;
297 if (bnode_matching[bnode] == INVALID) {
298 while (bnode != INVALID) {
299 UEdge uedge = bpred[bnode];
300 anode = graph->aNode(uedge);
302 bnode_matching[bnode] = uedge;
304 bnode = anode_matching[anode] != INVALID ?
305 graph->bNode(anode_matching[anode]) : INVALID;
307 anode_matching[anode] = uedge;
313 Node newanode = graph->aNode(bnode_matching[bnode]);
314 if (!areached[newanode]) {
315 areached[newanode] = true;
316 newqueue.push_back(newanode);
321 queue.swap(newqueue);
327 /// \brief Starts the algorithm.
329 /// Starts the algorithm. It runs augmenting phases until the optimal
330 /// solution reached.
335 /// \brief Runs the algorithm.
337 /// It just initalize the algorithm and then start it.
345 /// \name Query Functions
346 /// The result of the %Matching algorithm can be obtained using these
348 /// Before the use of these functions,
349 /// either run() or start() must be called.
353 /// \brief Set true all matching uedge in the map.
355 /// Set true all matching uedge in the map. It does not change the
356 /// value mapped to the other uedges.
357 /// \return The number of the matching edges.
358 template <typename MatchingMap>
359 int quickMatching(MatchingMap& mm) const {
360 for (ANodeIt it(*graph); it != INVALID; ++it) {
361 if (anode_matching[it] != INVALID) {
362 mm.set(anode_matching[it], true);
365 return matching_size;
368 /// \brief Set true all matching uedge in the map and the others to false.
370 /// Set true all matching uedge in the map and the others to false.
371 /// \return The number of the matching edges.
372 template <typename MatchingMap>
373 int matching(MatchingMap& mm) const {
374 for (UEdgeIt it(*graph); it != INVALID; ++it) {
375 mm.set(it, it == anode_matching[graph->aNode(it)]);
377 return matching_size;
380 ///Gives back the matching in an ANodeMap.
382 ///Gives back the matching in an ANodeMap. The parameter should
383 ///be a write ANodeMap of UEdge values.
384 ///\return The number of the matching edges.
385 template<class MatchingMap>
386 int aMatching(MatchingMap& mm) const {
387 for (ANodeIt it(*graph); it != INVALID; ++it) {
388 mm.set(it, anode_matching[it]);
390 return matching_size;
393 ///Gives back the matching in a BNodeMap.
395 ///Gives back the matching in a BNodeMap. The parameter should
396 ///be a write BNodeMap of UEdge values.
397 ///\return The number of the matching edges.
398 template<class MatchingMap>
399 int bMatching(MatchingMap& mm) const {
400 for (BNodeIt it(*graph); it != INVALID; ++it) {
401 mm.set(it, bnode_matching[it]);
403 return matching_size;
406 /// \brief Return true if the given uedge is in the matching.
408 /// It returns true if the given uedge is in the matching.
409 bool matchingEdge(const UEdge& edge) const {
410 return anode_matching[graph->aNode(edge)] == edge;
413 /// \brief Returns the matching edge from the node.
415 /// Returns the matching edge from the node. If there is not such
416 /// edge it gives back \c INVALID.
417 UEdge matchingEdge(const Node& node) const {
418 if (graph->aNode(node)) {
419 return anode_matching[node];
421 return bnode_matching[node];
425 /// \brief Gives back the number of the matching edges.
427 /// Gives back the number of the matching edges.
428 int matchingSize() const {
429 return matching_size;
432 /// \brief Returns a minimum covering of the nodes.
434 /// The minimum covering set problem is the dual solution of the
435 /// maximum bipartite matching. It provides a solution for this
436 /// problem what is proof of the optimality of the matching.
437 /// \return The size of the cover set.
438 template <typename CoverMap>
439 int coverSet(CoverMap& covering) const {
441 typename Graph::template ANodeMap<bool> areached(*graph, false);
442 typename Graph::template BNodeMap<bool> breached(*graph, false);
444 std::vector<Node> queue;
445 for (ANodeIt it(*graph); it != INVALID; ++it) {
446 if (anode_matching[it] == INVALID) {
451 while (!queue.empty()) {
452 std::vector<Node> newqueue;
453 for (int i = 0; i < int(queue.size()); ++i) {
454 Node anode = queue[i];
455 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
456 Node bnode = graph->bNode(jt);
457 if (breached[bnode]) continue;
458 breached[bnode] = true;
459 if (bnode_matching[bnode] != INVALID) {
460 Node newanode = graph->aNode(bnode_matching[bnode]);
461 if (!areached[newanode]) {
462 areached[newanode] = true;
463 newqueue.push_back(newanode);
468 queue.swap(newqueue);
472 for (ANodeIt it(*graph); it != INVALID; ++it) {
473 covering.set(it, !areached[it] && anode_matching[it] != INVALID);
474 if (!areached[it] && anode_matching[it] != INVALID) {
478 for (BNodeIt it(*graph); it != INVALID; ++it) {
479 covering.set(it, breached[it]);
487 /// \brief Gives back a barrier on the A-nodes
489 /// The barrier is s subset of the nodes on the same side of the
490 /// graph, which size minus its neighbours is exactly the
491 /// unmatched nodes on the A-side.
492 /// \retval barrier A WriteMap on the ANodes with bool value.
493 template <typename BarrierMap>
494 void aBarrier(BarrierMap& barrier) const {
496 typename Graph::template ANodeMap<bool> areached(*graph, false);
497 typename Graph::template BNodeMap<bool> breached(*graph, false);
499 std::vector<Node> queue;
500 for (ANodeIt it(*graph); it != INVALID; ++it) {
501 if (anode_matching[it] == INVALID) {
506 while (!queue.empty()) {
507 std::vector<Node> newqueue;
508 for (int i = 0; i < int(queue.size()); ++i) {
509 Node anode = queue[i];
510 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
511 Node bnode = graph->bNode(jt);
512 if (breached[bnode]) continue;
513 breached[bnode] = true;
514 if (bnode_matching[bnode] != INVALID) {
515 Node newanode = graph->aNode(bnode_matching[bnode]);
516 if (!areached[newanode]) {
517 areached[newanode] = true;
518 newqueue.push_back(newanode);
523 queue.swap(newqueue);
526 for (ANodeIt it(*graph); it != INVALID; ++it) {
527 barrier.set(it, areached[it] || anode_matching[it] == INVALID);
531 /// \brief Gives back a barrier on the B-nodes
533 /// The barrier is s subset of the nodes on the same side of the
534 /// graph, which size minus its neighbours is exactly the
535 /// unmatched nodes on the B-side.
536 /// \retval barrier A WriteMap on the BNodes with bool value.
537 template <typename BarrierMap>
538 void bBarrier(BarrierMap& barrier) const {
540 typename Graph::template ANodeMap<bool> areached(*graph, false);
541 typename Graph::template BNodeMap<bool> breached(*graph, false);
543 std::vector<Node> queue;
544 for (ANodeIt it(*graph); it != INVALID; ++it) {
545 if (anode_matching[it] == INVALID) {
550 while (!queue.empty()) {
551 std::vector<Node> newqueue;
552 for (int i = 0; i < int(queue.size()); ++i) {
553 Node anode = queue[i];
554 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
555 Node bnode = graph->bNode(jt);
556 if (breached[bnode]) continue;
557 breached[bnode] = true;
558 if (bnode_matching[bnode] != INVALID) {
559 Node newanode = graph->aNode(bnode_matching[bnode]);
560 if (!areached[newanode]) {
561 areached[newanode] = true;
562 newqueue.push_back(newanode);
567 queue.swap(newqueue);
570 for (BNodeIt it(*graph); it != INVALID; ++it) {
571 barrier.set(it, !breached[it]);
579 ANodeMatchingMap anode_matching;
580 BNodeMatchingMap bnode_matching;
587 /// \ingroup matching
589 /// \brief Maximum cardinality bipartite matching
591 /// This function calculates the maximum cardinality matching
592 /// in a bipartite graph. It gives back the matching in an undirected
595 /// \param graph The bipartite graph.
596 /// \return The size of the matching.
597 template <typename BpUGraph>
598 int maxBipartiteMatching(const BpUGraph& graph) {
599 MaxBipartiteMatching<BpUGraph> bpmatching(graph);
601 return bpmatching.matchingSize();
604 /// \ingroup matching
606 /// \brief Maximum cardinality bipartite matching
608 /// This function calculates the maximum cardinality matching
609 /// in a bipartite graph. It gives back the matching in an undirected
612 /// \param graph The bipartite graph.
613 /// \retval matching The ANodeMap of UEdges which will be set to covered
614 /// matching undirected edge.
615 /// \return The size of the matching.
616 template <typename BpUGraph, typename MatchingMap>
617 int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) {
618 MaxBipartiteMatching<BpUGraph> bpmatching(graph);
620 bpmatching.aMatching(matching);
621 return bpmatching.matchingSize();
624 /// \ingroup matching
626 /// \brief Maximum cardinality bipartite matching
628 /// This function calculates the maximum cardinality matching
629 /// in a bipartite graph. It gives back the matching in an undirected
632 /// \param graph The bipartite graph.
633 /// \retval matching The ANodeMap of UEdges which will be set to covered
634 /// matching undirected edge.
635 /// \retval barrier The BNodeMap of bools which will be set to a barrier
636 /// of the BNode-set.
637 /// \return The size of the matching.
638 template <typename BpUGraph, typename MatchingMap, typename BarrierMap>
639 int maxBipartiteMatching(const BpUGraph& graph,
640 MatchingMap& matching, BarrierMap& barrier) {
641 MaxBipartiteMatching<BpUGraph> bpmatching(graph);
643 bpmatching.aMatching(matching);
644 bpmatching.bBarrier(barrier);
645 return bpmatching.matchingSize();
648 /// \brief Default traits class for weighted bipartite matching algoritms.
650 /// Default traits class for weighted bipartite matching algoritms.
651 /// \param _BpUGraph The bipartite undirected graph type.
652 /// \param _WeightMap Type of weight map.
653 template <typename _BpUGraph, typename _WeightMap>
654 struct WeightedBipartiteMatchingDefaultTraits {
655 /// \brief The type of the weight of the undirected edges.
656 typedef typename _WeightMap::Value Value;
658 /// The undirected bipartite graph type the algorithm runs on.
659 typedef _BpUGraph BpUGraph;
661 /// The map of the edges weights
662 typedef _WeightMap WeightMap;
664 /// \brief The cross reference type used by heap.
666 /// The cross reference type used by heap.
667 /// Usually it is \c Graph::NodeMap<int>.
668 typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;
670 /// \brief Instantiates a HeapCrossRef.
672 /// This function instantiates a \ref HeapCrossRef.
673 /// \param graph is the graph, to which we would like to define the
675 static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
676 return new HeapCrossRef(graph);
679 /// \brief The heap type used by weighted matching algorithms.
681 /// The heap type used by weighted matching algorithms. It should
682 /// minimize the priorities and the heap's key type is the graph's
683 /// anode graph's node.
686 typedef BinHeap<Value, HeapCrossRef> Heap;
688 /// \brief Instantiates a Heap.
690 /// This function instantiates a \ref Heap.
691 /// \param crossref The cross reference of the heap.
692 static Heap *createHeap(HeapCrossRef& crossref) {
693 return new Heap(crossref);
699 /// \ingroup matching
701 /// \brief Bipartite Max Weighted Matching algorithm
703 /// This class implements the bipartite Max Weighted Matching
704 /// algorithm. It uses the successive shortest path algorithm to
705 /// calculate the maximum weighted matching in the bipartite
706 /// graph. The algorithm can be used also to calculate the maximum
707 /// cardinality maximum weighted matching. The time complexity
708 /// of the algorithm is \f$ O(ne\log(n)) \f$ with the default binary
709 /// heap implementation but this can be improved to
710 /// \f$ O(n^2\log(n)+ne) \f$ if we use fibonacci heaps.
712 /// The algorithm also provides a potential function on the nodes
713 /// which a dual solution of the matching algorithm and it can be
714 /// used to proof the optimality of the given pimal solution.
716 template <typename _BpUGraph, typename _WeightMap, typename _Traits>
718 template <typename _BpUGraph,
719 typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>,
720 typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
722 class MaxWeightedBipartiteMatching {
725 typedef _Traits Traits;
726 typedef typename Traits::BpUGraph BpUGraph;
727 typedef typename Traits::WeightMap WeightMap;
728 typedef typename Traits::Value Value;
732 typedef typename Traits::HeapCrossRef HeapCrossRef;
733 typedef typename Traits::Heap Heap;
736 typedef typename BpUGraph::Node Node;
737 typedef typename BpUGraph::ANodeIt ANodeIt;
738 typedef typename BpUGraph::BNodeIt BNodeIt;
739 typedef typename BpUGraph::UEdge UEdge;
740 typedef typename BpUGraph::UEdgeIt UEdgeIt;
741 typedef typename BpUGraph::IncEdgeIt IncEdgeIt;
743 typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
744 typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;
746 typedef typename BpUGraph::template ANodeMap<Value> ANodePotentialMap;
747 typedef typename BpUGraph::template BNodeMap<Value> BNodePotentialMap;
752 /// \brief \ref Exception for uninitialized parameters.
754 /// This error represents problems in the initialization
755 /// of the parameters of the algorithms.
756 class UninitializedParameter : public lemon::UninitializedParameter {
758 virtual const char* what() const throw() {
759 return "lemon::MaxWeightedBipartiteMatching::UninitializedParameter";
763 ///\name Named template parameters
767 template <class H, class CR>
768 struct DefHeapTraits : public Traits {
769 typedef CR HeapCrossRef;
771 static HeapCrossRef *createHeapCrossRef(const BpUGraph &) {
772 throw UninitializedParameter();
774 static Heap *createHeap(HeapCrossRef &) {
775 throw UninitializedParameter();
779 /// \brief \ref named-templ-param "Named parameter" for setting heap
780 /// and cross reference type
782 /// \ref named-templ-param "Named parameter" for setting heap and cross
784 template <class H, class CR = typename BpUGraph::template NodeMap<int> >
786 : public MaxWeightedBipartiteMatching<BpUGraph, WeightMap,
787 DefHeapTraits<H, CR> > {
788 typedef MaxWeightedBipartiteMatching<BpUGraph, WeightMap,
789 DefHeapTraits<H, CR> > Create;
792 template <class H, class CR>
793 struct DefStandardHeapTraits : public Traits {
794 typedef CR HeapCrossRef;
796 static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
797 return new HeapCrossRef(graph);
799 static Heap *createHeap(HeapCrossRef &crossref) {
800 return new Heap(crossref);
804 /// \brief \ref named-templ-param "Named parameter" for setting heap and
805 /// cross reference type with automatic allocation
807 /// \ref named-templ-param "Named parameter" for setting heap and cross
808 /// reference type. It can allocate the heap and the cross reference
809 /// object if the cross reference's constructor waits for the graph as
810 /// parameter and the heap's constructor waits for the cross reference.
811 template <class H, class CR = typename BpUGraph::template NodeMap<int> >
812 struct DefStandardHeap
813 : public MaxWeightedBipartiteMatching<BpUGraph, WeightMap,
814 DefStandardHeapTraits<H, CR> > {
815 typedef MaxWeightedBipartiteMatching<BpUGraph, WeightMap,
816 DefStandardHeapTraits<H, CR> >
823 /// \brief Constructor.
825 /// Constructor of the algorithm.
826 MaxWeightedBipartiteMatching(const BpUGraph& _graph,
827 const WeightMap& _weight)
828 : graph(&_graph), weight(&_weight),
829 anode_matching(_graph), bnode_matching(_graph),
830 anode_potential(_graph), bnode_potential(_graph),
831 _heap_cross_ref(0), local_heap_cross_ref(false),
832 _heap(0), local_heap(0) {}
834 /// \brief Destructor.
836 /// Destructor of the algorithm.
837 ~MaxWeightedBipartiteMatching() {
841 /// \brief Sets the heap and the cross reference used by algorithm.
843 /// Sets the heap and the cross reference used by algorithm.
844 /// If you don't use this function before calling \ref run(),
845 /// it will allocate one. The destuctor deallocates this
846 /// automatically allocated map, of course.
847 /// \return \c (*this)
848 MaxWeightedBipartiteMatching& heap(Heap& hp, HeapCrossRef &cr) {
849 if(local_heap_cross_ref) {
850 delete _heap_cross_ref;
851 local_heap_cross_ref = false;
853 _heap_cross_ref = &cr;
862 /// \name Execution control
863 /// The simplest way to execute the algorithm is to use
864 /// one of the member functions called \c run().
866 /// If you need more control on the execution,
867 /// first you must call \ref init() or one alternative for it.
868 /// Finally \ref start() will perform the matching computation or
869 /// with step-by-step execution you can augment the solution.
873 /// \brief Initalize the data structures.
875 /// It initalizes the data structures and creates an empty matching.
878 for (ANodeIt it(*graph); it != INVALID; ++it) {
879 anode_matching[it] = INVALID;
880 anode_potential[it] = 0;
882 for (BNodeIt it(*graph); it != INVALID; ++it) {
883 bnode_matching[it] = INVALID;
884 bnode_potential[it] = 0;
885 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
886 if ((*weight)[jt] > bnode_potential[it]) {
887 bnode_potential[it] = (*weight)[jt];
896 /// \brief An augmenting phase of the weighted matching algorithm
898 /// It runs an augmenting phase of the weighted matching
899 /// algorithm. This phase finds the best augmenting path and
900 /// augments only on this paths.
902 /// The algorithm consists at most
903 /// of \f$ O(n) \f$ phase and one phase is \f$ O(n\log(n)+e) \f$
904 /// long with Fibonacci heap or \f$ O((n+e)\log(n)) \f$ long
905 /// with binary heap.
906 /// \param decrease If the given parameter true the matching value
907 /// can be decreased in the augmenting phase. If we would like
908 /// to calculate the maximum cardinality maximum weighted matching
909 /// then we should let the algorithm to decrease the matching
910 /// value in order to increase the number of the matching edges.
911 bool augment(bool decrease = false) {
913 typename BpUGraph::template BNodeMap<Value> bdist(*graph);
914 typename BpUGraph::template BNodeMap<UEdge> bpred(*graph, INVALID);
916 Node bestNode = INVALID;
920 for (ANodeIt it(*graph); it != INVALID; ++it) {
921 (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
924 for (ANodeIt it(*graph); it != INVALID; ++it) {
925 if (anode_matching[it] == INVALID) {
931 while (!_heap->empty()) {
932 Node anode = _heap->top();
933 Value avalue = _heap->prio();
935 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
936 if (jt == anode_matching[anode]) continue;
937 Node bnode = graph->bNode(jt);
938 Value bvalue = avalue - (*weight)[jt] +
939 anode_potential[anode] + bnode_potential[bnode];
940 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
941 bdist[bnode] = bvalue;
944 if (bvalue > bdistMax) {
947 if (bnode_matching[bnode] != INVALID) {
948 Node newanode = graph->aNode(bnode_matching[bnode]);
949 switch (_heap->state(newanode)) {
951 _heap->push(newanode, bvalue);
954 if (bvalue < (*_heap)[newanode]) {
955 _heap->decrease(newanode, bvalue);
958 case Heap::POST_HEAP:
962 if (bestNode == INVALID ||
963 bnode_potential[bnode] - bvalue > bestValue) {
964 bestValue = bnode_potential[bnode] - bvalue;
971 if (bestNode == INVALID || (!decrease && bestValue < 0)) {
975 matching_value += bestValue;
978 for (BNodeIt it(*graph); it != INVALID; ++it) {
979 if (bpred[it] != INVALID) {
980 bnode_potential[it] -= bdist[it];
982 bnode_potential[it] -= bdistMax;
985 for (ANodeIt it(*graph); it != INVALID; ++it) {
986 if (anode_matching[it] != INVALID) {
987 Node bnode = graph->bNode(anode_matching[it]);
988 if (bpred[bnode] != INVALID) {
989 anode_potential[it] += bdist[bnode];
991 anode_potential[it] += bdistMax;
996 while (bestNode != INVALID) {
997 UEdge uedge = bpred[bestNode];
998 Node anode = graph->aNode(uedge);
1000 bnode_matching[bestNode] = uedge;
1001 if (anode_matching[anode] != INVALID) {
1002 bestNode = graph->bNode(anode_matching[anode]);
1006 anode_matching[anode] = uedge;
1013 /// \brief Starts the algorithm.
1015 /// Starts the algorithm. It runs augmenting phases until the
1016 /// optimal solution reached.
1018 /// \param maxCardinality If the given value is true it will
1019 /// calculate the maximum cardinality maximum matching instead of
1020 /// the maximum matching.
1021 void start(bool maxCardinality = false) {
1022 while (augment(maxCardinality)) {}
1025 /// \brief Runs the algorithm.
1027 /// It just initalize the algorithm and then start it.
1029 /// \param maxCardinality If the given value is true it will
1030 /// calculate the maximum cardinality maximum matching instead of
1031 /// the maximum matching.
1032 void run(bool maxCardinality = false) {
1034 start(maxCardinality);
1039 /// \name Query Functions
1040 /// The result of the %Matching algorithm can be obtained using these
1042 /// Before the use of these functions,
1043 /// either run() or start() must be called.
1047 /// \brief Gives back the potential in the NodeMap
1049 /// Gives back the potential in the NodeMap. The matching is optimal
1050 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
1051 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
1053 template <typename PotentialMap>
1054 void potential(PotentialMap& pt) const {
1055 for (ANodeIt it(*graph); it != INVALID; ++it) {
1056 pt.set(it, anode_potential[it]);
1058 for (BNodeIt it(*graph); it != INVALID; ++it) {
1059 pt.set(it, bnode_potential[it]);
1063 /// \brief Set true all matching uedge in the map.
1065 /// Set true all matching uedge in the map. It does not change the
1066 /// value mapped to the other uedges.
1067 /// \return The number of the matching edges.
1068 template <typename MatchingMap>
1069 int quickMatching(MatchingMap& mm) const {
1070 for (ANodeIt it(*graph); it != INVALID; ++it) {
1071 if (anode_matching[it] != INVALID) {
1072 mm.set(anode_matching[it], true);
1075 return matching_size;
1078 /// \brief Set true all matching uedge in the map and the others to false.
1080 /// Set true all matching uedge in the map and the others to false.
1081 /// \return The number of the matching edges.
1082 template <typename MatchingMap>
1083 int matching(MatchingMap& mm) const {
1084 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1085 mm.set(it, it == anode_matching[graph->aNode(it)]);
1087 return matching_size;
1090 ///Gives back the matching in an ANodeMap.
1092 ///Gives back the matching in an ANodeMap. The parameter should
1093 ///be a write ANodeMap of UEdge values.
1094 ///\return The number of the matching edges.
1095 template<class MatchingMap>
1096 int aMatching(MatchingMap& mm) const {
1097 for (ANodeIt it(*graph); it != INVALID; ++it) {
1098 mm.set(it, anode_matching[it]);
1100 return matching_size;
1103 ///Gives back the matching in a BNodeMap.
1105 ///Gives back the matching in a BNodeMap. The parameter should
1106 ///be a write BNodeMap of UEdge values.
1107 ///\return The number of the matching edges.
1108 template<class MatchingMap>
1109 int bMatching(MatchingMap& mm) const {
1110 for (BNodeIt it(*graph); it != INVALID; ++it) {
1111 mm.set(it, bnode_matching[it]);
1113 return matching_size;
1117 /// \brief Return true if the given uedge is in the matching.
1119 /// It returns true if the given uedge is in the matching.
1120 bool matchingEdge(const UEdge& edge) const {
1121 return anode_matching[graph->aNode(edge)] == edge;
1124 /// \brief Returns the matching edge from the node.
1126 /// Returns the matching edge from the node. If there is not such
1127 /// edge it gives back \c INVALID.
1128 UEdge matchingEdge(const Node& node) const {
1129 if (graph->aNode(node)) {
1130 return anode_matching[node];
1132 return bnode_matching[node];
1136 /// \brief Gives back the sum of weights of the matching edges.
1138 /// Gives back the sum of weights of the matching edges.
1139 Value matchingValue() const {
1140 return matching_value;
1143 /// \brief Gives back the number of the matching edges.
1145 /// Gives back the number of the matching edges.
1146 int matchingSize() const {
1147 return matching_size;
1154 void initStructures() {
1155 if (!_heap_cross_ref) {
1156 local_heap_cross_ref = true;
1157 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
1161 _heap = Traits::createHeap(*_heap_cross_ref);
1165 void destroyStructures() {
1166 if (local_heap_cross_ref) delete _heap_cross_ref;
1167 if (local_heap) delete _heap;
1173 const BpUGraph *graph;
1174 const WeightMap* weight;
1176 ANodeMatchingMap anode_matching;
1177 BNodeMatchingMap bnode_matching;
1179 ANodePotentialMap anode_potential;
1180 BNodePotentialMap bnode_potential;
1182 Value matching_value;
1185 HeapCrossRef *_heap_cross_ref;
1186 bool local_heap_cross_ref;
1193 /// \ingroup matching
1195 /// \brief Maximum weighted bipartite matching
1197 /// This function calculates the maximum weighted matching
1198 /// in a bipartite graph. It gives back the matching in an undirected
1201 /// \param graph The bipartite graph.
1202 /// \param weight The undirected edge map which contains the weights.
1203 /// \retval matching The undirected edge map which will be set to
1205 /// \return The value of the matching.
1206 template <typename BpUGraph, typename WeightMap, typename MatchingMap>
1207 typename WeightMap::Value
1208 maxWeightedBipartiteMatching(const BpUGraph& graph, const WeightMap& weight,
1209 MatchingMap& matching) {
1210 MaxWeightedBipartiteMatching<BpUGraph, WeightMap>
1211 bpmatching(graph, weight);
1213 bpmatching.matching(matching);
1214 return bpmatching.matchingValue();
1217 /// \ingroup matching
1219 /// \brief Maximum weighted maximum cardinality bipartite matching
1221 /// This function calculates the maximum weighted of the maximum cardinality
1222 /// matchings of a bipartite graph. It gives back the matching in an
1223 /// undirected edge map.
1225 /// \param graph The bipartite graph.
1226 /// \param weight The undirected edge map which contains the weights.
1227 /// \retval matching The undirected edge map which will be set to
1229 /// \return The value of the matching.
1230 template <typename BpUGraph, typename WeightMap, typename MatchingMap>
1231 typename WeightMap::Value
1232 maxWeightedMaxBipartiteMatching(const BpUGraph& graph,
1233 const WeightMap& weight,
1234 MatchingMap& matching) {
1235 MaxWeightedBipartiteMatching<BpUGraph, WeightMap>
1236 bpmatching(graph, weight);
1237 bpmatching.run(true);
1238 bpmatching.matching(matching);
1239 return bpmatching.matchingValue();
1242 /// \brief Default traits class for minimum cost bipartite matching
1245 /// Default traits class for minimum cost bipartite matching
1248 /// \param _BpUGraph The bipartite undirected graph
1251 /// \param _CostMap Type of cost map.
1252 template <typename _BpUGraph, typename _CostMap>
1253 struct MinCostMaxBipartiteMatchingDefaultTraits {
1254 /// \brief The type of the cost of the undirected edges.
1255 typedef typename _CostMap::Value Value;
1257 /// The undirected bipartite graph type the algorithm runs on.
1258 typedef _BpUGraph BpUGraph;
1260 /// The map of the edges costs
1261 typedef _CostMap CostMap;
1263 /// \brief The cross reference type used by heap.
1265 /// The cross reference type used by heap.
1266 /// Usually it is \c Graph::NodeMap<int>.
1267 typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;
1269 /// \brief Instantiates a HeapCrossRef.
1271 /// This function instantiates a \ref HeapCrossRef.
1272 /// \param graph is the graph, to which we would like to define the
1274 static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
1275 return new HeapCrossRef(graph);
1278 /// \brief The heap type used by costed matching algorithms.
1280 /// The heap type used by costed matching algorithms. It should
1281 /// minimize the priorities and the heap's key type is the graph's
1282 /// anode graph's node.
1285 typedef BinHeap<Value, HeapCrossRef> Heap;
1287 /// \brief Instantiates a Heap.
1289 /// This function instantiates a \ref Heap.
1290 /// \param crossref The cross reference of the heap.
1291 static Heap *createHeap(HeapCrossRef& crossref) {
1292 return new Heap(crossref);
1298 /// \ingroup matching
1300 /// \brief Bipartite Min Cost Matching algorithm
1302 /// This class implements the bipartite Min Cost Matching algorithm.
1303 /// It uses the successive shortest path algorithm to calculate the
1304 /// minimum cost maximum matching in the bipartite graph. The time
1305 /// complexity of the algorithm is \f$ O(ne\log(n)) \f$ with the
1306 /// default binary heap implementation but this can be improved to
1307 /// \f$ O(n^2\log(n)+ne) \f$ if we use fibonacci heaps.
1309 /// The algorithm also provides a potential function on the nodes
1310 /// which a dual solution of the matching algorithm and it can be
1311 /// used to proof the optimality of the given pimal solution.
1313 template <typename _BpUGraph, typename _CostMap, typename _Traits>
1315 template <typename _BpUGraph,
1316 typename _CostMap = typename _BpUGraph::template UEdgeMap<int>,
1317 typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
1319 class MinCostMaxBipartiteMatching {
1322 typedef _Traits Traits;
1323 typedef typename Traits::BpUGraph BpUGraph;
1324 typedef typename Traits::CostMap CostMap;
1325 typedef typename Traits::Value Value;
1329 typedef typename Traits::HeapCrossRef HeapCrossRef;
1330 typedef typename Traits::Heap Heap;
1333 typedef typename BpUGraph::Node Node;
1334 typedef typename BpUGraph::ANodeIt ANodeIt;
1335 typedef typename BpUGraph::BNodeIt BNodeIt;
1336 typedef typename BpUGraph::UEdge UEdge;
1337 typedef typename BpUGraph::UEdgeIt UEdgeIt;
1338 typedef typename BpUGraph::IncEdgeIt IncEdgeIt;
1340 typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
1341 typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;
1343 typedef typename BpUGraph::template ANodeMap<Value> ANodePotentialMap;
1344 typedef typename BpUGraph::template BNodeMap<Value> BNodePotentialMap;
1349 /// \brief \ref Exception for uninitialized parameters.
1351 /// This error represents problems in the initialization
1352 /// of the parameters of the algorithms.
1353 class UninitializedParameter : public lemon::UninitializedParameter {
1355 virtual const char* what() const throw() {
1356 return "lemon::MinCostMaxBipartiteMatching::UninitializedParameter";
1360 ///\name Named template parameters
1364 template <class H, class CR>
1365 struct DefHeapTraits : public Traits {
1366 typedef CR HeapCrossRef;
1368 static HeapCrossRef *createHeapCrossRef(const BpUGraph &) {
1369 throw UninitializedParameter();
1371 static Heap *createHeap(HeapCrossRef &) {
1372 throw UninitializedParameter();
1376 /// \brief \ref named-templ-param "Named parameter" for setting heap
1377 /// and cross reference type
1379 /// \ref named-templ-param "Named parameter" for setting heap and cross
1381 template <class H, class CR = typename BpUGraph::template NodeMap<int> >
1383 : public MinCostMaxBipartiteMatching<BpUGraph, CostMap,
1384 DefHeapTraits<H, CR> > {
1385 typedef MinCostMaxBipartiteMatching<BpUGraph, CostMap,
1386 DefHeapTraits<H, CR> > Create;
1389 template <class H, class CR>
1390 struct DefStandardHeapTraits : public Traits {
1391 typedef CR HeapCrossRef;
1393 static HeapCrossRef *createHeapCrossRef(const BpUGraph &graph) {
1394 return new HeapCrossRef(graph);
1396 static Heap *createHeap(HeapCrossRef &crossref) {
1397 return new Heap(crossref);
1401 /// \brief \ref named-templ-param "Named parameter" for setting heap and
1402 /// cross reference type with automatic allocation
1404 /// \ref named-templ-param "Named parameter" for setting heap and cross
1405 /// reference type. It can allocate the heap and the cross reference
1406 /// object if the cross reference's constructor waits for the graph as
1407 /// parameter and the heap's constructor waits for the cross reference.
1408 template <class H, class CR = typename BpUGraph::template NodeMap<int> >
1409 struct DefStandardHeap
1410 : public MinCostMaxBipartiteMatching<BpUGraph, CostMap,
1411 DefStandardHeapTraits<H, CR> > {
1412 typedef MinCostMaxBipartiteMatching<BpUGraph, CostMap,
1413 DefStandardHeapTraits<H, CR> >
1420 /// \brief Constructor.
1422 /// Constructor of the algorithm.
1423 MinCostMaxBipartiteMatching(const BpUGraph& _graph,
1424 const CostMap& _cost)
1425 : graph(&_graph), cost(&_cost),
1426 anode_matching(_graph), bnode_matching(_graph),
1427 anode_potential(_graph), bnode_potential(_graph),
1428 _heap_cross_ref(0), local_heap_cross_ref(false),
1429 _heap(0), local_heap(0) {}
1431 /// \brief Destructor.
1433 /// Destructor of the algorithm.
1434 ~MinCostMaxBipartiteMatching() {
1435 destroyStructures();
1438 /// \brief Sets the heap and the cross reference used by algorithm.
1440 /// Sets the heap and the cross reference used by algorithm.
1441 /// If you don't use this function before calling \ref run(),
1442 /// it will allocate one. The destuctor deallocates this
1443 /// automatically allocated map, of course.
1444 /// \return \c (*this)
1445 MinCostMaxBipartiteMatching& heap(Heap& hp, HeapCrossRef &cr) {
1446 if(local_heap_cross_ref) {
1447 delete _heap_cross_ref;
1448 local_heap_cross_ref = false;
1450 _heap_cross_ref = &cr;
1459 /// \name Execution control
1460 /// The simplest way to execute the algorithm is to use
1461 /// one of the member functions called \c run().
1463 /// If you need more control on the execution,
1464 /// first you must call \ref init() or one alternative for it.
1465 /// Finally \ref start() will perform the matching computation or
1466 /// with step-by-step execution you can augment the solution.
1470 /// \brief Initalize the data structures.
1472 /// It initalizes the data structures and creates an empty matching.
1475 for (ANodeIt it(*graph); it != INVALID; ++it) {
1476 anode_matching[it] = INVALID;
1477 anode_potential[it] = 0;
1479 for (BNodeIt it(*graph); it != INVALID; ++it) {
1480 bnode_matching[it] = INVALID;
1481 bnode_potential[it] = 0;
1488 /// \brief An augmenting phase of the costed matching algorithm
1490 /// It runs an augmenting phase of the matching algorithm. The
1491 /// phase finds the best augmenting path and augments only on this
1494 /// The algorithm consists at most
1495 /// of \f$ O(n) \f$ phase and one phase is \f$ O(n\log(n)+e) \f$
1496 /// long with Fibonacci heap or \f$ O((n+e)\log(n)) \f$ long
1497 /// with binary heap.
1500 typename BpUGraph::template BNodeMap<Value> bdist(*graph);
1501 typename BpUGraph::template BNodeMap<UEdge> bpred(*graph, INVALID);
1503 Node bestNode = INVALID;
1504 Value bestValue = 0;
1507 for (ANodeIt it(*graph); it != INVALID; ++it) {
1508 (*_heap_cross_ref)[it] = Heap::PRE_HEAP;
1511 for (ANodeIt it(*graph); it != INVALID; ++it) {
1512 if (anode_matching[it] == INVALID) {
1518 while (!_heap->empty()) {
1519 Node anode = _heap->top();
1520 Value avalue = _heap->prio();
1522 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
1523 if (jt == anode_matching[anode]) continue;
1524 Node bnode = graph->bNode(jt);
1525 Value bvalue = avalue + (*cost)[jt] +
1526 anode_potential[anode] - bnode_potential[bnode];
1527 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
1528 bdist[bnode] = bvalue;
1531 if (bvalue > bdistMax) {
1534 if (bnode_matching[bnode] != INVALID) {
1535 Node newanode = graph->aNode(bnode_matching[bnode]);
1536 switch (_heap->state(newanode)) {
1537 case Heap::PRE_HEAP:
1538 _heap->push(newanode, bvalue);
1541 if (bvalue < (*_heap)[newanode]) {
1542 _heap->decrease(newanode, bvalue);
1545 case Heap::POST_HEAP:
1549 if (bestNode == INVALID ||
1550 bvalue + bnode_potential[bnode] < bestValue) {
1551 bestValue = bvalue + bnode_potential[bnode];
1558 if (bestNode == INVALID) {
1562 matching_cost += bestValue;
1565 for (BNodeIt it(*graph); it != INVALID; ++it) {
1566 if (bpred[it] != INVALID) {
1567 bnode_potential[it] += bdist[it];
1569 bnode_potential[it] += bdistMax;
1572 for (ANodeIt it(*graph); it != INVALID; ++it) {
1573 if (anode_matching[it] != INVALID) {
1574 Node bnode = graph->bNode(anode_matching[it]);
1575 if (bpred[bnode] != INVALID) {
1576 anode_potential[it] += bdist[bnode];
1578 anode_potential[it] += bdistMax;
1583 while (bestNode != INVALID) {
1584 UEdge uedge = bpred[bestNode];
1585 Node anode = graph->aNode(uedge);
1587 bnode_matching[bestNode] = uedge;
1588 if (anode_matching[anode] != INVALID) {
1589 bestNode = graph->bNode(anode_matching[anode]);
1593 anode_matching[anode] = uedge;
1600 /// \brief Starts the algorithm.
1602 /// Starts the algorithm. It runs augmenting phases until the
1603 /// optimal solution reached.
1605 while (augment()) {}
1608 /// \brief Runs the algorithm.
1610 /// It just initalize the algorithm and then start it.
1618 /// \name Query Functions
1619 /// The result of the %Matching algorithm can be obtained using these
1621 /// Before the use of these functions,
1622 /// either run() or start() must be called.
1626 /// \brief Gives back the potential in the NodeMap
1628 /// Gives back the potential in the NodeMap. The matching is optimal
1629 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
1630 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
1632 template <typename PotentialMap>
1633 void potential(PotentialMap& pt) const {
1634 for (ANodeIt it(*graph); it != INVALID; ++it) {
1635 pt.set(it, anode_potential[it]);
1637 for (BNodeIt it(*graph); it != INVALID; ++it) {
1638 pt.set(it, bnode_potential[it]);
1642 /// \brief Set true all matching uedge in the map.
1644 /// Set true all matching uedge in the map. It does not change the
1645 /// value mapped to the other uedges.
1646 /// \return The number of the matching edges.
1647 template <typename MatchingMap>
1648 int quickMatching(MatchingMap& mm) const {
1649 for (ANodeIt it(*graph); it != INVALID; ++it) {
1650 if (anode_matching[it] != INVALID) {
1651 mm.set(anode_matching[it], true);
1654 return matching_size;
1657 /// \brief Set true all matching uedge in the map and the others to false.
1659 /// Set true all matching uedge in the map and the others to false.
1660 /// \return The number of the matching edges.
1661 template <typename MatchingMap>
1662 int matching(MatchingMap& mm) const {
1663 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1664 mm.set(it, it == anode_matching[graph->aNode(it)]);
1666 return matching_size;
1669 /// \brief Gives back the matching in an ANodeMap.
1671 /// Gives back the matching in an ANodeMap. The parameter should
1672 /// be a write ANodeMap of UEdge values.
1673 /// \return The number of the matching edges.
1674 template<class MatchingMap>
1675 int aMatching(MatchingMap& mm) const {
1676 for (ANodeIt it(*graph); it != INVALID; ++it) {
1677 mm.set(it, anode_matching[it]);
1679 return matching_size;
1682 /// \brief Gives back the matching in a BNodeMap.
1684 /// Gives back the matching in a BNodeMap. The parameter should
1685 /// be a write BNodeMap of UEdge values.
1686 /// \return The number of the matching edges.
1687 template<class MatchingMap>
1688 int bMatching(MatchingMap& mm) const {
1689 for (BNodeIt it(*graph); it != INVALID; ++it) {
1690 mm.set(it, bnode_matching[it]);
1692 return matching_size;
1695 /// \brief Return true if the given uedge is in the matching.
1697 /// It returns true if the given uedge is in the matching.
1698 bool matchingEdge(const UEdge& edge) const {
1699 return anode_matching[graph->aNode(edge)] == edge;
1702 /// \brief Returns the matching edge from the node.
1704 /// Returns the matching edge from the node. If there is not such
1705 /// edge it gives back \c INVALID.
1706 UEdge matchingEdge(const Node& node) const {
1707 if (graph->aNode(node)) {
1708 return anode_matching[node];
1710 return bnode_matching[node];
1714 /// \brief Gives back the sum of costs of the matching edges.
1716 /// Gives back the sum of costs of the matching edges.
1717 Value matchingCost() const {
1718 return matching_cost;
1721 /// \brief Gives back the number of the matching edges.
1723 /// Gives back the number of the matching edges.
1724 int matchingSize() const {
1725 return matching_size;
1732 void initStructures() {
1733 if (!_heap_cross_ref) {
1734 local_heap_cross_ref = true;
1735 _heap_cross_ref = Traits::createHeapCrossRef(*graph);
1739 _heap = Traits::createHeap(*_heap_cross_ref);
1743 void destroyStructures() {
1744 if (local_heap_cross_ref) delete _heap_cross_ref;
1745 if (local_heap) delete _heap;
1751 const BpUGraph *graph;
1752 const CostMap* cost;
1754 ANodeMatchingMap anode_matching;
1755 BNodeMatchingMap bnode_matching;
1757 ANodePotentialMap anode_potential;
1758 BNodePotentialMap bnode_potential;
1760 Value matching_cost;
1763 HeapCrossRef *_heap_cross_ref;
1764 bool local_heap_cross_ref;
1771 /// \ingroup matching
1773 /// \brief Minimum cost maximum cardinality bipartite matching
1775 /// This function calculates the maximum cardinality matching with
1776 /// minimum cost of a bipartite graph. It gives back the matching in
1777 /// an undirected edge map.
1779 /// \param graph The bipartite graph.
1780 /// \param cost The undirected edge map which contains the costs.
1781 /// \retval matching The undirected edge map which will be set to
1783 /// \return The cost of the matching.
1784 template <typename BpUGraph, typename CostMap, typename MatchingMap>
1785 typename CostMap::Value
1786 minCostMaxBipartiteMatching(const BpUGraph& graph,
1787 const CostMap& cost,
1788 MatchingMap& matching) {
1789 MinCostMaxBipartiteMatching<BpUGraph, CostMap>
1790 bpmatching(graph, cost);
1792 bpmatching.matching(matching);
1793 return bpmatching.matchingCost();