1.1 --- a/lemon/bipartite_matching.h Thu Jul 26 13:59:12 2007 +0000
1.2 +++ b/lemon/bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
1.3 @@ -29,6 +29,9 @@
1.4 ///\ingroup matching
1.5 ///\file
1.6 ///\brief Maximum matching algorithms in bipartite graphs.
1.7 +///
1.8 +///\note The pr_bipartite_matching.h file also contains algorithms to
1.9 +///solve maximum cardinality bipartite matching problems.
1.10
1.11 namespace lemon {
1.12
1.13 @@ -39,6 +42,11 @@
1.14 /// Bipartite Max Cardinality Matching algorithm. This class implements
1.15 /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time
1.16 /// complexity.
1.17 + ///
1.18 + /// \note In several cases the push-relabel based algorithms have
1.19 + /// better runtime performance than the augmenting path based ones.
1.20 + ///
1.21 + /// \see PrBipartiteMatching
1.22 template <typename BpUGraph>
1.23 class MaxBipartiteMatching {
1.24 protected:
1.25 @@ -342,10 +350,64 @@
1.26
1.27 ///@{
1.28
1.29 - /// \brief Returns an minimum covering of the nodes.
1.30 + /// \brief Set true all matching uedge in the map.
1.31 + ///
1.32 + /// Set true all matching uedge in the map. It does not change the
1.33 + /// value mapped to the other uedges.
1.34 + /// \return The number of the matching edges.
1.35 + template <typename MatchingMap>
1.36 + int quickMatching(MatchingMap& mm) const {
1.37 + for (ANodeIt it(*graph); it != INVALID; ++it) {
1.38 + if (anode_matching[it] != INVALID) {
1.39 + mm[anode_matching[it]] = true;
1.40 + }
1.41 + }
1.42 + return matching_size;
1.43 + }
1.44 +
1.45 + /// \brief Set true all matching uedge in the map and the others to false.
1.46 + ///
1.47 + /// Set true all matching uedge in the map and the others to false.
1.48 + /// \return The number of the matching edges.
1.49 + template <typename MatchingMap>
1.50 + int matching(MatchingMap& mm) const {
1.51 + for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.52 + mm[it] = it == anode_matching[graph->aNode(it)];
1.53 + }
1.54 + return matching_size;
1.55 + }
1.56 +
1.57 +
1.58 + /// \brief Return true if the given uedge is in the matching.
1.59 + ///
1.60 + /// It returns true if the given uedge is in the matching.
1.61 + bool matchingEdge(const UEdge& edge) const {
1.62 + return anode_matching[graph->aNode(edge)] == edge;
1.63 + }
1.64 +
1.65 + /// \brief Returns the matching edge from the node.
1.66 + ///
1.67 + /// Returns the matching edge from the node. If there is not such
1.68 + /// edge it gives back \c INVALID.
1.69 + UEdge matchingEdge(const Node& node) const {
1.70 + if (graph->aNode(node)) {
1.71 + return anode_matching[node];
1.72 + } else {
1.73 + return bnode_matching[node];
1.74 + }
1.75 + }
1.76 +
1.77 + /// \brief Gives back the number of the matching edges.
1.78 + ///
1.79 + /// Gives back the number of the matching edges.
1.80 + int matchingSize() const {
1.81 + return matching_size;
1.82 + }
1.83 +
1.84 + /// \brief Returns a minimum covering of the nodes.
1.85 ///
1.86 /// The minimum covering set problem is the dual solution of the
1.87 - /// maximum bipartite matching. It provides an solution for this
1.88 + /// maximum bipartite matching. It provides a solution for this
1.89 /// problem what is proof of the optimality of the matching.
1.90 /// \return The size of the cover set.
1.91 template <typename CoverMap>
1.92 @@ -397,58 +459,92 @@
1.93 return size;
1.94 }
1.95
1.96 - /// \brief Set true all matching uedge in the map.
1.97 - ///
1.98 - /// Set true all matching uedge in the map. It does not change the
1.99 - /// value mapped to the other uedges.
1.100 - /// \return The number of the matching edges.
1.101 - template <typename MatchingMap>
1.102 - int quickMatching(MatchingMap& mm) const {
1.103 + /// \brief Gives back a barrier on the A-nodes
1.104 +
1.105 + /// The barrier is s subset of the nodes on the same side of the
1.106 + /// graph, which size minus its neighbours is exactly the
1.107 + /// unmatched nodes on the A-side.
1.108 + /// \retval barrier A WriteMap on the ANodes with bool value.
1.109 + template <typename BarrierMap>
1.110 + void aBarrier(BarrierMap& barrier) const {
1.111 +
1.112 + typename Graph::template ANodeMap<bool> areached(*graph, false);
1.113 + typename Graph::template BNodeMap<bool> breached(*graph, false);
1.114 +
1.115 + std::vector<Node> queue;
1.116 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.117 - if (anode_matching[it] != INVALID) {
1.118 - mm[anode_matching[it]] = true;
1.119 + if (anode_matching[it] == INVALID) {
1.120 + queue.push_back(it);
1.121 }
1.122 }
1.123 - return matching_size;
1.124 - }
1.125
1.126 - /// \brief Set true all matching uedge in the map and the others to false.
1.127 - ///
1.128 - /// Set true all matching uedge in the map and the others to false.
1.129 - /// \return The number of the matching edges.
1.130 - template <typename MatchingMap>
1.131 - int matching(MatchingMap& mm) const {
1.132 - for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.133 - mm[it] = it == anode_matching[graph->aNode(it)];
1.134 + while (!queue.empty()) {
1.135 + std::vector<Node> newqueue;
1.136 + for (int i = 0; i < int(queue.size()); ++i) {
1.137 + Node anode = queue[i];
1.138 + for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
1.139 + Node bnode = graph->bNode(jt);
1.140 + if (breached[bnode]) continue;
1.141 + breached[bnode] = true;
1.142 + if (bnode_matching[bnode] != INVALID) {
1.143 + Node newanode = graph->aNode(bnode_matching[bnode]);
1.144 + if (!areached[newanode]) {
1.145 + areached[newanode] = true;
1.146 + newqueue.push_back(newanode);
1.147 + }
1.148 + }
1.149 + }
1.150 + }
1.151 + queue.swap(newqueue);
1.152 }
1.153 - return matching_size;
1.154 - }
1.155
1.156 -
1.157 - /// \brief Return true if the given uedge is in the matching.
1.158 - ///
1.159 - /// It returns true if the given uedge is in the matching.
1.160 - bool matchingEdge(const UEdge& edge) const {
1.161 - return anode_matching[graph->aNode(edge)] == edge;
1.162 - }
1.163 -
1.164 - /// \brief Returns the matching edge from the node.
1.165 - ///
1.166 - /// Returns the matching edge from the node. If there is not such
1.167 - /// edge it gives back \c INVALID.
1.168 - UEdge matchingEdge(const Node& node) const {
1.169 - if (graph->aNode(node)) {
1.170 - return anode_matching[node];
1.171 - } else {
1.172 - return bnode_matching[node];
1.173 + for (ANodeIt it(*graph); it != INVALID; ++it) {
1.174 + barrier[it] = areached[it] || anode_matching[it] == INVALID;
1.175 }
1.176 }
1.177
1.178 - /// \brief Gives back the number of the matching edges.
1.179 - ///
1.180 - /// Gives back the number of the matching edges.
1.181 - int matchingSize() const {
1.182 - return matching_size;
1.183 + /// \brief Gives back a barrier on the B-nodes
1.184 +
1.185 + /// The barrier is s subset of the nodes on the same side of the
1.186 + /// graph, which size minus its neighbours is exactly the
1.187 + /// unmatched nodes on the B-side.
1.188 + /// \retval barrier A WriteMap on the BNodes with bool value.
1.189 + template <typename BarrierMap>
1.190 + void bBarrier(BarrierMap& barrier) const {
1.191 +
1.192 + typename Graph::template ANodeMap<bool> areached(*graph, false);
1.193 + typename Graph::template BNodeMap<bool> breached(*graph, false);
1.194 +
1.195 + std::vector<Node> queue;
1.196 + for (ANodeIt it(*graph); it != INVALID; ++it) {
1.197 + if (anode_matching[it] == INVALID) {
1.198 + queue.push_back(it);
1.199 + }
1.200 + }
1.201 +
1.202 + while (!queue.empty()) {
1.203 + std::vector<Node> newqueue;
1.204 + for (int i = 0; i < int(queue.size()); ++i) {
1.205 + Node anode = queue[i];
1.206 + for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
1.207 + Node bnode = graph->bNode(jt);
1.208 + if (breached[bnode]) continue;
1.209 + breached[bnode] = true;
1.210 + if (bnode_matching[bnode] != INVALID) {
1.211 + Node newanode = graph->aNode(bnode_matching[bnode]);
1.212 + if (!areached[newanode]) {
1.213 + areached[newanode] = true;
1.214 + newqueue.push_back(newanode);
1.215 + }
1.216 + }
1.217 + }
1.218 + }
1.219 + queue.swap(newqueue);
1.220 + }
1.221 +
1.222 + for (BNodeIt it(*graph); it != INVALID; ++it) {
1.223 + barrier[it] = !breached[it];
1.224 + }
1.225 }
1.226
1.227 /// @}