COIN-OR::LEMON - Graph Library

Changeset 2466:feb7974cf4ec in lemon-0.x for lemon


Ignore:
Timestamp:
08/28/07 15:58:54 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3304
Message:

Redesign of augmenting path based matching
Small bug fix in the push-relabel based

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bipartite_matching.h

    r2463 r2466  
    7070    ///
    7171    /// Constructor of the algorithm.
    72     MaxBipartiteMatching(const BpUGraph& _graph)
    73       : anode_matching(_graph), bnode_matching(_graph), graph(&_graph) {}
     72    MaxBipartiteMatching(const BpUGraph& graph)
     73      : _matching(graph), _rmatching(graph), _reached(graph), _graph(&graph) {}
    7474
    7575    /// \name Execution control
     
    8888    /// It initalizes the data structures and creates an empty matching.
    8989    void init() {
    90       for (ANodeIt it(*graph); it != INVALID; ++it) {
    91         anode_matching[it] = INVALID;
    92       }
    93       for (BNodeIt it(*graph); it != INVALID; ++it) {
    94         bnode_matching[it] = INVALID;
    95       }
    96       matching_size = 0;
     90      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     91        _matching.set(it, INVALID);
     92      }
     93      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     94        _rmatching.set(it, INVALID);
     95        _reached.set(it, -1);
     96      }
     97      _size = 0;
     98      _phase = -1;
    9799    }
    98100
     
    103105    /// the matching than from the initial empty matching.
    104106    void greedyInit() {
    105       matching_size = 0;
    106       for (BNodeIt it(*graph); it != INVALID; ++it) {
    107         bnode_matching[it] = INVALID;
    108       }
    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;
    115             ++matching_size;
     107      _size = 0;
     108      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     109        _rmatching.set(it, INVALID);
     110        _reached.set(it, 0);
     111      }
     112      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     113        _matching[it] = INVALID;
     114        for (IncEdgeIt jt(*_graph, it); jt != INVALID; ++jt) {
     115          if (_rmatching[_graph->bNode(jt)] == INVALID) {
     116            _matching.set(it, jt);
     117            _rmatching.set(_graph->bNode(jt), jt);
     118            _reached.set(it, -1);
     119            ++_size;
    116120            break;
    117121          }
    118122        }
    119123      }
     124      _phase = 0;
    120125    }
    121126
     
    125130    template <typename MatchingMap>
    126131    void matchingInit(const MatchingMap& mm) {
    127       for (ANodeIt it(*graph); it != INVALID; ++it) {
    128         anode_matching[it] = INVALID;
    129       }
    130       for (BNodeIt it(*graph); it != INVALID; ++it) {
    131         bnode_matching[it] = INVALID;
    132       }
    133       matching_size = 0;
    134       for (UEdgeIt it(*graph); it != INVALID; ++it) {
     132      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     133        _matching.set(it, INVALID);
     134      }
     135      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     136        _rmatching.set(it, INVALID);
     137        _reached.set(it, 0);
     138      }
     139      _size = 0;
     140      for (UEdgeIt it(*_graph); it != INVALID; ++it) {
    135141        if (mm[it]) {
    136           ++matching_size;
    137           anode_matching[graph->aNode(it)] = it;
    138           bnode_matching[graph->bNode(it)] = it;
    139         }
    140       }
     142          ++_size;
     143          _matching.set(_graph->aNode(it), it);
     144          _rmatching.set(_graph->bNode(it), it);
     145          _reached.set(it, 0);
     146        }
     147      }
     148      _phase = 0;
    141149    }
    142150
     
    146154    /// \return %True when the given map contains really a matching.
    147155    template <typename MatchingMap>
    148     void checkedMatchingInit(const MatchingMap& mm) {
    149       for (ANodeIt it(*graph); it != INVALID; ++it) {
    150         anode_matching[it] = INVALID;
    151       }
    152       for (BNodeIt it(*graph); it != INVALID; ++it) {
    153         bnode_matching[it] = INVALID;
    154       }
    155       matching_size = 0;
    156       for (UEdgeIt it(*graph); it != INVALID; ++it) {
     156    bool checkedMatchingInit(const MatchingMap& mm) {
     157      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     158        _matching.set(it, INVALID);
     159      }
     160      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     161        _rmatching.set(it, INVALID);
     162        _reached.set(it, 0);
     163      }
     164      _size = 0;
     165      for (UEdgeIt it(*_graph); it != INVALID; ++it) {
    157166        if (mm[it]) {
    158           ++matching_size;
    159           if (anode_matching[graph->aNode(it)] != INVALID) {
     167          ++_size;
     168          if (_matching[_graph->aNode(it)] != INVALID) {
    160169            return false;
    161170          }
    162           anode_matching[graph->aNode(it)] = it;
    163           if (bnode_matching[graph->aNode(it)] != INVALID) {
     171          _matching.set(_graph->aNode(it), it);
     172          if (_matching[_graph->bNode(it)] != INVALID) {
    164173            return false;
    165174          }
    166           bnode_matching[graph->bNode(it)] = it;
    167         }
     175          _matching.set(_graph->bNode(it), it);
     176          _reached.set(_graph->bNode(it), -1);
     177        }
     178      }
     179      _phase = 0;
     180      return true;
     181    }
     182
     183  private:
     184   
     185    bool _find_path(Node anode, int maxlevel,
     186                    typename Graph::template BNodeMap<int>& level) {
     187      for (IncEdgeIt it(*_graph, anode); it != INVALID; ++it) {
     188        Node bnode = _graph->bNode(it);
     189        if (level[bnode] == maxlevel) {
     190          level.set(bnode, -1);
     191          if (maxlevel == 0) {
     192            _matching.set(anode, it);
     193            _rmatching.set(bnode, it);
     194            return true;
     195          } else {
     196            Node nnode = _graph->aNode(_rmatching[bnode]);
     197            if (_find_path(nnode, maxlevel - 1, level)) {
     198              _matching.set(anode, it);
     199              _rmatching.set(bnode, it);
     200              return true;
     201            }
     202          }
     203        }
    168204      }
    169205      return false;
    170206    }
    171207
     208  public:
     209
    172210    /// \brief An augmenting phase of the Hopcroft-Karp algorithm
    173211    ///
    174212    /// 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.
     213    /// algorithm. This phase finds maximal edge disjoint augmenting
     214    /// paths and augments on these paths. The algorithm consists at
     215    /// most of \f$ O(\sqrt{n}) \f$ phase and one phase is \f$ O(e)
     216    /// \f$ long.
    179217    bool augment() {
    180218
    181       typename Graph::template ANodeMap<bool> areached(*graph, false);
    182       typename Graph::template BNodeMap<bool> breached(*graph, false);
    183 
    184       typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
    185 
    186       std::vector<Node> queue, bqueue;
    187       for (ANodeIt it(*graph); it != INVALID; ++it) {
    188         if (anode_matching[it] == INVALID) {
     219      ++_phase;
     220     
     221      typename Graph::template BNodeMap<int> _level(*_graph, -1);
     222      typename Graph::template ANodeMap<bool> _found(*_graph, false);
     223
     224      std::vector<Node> queue, aqueue;
     225      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     226        if (_rmatching[it] == INVALID) {
    189227          queue.push_back(it);
    190           areached[it] = true;
     228          _reached.set(it, _phase);
     229          _level.set(it, 0);
    191230        }
    192231      }
     
    194233      bool success = false;
    195234
     235      int level = 0;
    196236      while (!success && !queue.empty()) {
    197         std::vector<Node> newqueue;
     237        std::vector<Node> nqueue;
    198238        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;
    204             bpred[bnode] = jt;
    205             if (bnode_matching[bnode] == INVALID) {
    206               bqueue.push_back(bnode);
     239          Node bnode = queue[i];
     240          for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) {
     241            Node anode = _graph->aNode(jt);
     242            if (_matching[anode] == INVALID) {
     243
     244              if (!_found[anode]) {
     245                if (_find_path(anode, level, _level)) {
     246                  ++_size;
     247                }
     248                _found.set(anode, true);
     249              }
    207250              success = true;
    208251            } else {           
    209               Node newanode = graph->aNode(bnode_matching[bnode]);
    210               if (!areached[newanode]) {
    211                 areached[newanode] = true;
    212                 newqueue.push_back(newanode);
     252              Node nnode = _graph->bNode(_matching[anode]);
     253              if (_reached[nnode] != _phase) {
     254                _reached.set(nnode, _phase);
     255                nqueue.push_back(nnode);
     256                _level.set(nnode, level + 1);
    213257              }
    214258            }
    215259          }
    216260        }
    217         queue.swap(newqueue);
    218       }
    219 
    220       if (success) {
    221 
    222         typename Graph::template ANodeMap<bool> aused(*graph, false);
    223        
    224         for (int i = 0; i < int(bqueue.size()); ++i) {
    225           Node bnode = bqueue[i];
    226 
    227           bool used = false;
    228 
    229           while (bnode != INVALID) {
    230             UEdge uedge = bpred[bnode];
    231             Node anode = graph->aNode(uedge);
    232            
    233             if (aused[anode]) {
    234               used = true;
    235               break;
    236             }
    237            
    238             bnode = anode_matching[anode] != INVALID ?
    239               graph->bNode(anode_matching[anode]) : INVALID;
    240            
    241           }
    242          
    243           if (used) continue;
    244 
    245           bnode = bqueue[i];
    246           while (bnode != INVALID) {
    247             UEdge uedge = bpred[bnode];
    248             Node anode = graph->aNode(uedge);
    249            
    250             bnode_matching[bnode] = uedge;
    251 
    252             bnode = anode_matching[anode] != INVALID ?
    253               graph->bNode(anode_matching[anode]) : INVALID;
    254            
    255             anode_matching[anode] = uedge;
    256 
    257             aused[anode] = true;
    258           }
    259           ++matching_size;
    260 
    261         }
    262       }
     261        ++level;
     262        queue.swap(nqueue);
     263      }
     264     
    263265      return success;
    264266    }
    265 
    266     /// \brief An augmenting phase of the Ford-Fulkerson algorithm
    267     ///
    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() {
    274 
    275       typename Graph::template ANodeMap<bool> areached(*graph, false);
    276       typename Graph::template BNodeMap<bool> breached(*graph, false);
    277 
    278       typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
    279 
    280       std::vector<Node> queue;
    281       for (ANodeIt it(*graph); it != INVALID; ++it) {
    282         if (anode_matching[it] == INVALID) {
     267  private:
     268   
     269    void _find_path_bfs(Node anode,
     270                        typename Graph::template ANodeMap<UEdge>& pred) {
     271      while (true) {
     272        UEdge uedge = pred[anode];
     273        Node bnode = _graph->bNode(uedge);
     274
     275        UEdge nedge = _rmatching[bnode];
     276
     277        _matching.set(anode, uedge);
     278        _rmatching.set(bnode, uedge);
     279
     280        if (nedge == INVALID) break;
     281        anode = _graph->aNode(nedge);
     282      }
     283    }
     284
     285  public:
     286
     287    /// \brief An augmenting phase with single path augementing
     288    ///
     289    /// This phase finds only one augmenting paths and augments on
     290    /// these paths. The algorithm consists at most of \f$ O(n) \f$
     291    /// phase and one phase is \f$ O(e) \f$ long.
     292    bool simpleAugment() {
     293      ++_phase;
     294     
     295      typename Graph::template ANodeMap<UEdge> _pred(*_graph);
     296
     297      std::vector<Node> queue, aqueue;
     298      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     299        if (_rmatching[it] == INVALID) {
    283300          queue.push_back(it);
    284           areached[it] = true;
    285         }
    286       }
    287 
    288       while (!queue.empty()) {
    289         std::vector<Node> newqueue;
     301          _reached.set(it, _phase);
     302        }
     303      }
     304
     305      bool success = false;
     306
     307      int level = 0;
     308      while (!success && !queue.empty()) {
     309        std::vector<Node> nqueue;
    290310        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;
    296             bpred[bnode] = jt;
    297             if (bnode_matching[bnode] == INVALID) {
    298               while (bnode != INVALID) {
    299                 UEdge uedge = bpred[bnode];
    300                 anode = graph->aNode(uedge);
    301                
    302                 bnode_matching[bnode] = uedge;
    303                
    304                 bnode = anode_matching[anode] != INVALID ?
    305                   graph->bNode(anode_matching[anode]) : INVALID;
    306                
    307                 anode_matching[anode] = uedge;
    308                
    309               }
    310               ++matching_size;
    311               return true;
     311          Node bnode = queue[i];
     312          for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) {
     313            Node anode = _graph->aNode(jt);
     314            if (_matching[anode] == INVALID) {
     315              _pred.set(anode, jt);
     316              _find_path_bfs(anode, _pred);
     317              ++_size;
     318              return true;
    312319            } else {           
    313               Node newanode = graph->aNode(bnode_matching[bnode]);
    314               if (!areached[newanode]) {
    315                 areached[newanode] = true;
    316                 newqueue.push_back(newanode);
     320              Node nnode = _graph->bNode(_matching[anode]);
     321              if (_reached[nnode] != _phase) {
     322                _pred.set(anode, jt);
     323                _reached.set(nnode, _phase);
     324                nqueue.push_back(nnode);
    317325              }
    318326            }
    319327          }
    320328        }
    321         queue.swap(newqueue);
     329        ++level;
     330        queue.swap(nqueue);
    322331      }
    323332     
    324       return false;
    325     }
     333      return success;
     334    }
     335
     336
    326337
    327338    /// \brief Starts the algorithm.
     
    351362    ///@{
    352363
     364    /// \brief Return true if the given uedge is in the matching.
     365    ///
     366    /// It returns true if the given uedge is in the matching.
     367    bool matchingEdge(const UEdge& edge) const {
     368      return _matching[_graph->aNode(edge)] == edge;
     369    }
     370
     371    /// \brief Returns the matching edge from the node.
     372    ///
     373    /// Returns the matching edge from the node. If there is not such
     374    /// edge it gives back \c INVALID.
     375    /// \note If the parameter node is a B-node then the running time is
     376    /// propotional to the degree of the node.
     377    UEdge matchingEdge(const Node& node) const {
     378      if (_graph->aNode(node)) {
     379        return _matching[node];
     380      } else {
     381        return _rmatching[node];
     382      }
     383    }
     384
    353385    /// \brief Set true all matching uedge in the map.
    354386    ///
     
    358390    template <typename MatchingMap>
    359391    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);
    363         }
    364       }
    365       return matching_size;
     392      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     393        if (_matching[it] != INVALID) {
     394          mm.set(_matching[it], true);
     395        }
     396      }
     397      return _size;
    366398    }
    367399
     
    372404    template <typename MatchingMap>
    373405    int matching(MatchingMap& mm) const {
    374       for (UEdgeIt it(*graph); it != INVALID; ++it) {
    375         mm.set(it, it == anode_matching[graph->aNode(it)]);
    376       }
    377       return matching_size;
     406      for (UEdgeIt it(*_graph); it != INVALID; ++it) {
     407        mm.set(it, it == _matching[_graph->aNode(it)]);
     408      }
     409      return _size;
    378410    }
    379411
     
    385417    template<class MatchingMap>
    386418    int aMatching(MatchingMap& mm) const {
    387       for (ANodeIt it(*graph); it != INVALID; ++it) {
    388         mm.set(it, anode_matching[it]);
    389       }
    390       return matching_size;
     419      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     420        mm.set(it, _matching[it]);
     421      }
     422      return _size;
    391423    }
    392424
     
    398430    template<class MatchingMap>
    399431    int bMatching(MatchingMap& mm) const {
    400       for (BNodeIt it(*graph); it != INVALID; ++it) {
    401         mm.set(it, bnode_matching[it]);
    402       }
    403       return matching_size;
    404     }
    405 
    406     /// \brief Return true if the given uedge is in the matching.
    407     ///
    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;
    411     }
    412 
    413     /// \brief Returns the matching edge from the node.
    414     ///
    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];
    420       } else {
    421         return bnode_matching[node];
    422       }
    423     }
    424 
    425     /// \brief Gives back the number of the matching edges.
    426     ///
    427     /// Gives back the number of the matching edges.
    428     int matchingSize() const {
    429       return matching_size;
     432      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     433        mm.set(it, _rmatching[it]);
     434      }
     435      return _size;
    430436    }
    431437
     
    439445    int coverSet(CoverMap& covering) const {
    440446
    441       typename Graph::template ANodeMap<bool> areached(*graph, false);
    442       typename Graph::template BNodeMap<bool> breached(*graph, false);
    443      
    444       std::vector<Node> queue;
    445       for (ANodeIt it(*graph); it != INVALID; ++it) {
    446         if (anode_matching[it] == INVALID) {
    447           queue.push_back(it);
    448         }
    449       }
    450 
    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);
    464               }
    465             }
    466           }
    467         }
    468         queue.swap(newqueue);
    469       }
    470 
    471447      int size = 0;
    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) {
    475           ++size;
    476         }
    477       }
    478       for (BNodeIt it(*graph); it != INVALID; ++it) {
    479         covering.set(it, breached[it]);
    480         if (breached[it]) {
    481           ++size;
    482         }
     448      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     449        bool cn = _matching[it] != INVALID &&
     450          _reached[_graph->bNode(_matching[it])] == _phase;
     451        covering.set(it, cn);
     452        if (cn) ++size;
     453      }
     454      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     455        bool cn = _reached[it] != _phase;
     456        covering.set(it, cn);
     457        if (cn) ++size;
    483458      }
    484459      return size;
     
    486461
    487462    /// \brief Gives back a barrier on the A-nodes
    488    
     463    ///   
    489464    /// The barrier is s subset of the nodes on the same side of the
    490465    /// graph, which size minus its neighbours is exactly the
     
    494469    void aBarrier(BarrierMap& barrier) const {
    495470
    496       typename Graph::template ANodeMap<bool> areached(*graph, false);
    497       typename Graph::template BNodeMap<bool> breached(*graph, false);
    498      
    499       std::vector<Node> queue;
    500       for (ANodeIt it(*graph); it != INVALID; ++it) {
    501         if (anode_matching[it] == INVALID) {
    502           queue.push_back(it);
    503         }
    504       }
    505 
    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);
    519               }
    520             }
    521           }
    522         }
    523         queue.swap(newqueue);
    524       }
    525 
    526       for (ANodeIt it(*graph); it != INVALID; ++it) {
    527         barrier.set(it, areached[it] || anode_matching[it] == INVALID);
     471      for (ANodeIt it(*_graph); it != INVALID; ++it) {
     472        barrier.set(it, _matching[it] == INVALID ||
     473                    _reached[_graph->bNode(_matching[it])] != _phase);
    528474      }
    529475    }
    530476
    531477    /// \brief Gives back a barrier on the B-nodes
    532    
     478    ///   
    533479    /// The barrier is s subset of the nodes on the same side of the
    534480    /// graph, which size minus its neighbours is exactly the
     
    538484    void bBarrier(BarrierMap& barrier) const {
    539485
    540       typename Graph::template ANodeMap<bool> areached(*graph, false);
    541       typename Graph::template BNodeMap<bool> breached(*graph, false);
    542      
    543       std::vector<Node> queue;
    544       for (ANodeIt it(*graph); it != INVALID; ++it) {
    545         if (anode_matching[it] == INVALID) {
    546           queue.push_back(it);
    547         }
    548       }
    549 
    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);
    563               }
    564             }
    565           }
    566         }
    567         queue.swap(newqueue);
    568       }
    569 
    570       for (BNodeIt it(*graph); it != INVALID; ++it) {
    571         barrier.set(it, !breached[it]);
    572       }
     486      for (BNodeIt it(*_graph); it != INVALID; ++it) {
     487        barrier.set(it, _reached[it] == _phase);
     488      }
     489    }
     490
     491    /// \brief Gives back the number of the matching edges.
     492    ///
     493    /// Gives back the number of the matching edges.
     494    int matchingSize() const {
     495      return _size;
    573496    }
    574497
     
    577500  private:
    578501
    579     ANodeMatchingMap anode_matching;
    580     BNodeMatchingMap bnode_matching;
    581     const Graph *graph;
    582 
    583     int matching_size;
     502    typename BpUGraph::template ANodeMap<UEdge> _matching;
     503    typename BpUGraph::template BNodeMap<UEdge> _rmatching;
     504
     505    typename BpUGraph::template BNodeMap<int> _reached;
     506
     507    int _phase;
     508    const Graph *_graph;
     509
     510    int _size;
    584511 
    585512  };
  • lemon/pr_bipartite_matching.h

    r2463 r2466  
    6060  public:
    6161
     62    /// Constructor
     63
     64    /// Constructor
     65    ///
    6266    PrBipartiteMatching(const Graph &g) :
    6367      _g(g),
     
    196200      }
    197201     
    198       _matching_size = _node_num;
    199       for(ANodeIt n(_g);n!=INVALID;++n)
    200         if(_matching[n]==INVALID) _matching_size--;
    201         else if (_cov[_g.bNode(_matching[n])]>1) {
     202      for(ANodeIt n(_g);n!=INVALID;++n) {
     203        if (_matching[n]==INVALID)continue;
     204        if (_cov[_g.bNode(_matching[n])]>1) {
    202205          _cov[_g.bNode(_matching[n])]--;
    203           _matching_size--;
    204206          _matching[n]=INVALID;
    205         }
     207        } else {
     208          ++_matching_size;
     209        }
     210      }
    206211    }
    207212
     
    262267          return false;
    263268      }
     269      _matching_size = _node_num;
    264270      return true;
    265271    }
Note: See TracChangeset for help on using the changeset viewer.