Redesign of augmenting path based matching
authordeba
Tue, 28 Aug 2007 13:58:54 +0000
changeset 2466feb7974cf4ec
parent 2465 df09310da558
child 2467 2025a571895e
Redesign of augmenting path based matching
Small bug fix in the push-relabel based
lemon/bipartite_matching.h
lemon/pr_bipartite_matching.h
     1.1 --- a/lemon/bipartite_matching.h	Sat Aug 25 10:12:03 2007 +0000
     1.2 +++ b/lemon/bipartite_matching.h	Tue Aug 28 13:58:54 2007 +0000
     1.3 @@ -69,8 +69,8 @@
     1.4      /// \brief Constructor.
     1.5      ///
     1.6      /// Constructor of the algorithm. 
     1.7 -    MaxBipartiteMatching(const BpUGraph& _graph) 
     1.8 -      : anode_matching(_graph), bnode_matching(_graph), graph(&_graph) {}
     1.9 +    MaxBipartiteMatching(const BpUGraph& graph) 
    1.10 +      : _matching(graph), _rmatching(graph), _reached(graph), _graph(&graph) {}
    1.11  
    1.12      /// \name Execution control
    1.13      /// The simplest way to execute the algorithm is to use
    1.14 @@ -87,13 +87,15 @@
    1.15      ///
    1.16      /// It initalizes the data structures and creates an empty matching.
    1.17      void init() {
    1.18 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
    1.19 -        anode_matching[it] = INVALID;
    1.20 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
    1.21 +        _matching.set(it, INVALID);
    1.22        }
    1.23 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
    1.24 -        bnode_matching[it] = INVALID;
    1.25 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
    1.26 +        _rmatching.set(it, INVALID);
    1.27 +	_reached.set(it, -1);
    1.28        }
    1.29 -      matching_size = 0;
    1.30 +      _size = 0;
    1.31 +      _phase = -1;
    1.32      }
    1.33  
    1.34      /// \brief Initalize the data structures.
    1.35 @@ -102,21 +104,24 @@
    1.36      /// matching.  From this matching sometimes it is faster to get
    1.37      /// the matching than from the initial empty matching.
    1.38      void greedyInit() {
    1.39 -      matching_size = 0;
    1.40 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
    1.41 -        bnode_matching[it] = INVALID;
    1.42 +      _size = 0;
    1.43 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
    1.44 +        _rmatching.set(it, INVALID);
    1.45 +	_reached.set(it, 0);
    1.46        }
    1.47 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
    1.48 -        anode_matching[it] = INVALID;
    1.49 -        for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
    1.50 -          if (bnode_matching[graph->bNode(jt)] == INVALID) {
    1.51 -            anode_matching[it] = jt;
    1.52 -            bnode_matching[graph->bNode(jt)] = jt;
    1.53 -            ++matching_size;
    1.54 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
    1.55 +        _matching[it] = INVALID;
    1.56 +        for (IncEdgeIt jt(*_graph, it); jt != INVALID; ++jt) {
    1.57 +          if (_rmatching[_graph->bNode(jt)] == INVALID) {
    1.58 +            _matching.set(it, jt);
    1.59 +	    _rmatching.set(_graph->bNode(jt), jt);
    1.60 +	    _reached.set(it, -1);
    1.61 +            ++_size;
    1.62              break;
    1.63            }
    1.64          }
    1.65        }
    1.66 +      _phase = 0;
    1.67      }
    1.68  
    1.69      /// \brief Initalize the data structures with an initial matching.
    1.70 @@ -124,20 +129,23 @@
    1.71      /// It initalizes the data structures with an initial matching.
    1.72      template <typename MatchingMap>
    1.73      void matchingInit(const MatchingMap& mm) {
    1.74 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
    1.75 -        anode_matching[it] = INVALID;
    1.76 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
    1.77 +        _matching.set(it, INVALID);
    1.78        }
    1.79 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
    1.80 -        bnode_matching[it] = INVALID;
    1.81 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
    1.82 +        _rmatching.set(it, INVALID);
    1.83 +	_reached.set(it, 0);
    1.84        }
    1.85 -      matching_size = 0;
    1.86 -      for (UEdgeIt it(*graph); it != INVALID; ++it) {
    1.87 +      _size = 0;
    1.88 +      for (UEdgeIt it(*_graph); it != INVALID; ++it) {
    1.89          if (mm[it]) {
    1.90 -          ++matching_size;
    1.91 -          anode_matching[graph->aNode(it)] = it;
    1.92 -          bnode_matching[graph->bNode(it)] = it;
    1.93 +          ++_size;
    1.94 +          _matching.set(_graph->aNode(it), it);
    1.95 +          _rmatching.set(_graph->bNode(it), it);
    1.96 +	  _reached.set(it, 0);
    1.97          }
    1.98        }
    1.99 +      _phase = 0;
   1.100      }
   1.101  
   1.102      /// \brief Initalize the data structures with an initial matching.
   1.103 @@ -145,185 +153,188 @@
   1.104      /// It initalizes the data structures with an initial matching.
   1.105      /// \return %True when the given map contains really a matching.
   1.106      template <typename MatchingMap>
   1.107 -    void checkedMatchingInit(const MatchingMap& mm) {
   1.108 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.109 -        anode_matching[it] = INVALID;
   1.110 +    bool checkedMatchingInit(const MatchingMap& mm) {
   1.111 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
   1.112 +        _matching.set(it, INVALID);
   1.113        }
   1.114 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
   1.115 -        bnode_matching[it] = INVALID;
   1.116 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
   1.117 +        _rmatching.set(it, INVALID);
   1.118 +	_reached.set(it, 0);
   1.119        }
   1.120 -      matching_size = 0;
   1.121 -      for (UEdgeIt it(*graph); it != INVALID; ++it) {
   1.122 +      _size = 0;
   1.123 +      for (UEdgeIt it(*_graph); it != INVALID; ++it) {
   1.124          if (mm[it]) {
   1.125 -          ++matching_size;
   1.126 -          if (anode_matching[graph->aNode(it)] != INVALID) {
   1.127 +          ++_size;
   1.128 +          if (_matching[_graph->aNode(it)] != INVALID) {
   1.129              return false;
   1.130            }
   1.131 -          anode_matching[graph->aNode(it)] = it;
   1.132 -          if (bnode_matching[graph->aNode(it)] != INVALID) {
   1.133 +          _matching.set(_graph->aNode(it), it);
   1.134 +          if (_matching[_graph->bNode(it)] != INVALID) {
   1.135              return false;
   1.136            }
   1.137 -          bnode_matching[graph->bNode(it)] = it;
   1.138 +          _matching.set(_graph->bNode(it), it);
   1.139 +	  _reached.set(_graph->bNode(it), -1);
   1.140          }
   1.141        }
   1.142 +      _phase = 0;
   1.143 +      return true;
   1.144 +    }
   1.145 +
   1.146 +  private:
   1.147 +    
   1.148 +    bool _find_path(Node anode, int maxlevel,
   1.149 +		    typename Graph::template BNodeMap<int>& level) {
   1.150 +      for (IncEdgeIt it(*_graph, anode); it != INVALID; ++it) {
   1.151 +	Node bnode = _graph->bNode(it); 
   1.152 +	if (level[bnode] == maxlevel) {
   1.153 +	  level.set(bnode, -1);
   1.154 +	  if (maxlevel == 0) {
   1.155 +	    _matching.set(anode, it);
   1.156 +	    _rmatching.set(bnode, it);
   1.157 +	    return true;
   1.158 +	  } else {
   1.159 +	    Node nnode = _graph->aNode(_rmatching[bnode]);
   1.160 +	    if (_find_path(nnode, maxlevel - 1, level)) {
   1.161 +	      _matching.set(anode, it);
   1.162 +	      _rmatching.set(bnode, it);
   1.163 +	      return true;
   1.164 +	    }
   1.165 +	  }
   1.166 +	}
   1.167 +      }
   1.168        return false;
   1.169      }
   1.170  
   1.171 +  public:
   1.172 +
   1.173      /// \brief An augmenting phase of the Hopcroft-Karp algorithm
   1.174      ///
   1.175      /// It runs an augmenting phase of the Hopcroft-Karp
   1.176 -    /// algorithm. This phase finds maximum count of edge disjoint
   1.177 -    /// augmenting paths and augments on these paths. The algorithm
   1.178 -    /// consists at most of \f$ O(\sqrt{n}) \f$ phase and one phase is
   1.179 -    /// \f$ O(e) \f$ long.
   1.180 +    /// algorithm. This phase finds maximal edge disjoint augmenting
   1.181 +    /// paths and augments on these paths. The algorithm consists at
   1.182 +    /// most of \f$ O(\sqrt{n}) \f$ phase and one phase is \f$ O(e)
   1.183 +    /// \f$ long.
   1.184      bool augment() {
   1.185  
   1.186 -      typename Graph::template ANodeMap<bool> areached(*graph, false);
   1.187 -      typename Graph::template BNodeMap<bool> breached(*graph, false);
   1.188 +      ++_phase;
   1.189 +      
   1.190 +      typename Graph::template BNodeMap<int> _level(*_graph, -1);
   1.191 +      typename Graph::template ANodeMap<bool> _found(*_graph, false);
   1.192  
   1.193 -      typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
   1.194 -
   1.195 -      std::vector<Node> queue, bqueue;
   1.196 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.197 -        if (anode_matching[it] == INVALID) {
   1.198 +      std::vector<Node> queue, aqueue;
   1.199 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
   1.200 +        if (_rmatching[it] == INVALID) {
   1.201            queue.push_back(it);
   1.202 -          areached[it] = true;
   1.203 +          _reached.set(it, _phase);
   1.204 +	  _level.set(it, 0);
   1.205          }
   1.206        }
   1.207  
   1.208        bool success = false;
   1.209  
   1.210 +      int level = 0;
   1.211        while (!success && !queue.empty()) {
   1.212 -        std::vector<Node> newqueue;
   1.213 +        std::vector<Node> nqueue;
   1.214          for (int i = 0; i < int(queue.size()); ++i) {
   1.215 -          Node anode = queue[i];
   1.216 -          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
   1.217 -            Node bnode = graph->bNode(jt);
   1.218 -            if (breached[bnode]) continue;
   1.219 -            breached[bnode] = true;
   1.220 -            bpred[bnode] = jt;
   1.221 -            if (bnode_matching[bnode] == INVALID) {
   1.222 -              bqueue.push_back(bnode);
   1.223 +          Node bnode = queue[i];
   1.224 +          for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) {
   1.225 +            Node anode = _graph->aNode(jt);
   1.226 +            if (_matching[anode] == INVALID) {
   1.227 +
   1.228 +	      if (!_found[anode]) {
   1.229 +		if (_find_path(anode, level, _level)) {
   1.230 +		  ++_size;
   1.231 +		}
   1.232 +		_found.set(anode, true);
   1.233 +	      }
   1.234                success = true;
   1.235              } else {           
   1.236 -              Node newanode = graph->aNode(bnode_matching[bnode]);
   1.237 -              if (!areached[newanode]) {
   1.238 -                areached[newanode] = true;
   1.239 -                newqueue.push_back(newanode);
   1.240 +              Node nnode = _graph->bNode(_matching[anode]);
   1.241 +              if (_reached[nnode] != _phase) {
   1.242 +                _reached.set(nnode, _phase);
   1.243 +                nqueue.push_back(nnode);
   1.244 +		_level.set(nnode, level + 1);
   1.245                }
   1.246              }
   1.247            }
   1.248          }
   1.249 -        queue.swap(newqueue);
   1.250 +	++level;
   1.251 +        queue.swap(nqueue);
   1.252        }
   1.253 -
   1.254 -      if (success) {
   1.255 -
   1.256 -        typename Graph::template ANodeMap<bool> aused(*graph, false);
   1.257 -        
   1.258 -        for (int i = 0; i < int(bqueue.size()); ++i) {
   1.259 -          Node bnode = bqueue[i];
   1.260 -
   1.261 -          bool used = false;
   1.262 -
   1.263 -          while (bnode != INVALID) {
   1.264 -            UEdge uedge = bpred[bnode];
   1.265 -            Node anode = graph->aNode(uedge);
   1.266 -            
   1.267 -            if (aused[anode]) {
   1.268 -              used = true;
   1.269 -              break;
   1.270 -            }
   1.271 -            
   1.272 -            bnode = anode_matching[anode] != INVALID ? 
   1.273 -              graph->bNode(anode_matching[anode]) : INVALID;
   1.274 -            
   1.275 -          }
   1.276 -          
   1.277 -          if (used) continue;
   1.278 -
   1.279 -          bnode = bqueue[i];
   1.280 -          while (bnode != INVALID) {
   1.281 -            UEdge uedge = bpred[bnode];
   1.282 -            Node anode = graph->aNode(uedge);
   1.283 -            
   1.284 -            bnode_matching[bnode] = uedge;
   1.285 -
   1.286 -            bnode = anode_matching[anode] != INVALID ? 
   1.287 -              graph->bNode(anode_matching[anode]) : INVALID;
   1.288 -            
   1.289 -            anode_matching[anode] = uedge;
   1.290 -
   1.291 -            aused[anode] = true;
   1.292 -          }
   1.293 -          ++matching_size;
   1.294 -
   1.295 -        }
   1.296 -      }
   1.297 +      
   1.298        return success;
   1.299      }
   1.300 +  private:
   1.301 +    
   1.302 +    void _find_path_bfs(Node anode,
   1.303 +			typename Graph::template ANodeMap<UEdge>& pred) {
   1.304 +      while (true) {
   1.305 +	UEdge uedge = pred[anode];
   1.306 +	Node bnode = _graph->bNode(uedge);
   1.307  
   1.308 -    /// \brief An augmenting phase of the Ford-Fulkerson algorithm
   1.309 +	UEdge nedge = _rmatching[bnode];
   1.310 +
   1.311 +	_matching.set(anode, uedge);
   1.312 +	_rmatching.set(bnode, uedge);
   1.313 +
   1.314 +	if (nedge == INVALID) break;
   1.315 +	anode = _graph->aNode(nedge);
   1.316 +      }
   1.317 +    }
   1.318 +
   1.319 +  public:
   1.320 +
   1.321 +    /// \brief An augmenting phase with single path augementing
   1.322      ///
   1.323 -    /// It runs an augmenting phase of the Ford-Fulkerson
   1.324 -    /// algorithm. This phase finds only one augmenting path and 
   1.325 -    /// augments only on this paths. The algorithm consists at most 
   1.326 -    /// of \f$ O(n) \f$ simple phase and one phase is at most 
   1.327 -    /// \f$ O(e) \f$ long.
   1.328 -    bool simpleAugment() {
   1.329 +    /// This phase finds only one augmenting paths and augments on
   1.330 +    /// these paths. The algorithm consists at most of \f$ O(n) \f$
   1.331 +    /// phase and one phase is \f$ O(e) \f$ long.
   1.332 +    bool simpleAugment() { 
   1.333 +      ++_phase;
   1.334 +      
   1.335 +      typename Graph::template ANodeMap<UEdge> _pred(*_graph);
   1.336  
   1.337 -      typename Graph::template ANodeMap<bool> areached(*graph, false);
   1.338 -      typename Graph::template BNodeMap<bool> breached(*graph, false);
   1.339 -
   1.340 -      typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
   1.341 -
   1.342 -      std::vector<Node> queue;
   1.343 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.344 -        if (anode_matching[it] == INVALID) {
   1.345 +      std::vector<Node> queue, aqueue;
   1.346 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
   1.347 +        if (_rmatching[it] == INVALID) {
   1.348            queue.push_back(it);
   1.349 -          areached[it] = true;
   1.350 +          _reached.set(it, _phase);
   1.351          }
   1.352        }
   1.353  
   1.354 -      while (!queue.empty()) {
   1.355 -        std::vector<Node> newqueue;
   1.356 +      bool success = false;
   1.357 +
   1.358 +      int level = 0;
   1.359 +      while (!success && !queue.empty()) {
   1.360 +        std::vector<Node> nqueue;
   1.361          for (int i = 0; i < int(queue.size()); ++i) {
   1.362 -          Node anode = queue[i];
   1.363 -          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
   1.364 -            Node bnode = graph->bNode(jt);
   1.365 -            if (breached[bnode]) continue;
   1.366 -            breached[bnode] = true;
   1.367 -            bpred[bnode] = jt;
   1.368 -            if (bnode_matching[bnode] == INVALID) {
   1.369 -              while (bnode != INVALID) {
   1.370 -                UEdge uedge = bpred[bnode];
   1.371 -                anode = graph->aNode(uedge);
   1.372 -                
   1.373 -                bnode_matching[bnode] = uedge;
   1.374 -                
   1.375 -                bnode = anode_matching[anode] != INVALID ? 
   1.376 -                  graph->bNode(anode_matching[anode]) : INVALID;
   1.377 -                
   1.378 -                anode_matching[anode] = uedge;
   1.379 -                
   1.380 -              }
   1.381 -              ++matching_size;
   1.382 -              return true;
   1.383 +          Node bnode = queue[i];
   1.384 +          for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) {
   1.385 +            Node anode = _graph->aNode(jt);
   1.386 +            if (_matching[anode] == INVALID) {
   1.387 +	      _pred.set(anode, jt);
   1.388 +	      _find_path_bfs(anode, _pred);
   1.389 +	      ++_size;
   1.390 +	      return true;
   1.391              } else {           
   1.392 -              Node newanode = graph->aNode(bnode_matching[bnode]);
   1.393 -              if (!areached[newanode]) {
   1.394 -                areached[newanode] = true;
   1.395 -                newqueue.push_back(newanode);
   1.396 +              Node nnode = _graph->bNode(_matching[anode]);
   1.397 +              if (_reached[nnode] != _phase) {
   1.398 +		_pred.set(anode, jt);
   1.399 +		_reached.set(nnode, _phase);
   1.400 +                nqueue.push_back(nnode);
   1.401                }
   1.402              }
   1.403            }
   1.404          }
   1.405 -        queue.swap(newqueue);
   1.406 +	++level;
   1.407 +        queue.swap(nqueue);
   1.408        }
   1.409        
   1.410 -      return false;
   1.411 +      return success;
   1.412      }
   1.413  
   1.414 +
   1.415 +
   1.416      /// \brief Starts the algorithm.
   1.417      ///
   1.418      /// Starts the algorithm. It runs augmenting phases until the optimal
   1.419 @@ -350,6 +361,27 @@
   1.420      
   1.421      ///@{
   1.422  
   1.423 +    /// \brief Return true if the given uedge is in the matching.
   1.424 +    /// 
   1.425 +    /// It returns true if the given uedge is in the matching.
   1.426 +    bool matchingEdge(const UEdge& edge) const {
   1.427 +      return _matching[_graph->aNode(edge)] == edge;
   1.428 +    }
   1.429 +
   1.430 +    /// \brief Returns the matching edge from the node.
   1.431 +    /// 
   1.432 +    /// Returns the matching edge from the node. If there is not such
   1.433 +    /// edge it gives back \c INVALID.
   1.434 +    /// \note If the parameter node is a B-node then the running time is
   1.435 +    /// propotional to the degree of the node.
   1.436 +    UEdge matchingEdge(const Node& node) const {
   1.437 +      if (_graph->aNode(node)) {
   1.438 +        return _matching[node];
   1.439 +      } else {
   1.440 +        return _rmatching[node];
   1.441 +      }
   1.442 +    }
   1.443 +
   1.444      /// \brief Set true all matching uedge in the map.
   1.445      /// 
   1.446      /// Set true all matching uedge in the map. It does not change the
   1.447 @@ -357,12 +389,12 @@
   1.448      /// \return The number of the matching edges.
   1.449      template <typename MatchingMap>
   1.450      int quickMatching(MatchingMap& mm) const {
   1.451 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.452 -        if (anode_matching[it] != INVALID) {
   1.453 -          mm.set(anode_matching[it], true);
   1.454 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
   1.455 +        if (_matching[it] != INVALID) {
   1.456 +          mm.set(_matching[it], true);
   1.457          }
   1.458        }
   1.459 -      return matching_size;
   1.460 +      return _size;
   1.461      }
   1.462  
   1.463      /// \brief Set true all matching uedge in the map and the others to false.
   1.464 @@ -371,10 +403,10 @@
   1.465      /// \return The number of the matching edges.
   1.466      template <typename MatchingMap>
   1.467      int matching(MatchingMap& mm) const {
   1.468 -      for (UEdgeIt it(*graph); it != INVALID; ++it) {
   1.469 -        mm.set(it, it == anode_matching[graph->aNode(it)]);
   1.470 +      for (UEdgeIt it(*_graph); it != INVALID; ++it) {
   1.471 +        mm.set(it, it == _matching[_graph->aNode(it)]);
   1.472        }
   1.473 -      return matching_size;
   1.474 +      return _size;
   1.475      }
   1.476  
   1.477      ///Gives back the matching in an ANodeMap.
   1.478 @@ -384,10 +416,10 @@
   1.479      ///\return The number of the matching edges.
   1.480      template<class MatchingMap>
   1.481      int aMatching(MatchingMap& mm) const {
   1.482 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.483 -        mm.set(it, anode_matching[it]);
   1.484 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
   1.485 +        mm.set(it, _matching[it]);
   1.486        }
   1.487 -      return matching_size;
   1.488 +      return _size;
   1.489      }
   1.490  
   1.491      ///Gives back the matching in a BNodeMap.
   1.492 @@ -397,36 +429,10 @@
   1.493      ///\return The number of the matching edges.
   1.494      template<class MatchingMap>
   1.495      int bMatching(MatchingMap& mm) const {
   1.496 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
   1.497 -        mm.set(it, bnode_matching[it]);
   1.498 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
   1.499 +        mm.set(it, _rmatching[it]);
   1.500        }
   1.501 -      return matching_size;
   1.502 -    }
   1.503 -
   1.504 -    /// \brief Return true if the given uedge is in the matching.
   1.505 -    /// 
   1.506 -    /// It returns true if the given uedge is in the matching.
   1.507 -    bool matchingEdge(const UEdge& edge) const {
   1.508 -      return anode_matching[graph->aNode(edge)] == edge;
   1.509 -    }
   1.510 -
   1.511 -    /// \brief Returns the matching edge from the node.
   1.512 -    /// 
   1.513 -    /// Returns the matching edge from the node. If there is not such
   1.514 -    /// edge it gives back \c INVALID.
   1.515 -    UEdge matchingEdge(const Node& node) const {
   1.516 -      if (graph->aNode(node)) {
   1.517 -        return anode_matching[node];
   1.518 -      } else {
   1.519 -        return bnode_matching[node];
   1.520 -      }
   1.521 -    }
   1.522 -
   1.523 -    /// \brief Gives back the number of the matching edges.
   1.524 -    ///
   1.525 -    /// Gives back the number of the matching edges.
   1.526 -    int matchingSize() const {
   1.527 -      return matching_size;
   1.528 +      return _size;
   1.529      }
   1.530  
   1.531      /// \brief Returns a minimum covering of the nodes.
   1.532 @@ -438,54 +444,23 @@
   1.533      template <typename CoverMap>
   1.534      int coverSet(CoverMap& covering) const {
   1.535  
   1.536 -      typename Graph::template ANodeMap<bool> areached(*graph, false);
   1.537 -      typename Graph::template BNodeMap<bool> breached(*graph, false);
   1.538 -      
   1.539 -      std::vector<Node> queue;
   1.540 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.541 -        if (anode_matching[it] == INVALID) {
   1.542 -          queue.push_back(it);
   1.543 -        }
   1.544 +      int size = 0;
   1.545 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
   1.546 +	bool cn = _matching[it] != INVALID && 
   1.547 +	  _reached[_graph->bNode(_matching[it])] == _phase;
   1.548 +        covering.set(it, cn);
   1.549 +        if (cn) ++size;
   1.550        }
   1.551 -
   1.552 -      while (!queue.empty()) {
   1.553 -        std::vector<Node> newqueue;
   1.554 -        for (int i = 0; i < int(queue.size()); ++i) {
   1.555 -          Node anode = queue[i];
   1.556 -          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
   1.557 -            Node bnode = graph->bNode(jt);
   1.558 -            if (breached[bnode]) continue;
   1.559 -            breached[bnode] = true;
   1.560 -            if (bnode_matching[bnode] != INVALID) {
   1.561 -              Node newanode = graph->aNode(bnode_matching[bnode]);
   1.562 -              if (!areached[newanode]) {
   1.563 -                areached[newanode] = true;
   1.564 -                newqueue.push_back(newanode);
   1.565 -              }
   1.566 -            }
   1.567 -          }
   1.568 -        }
   1.569 -        queue.swap(newqueue);
   1.570 -      }
   1.571 -
   1.572 -      int size = 0;
   1.573 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.574 -        covering.set(it, !areached[it] && anode_matching[it] != INVALID);
   1.575 -        if (!areached[it] && anode_matching[it] != INVALID) {
   1.576 -          ++size;
   1.577 -        }
   1.578 -      }
   1.579 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
   1.580 -        covering.set(it, breached[it]);
   1.581 -        if (breached[it]) {
   1.582 -          ++size;
   1.583 -        }
   1.584 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
   1.585 +	bool cn = _reached[it] != _phase;
   1.586 +        covering.set(it, cn);
   1.587 +        if (cn) ++size;
   1.588        }
   1.589        return size;
   1.590      }
   1.591  
   1.592      /// \brief Gives back a barrier on the A-nodes
   1.593 -    
   1.594 +    ///    
   1.595      /// The barrier is s subset of the nodes on the same side of the
   1.596      /// graph, which size minus its neighbours is exactly the
   1.597      /// unmatched nodes on the A-side.  
   1.598 @@ -493,43 +468,14 @@
   1.599      template <typename BarrierMap>
   1.600      void aBarrier(BarrierMap& barrier) const {
   1.601  
   1.602 -      typename Graph::template ANodeMap<bool> areached(*graph, false);
   1.603 -      typename Graph::template BNodeMap<bool> breached(*graph, false);
   1.604 -      
   1.605 -      std::vector<Node> queue;
   1.606 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.607 -        if (anode_matching[it] == INVALID) {
   1.608 -          queue.push_back(it);
   1.609 -        }
   1.610 -      }
   1.611 -
   1.612 -      while (!queue.empty()) {
   1.613 -        std::vector<Node> newqueue;
   1.614 -        for (int i = 0; i < int(queue.size()); ++i) {
   1.615 -          Node anode = queue[i];
   1.616 -          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
   1.617 -            Node bnode = graph->bNode(jt);
   1.618 -            if (breached[bnode]) continue;
   1.619 -            breached[bnode] = true;
   1.620 -            if (bnode_matching[bnode] != INVALID) {
   1.621 -              Node newanode = graph->aNode(bnode_matching[bnode]);
   1.622 -              if (!areached[newanode]) {
   1.623 -                areached[newanode] = true;
   1.624 -                newqueue.push_back(newanode);
   1.625 -              }
   1.626 -            }
   1.627 -          }
   1.628 -        }
   1.629 -        queue.swap(newqueue);
   1.630 -      }
   1.631 -
   1.632 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.633 -        barrier.set(it, areached[it] || anode_matching[it] == INVALID);
   1.634 +      for (ANodeIt it(*_graph); it != INVALID; ++it) {
   1.635 +        barrier.set(it, _matching[it] == INVALID || 
   1.636 +		    _reached[_graph->bNode(_matching[it])] != _phase);
   1.637        }
   1.638      }
   1.639  
   1.640      /// \brief Gives back a barrier on the B-nodes
   1.641 -    
   1.642 +    ///    
   1.643      /// The barrier is s subset of the nodes on the same side of the
   1.644      /// graph, which size minus its neighbours is exactly the
   1.645      /// unmatched nodes on the B-side.  
   1.646 @@ -537,50 +483,31 @@
   1.647      template <typename BarrierMap>
   1.648      void bBarrier(BarrierMap& barrier) const {
   1.649  
   1.650 -      typename Graph::template ANodeMap<bool> areached(*graph, false);
   1.651 -      typename Graph::template BNodeMap<bool> breached(*graph, false);
   1.652 -      
   1.653 -      std::vector<Node> queue;
   1.654 -      for (ANodeIt it(*graph); it != INVALID; ++it) {
   1.655 -        if (anode_matching[it] == INVALID) {
   1.656 -          queue.push_back(it);
   1.657 -        }
   1.658 +      for (BNodeIt it(*_graph); it != INVALID; ++it) {
   1.659 +        barrier.set(it, _reached[it] == _phase);
   1.660        }
   1.661 +    }
   1.662  
   1.663 -      while (!queue.empty()) {
   1.664 -        std::vector<Node> newqueue;
   1.665 -        for (int i = 0; i < int(queue.size()); ++i) {
   1.666 -          Node anode = queue[i];
   1.667 -          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
   1.668 -            Node bnode = graph->bNode(jt);
   1.669 -            if (breached[bnode]) continue;
   1.670 -            breached[bnode] = true;
   1.671 -            if (bnode_matching[bnode] != INVALID) {
   1.672 -              Node newanode = graph->aNode(bnode_matching[bnode]);
   1.673 -              if (!areached[newanode]) {
   1.674 -                areached[newanode] = true;
   1.675 -                newqueue.push_back(newanode);
   1.676 -              }
   1.677 -            }
   1.678 -          }
   1.679 -        }
   1.680 -        queue.swap(newqueue);
   1.681 -      }
   1.682 -
   1.683 -      for (BNodeIt it(*graph); it != INVALID; ++it) {
   1.684 -        barrier.set(it, !breached[it]);
   1.685 -      }
   1.686 +    /// \brief Gives back the number of the matching edges.
   1.687 +    ///
   1.688 +    /// Gives back the number of the matching edges.
   1.689 +    int matchingSize() const {
   1.690 +      return _size;
   1.691      }
   1.692  
   1.693      /// @}
   1.694  
   1.695    private:
   1.696  
   1.697 -    ANodeMatchingMap anode_matching;
   1.698 -    BNodeMatchingMap bnode_matching;
   1.699 -    const Graph *graph;
   1.700 +    typename BpUGraph::template ANodeMap<UEdge> _matching;
   1.701 +    typename BpUGraph::template BNodeMap<UEdge> _rmatching;
   1.702  
   1.703 -    int matching_size;
   1.704 +    typename BpUGraph::template BNodeMap<int> _reached;
   1.705 +
   1.706 +    int _phase;
   1.707 +    const Graph *_graph;
   1.708 +
   1.709 +    int _size;
   1.710    
   1.711    };
   1.712  
     2.1 --- a/lemon/pr_bipartite_matching.h	Sat Aug 25 10:12:03 2007 +0000
     2.2 +++ b/lemon/pr_bipartite_matching.h	Tue Aug 28 13:58:54 2007 +0000
     2.3 @@ -59,6 +59,10 @@
     2.4  
     2.5    public:
     2.6  
     2.7 +    /// Constructor
     2.8 +
     2.9 +    /// Constructor
    2.10 +    ///
    2.11      PrBipartiteMatching(const Graph &g) :
    2.12        _g(g),
    2.13        _node_num(countBNodes(g)),
    2.14 @@ -195,14 +199,15 @@
    2.15  	  _levels.liftToTop(actlevel);
    2.16        }
    2.17        
    2.18 -      _matching_size = _node_num;
    2.19 -      for(ANodeIt n(_g);n!=INVALID;++n)
    2.20 -	if(_matching[n]==INVALID) _matching_size--;
    2.21 -	else if (_cov[_g.bNode(_matching[n])]>1) {
    2.22 +      for(ANodeIt n(_g);n!=INVALID;++n) {
    2.23 +	if (_matching[n]==INVALID)continue;
    2.24 +	if (_cov[_g.bNode(_matching[n])]>1) {
    2.25  	  _cov[_g.bNode(_matching[n])]--;
    2.26 -	  _matching_size--;
    2.27  	  _matching[n]=INVALID;
    2.28 +	} else {
    2.29 +	  ++_matching_size;
    2.30  	}
    2.31 +      }
    2.32      }
    2.33  
    2.34      ///Start the algorithm to find a perfect matching
    2.35 @@ -261,6 +266,7 @@
    2.36  	  _empty_level=actlevel;
    2.37  	  return false;
    2.38        }
    2.39 +      _matching_size = _node_num;
    2.40        return true;
    2.41      }
    2.42