1.1 --- a/lemon/bipartite_matching.h	Sat Dec 29 15:11:41 2007 +0000
     1.2 +++ b/lemon/bipartite_matching.h	Sun Dec 30 18:23:32 2007 +0000
     1.3 @@ -578,7 +578,7 @@
     1.4    /// \param _BpUGraph The bipartite undirected graph type.
     1.5    /// \param _WeightMap Type of weight map.
     1.6    template <typename _BpUGraph, typename _WeightMap>
     1.7 -  struct WeightedBipartiteMatchingDefaultTraits {
     1.8 +  struct MaxWeightedBipartiteMatchingDefaultTraits {
     1.9      /// \brief The type of the weight of the undirected edges.
    1.10      typedef typename _WeightMap::Value Value;
    1.11  
    1.12 @@ -591,8 +591,8 @@
    1.13      /// \brief The cross reference type used by heap.
    1.14      ///
    1.15      /// The cross reference type used by heap.
    1.16 -    /// Usually it is \c Graph::NodeMap<int>.
    1.17 -    typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;
    1.18 +    /// Usually it is \c Graph::ANodeMap<int>.
    1.19 +    typedef typename BpUGraph::template ANodeMap<int> HeapCrossRef;
    1.20  
    1.21      /// \brief Instantiates a HeapCrossRef.
    1.22      ///
    1.23 @@ -644,7 +644,8 @@
    1.24  #else
    1.25    template <typename _BpUGraph, 
    1.26              typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>,
    1.27 -            typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
    1.28 +            typename _Traits = 
    1.29 +	    MaxWeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
    1.30  #endif
    1.31    class MaxWeightedBipartiteMatching {
    1.32    public:
    1.33 @@ -864,13 +865,13 @@
    1.34            Node bnode = graph->bNode(jt);
    1.35            Value bvalue = avalue  - (*weight)[jt] +
    1.36              anode_potential[anode] + bnode_potential[bnode];
    1.37 +          if (bvalue > bdistMax) {
    1.38 +            bdistMax = bvalue;
    1.39 +          }
    1.40            if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
    1.41              bdist[bnode] = bvalue;
    1.42              bpred[bnode] = jt;
    1.43 -          }
    1.44 -          if (bvalue > bdistMax) {
    1.45 -            bdistMax = bvalue;
    1.46 -          }
    1.47 +          } else continue;
    1.48            if (bnode_matching[bnode] != INVALID) {
    1.49              Node newanode = graph->aNode(bnode_matching[bnode]);
    1.50              switch (_heap->state(newanode)) {
    1.51 @@ -1241,7 +1242,8 @@
    1.52  #else
    1.53    template <typename _BpUGraph, 
    1.54              typename _CostMap = typename _BpUGraph::template UEdgeMap<int>,
    1.55 -            typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
    1.56 +            typename _Traits = 
    1.57 +	    MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
    1.58  #endif
    1.59    class MinCostMaxBipartiteMatching {
    1.60    public:
    1.61 @@ -1451,13 +1453,13 @@
    1.62            Node bnode = graph->bNode(jt);
    1.63            Value bvalue = avalue + (*cost)[jt] + 
    1.64              anode_potential[anode] - bnode_potential[bnode];
    1.65 +          if (bvalue > bdistMax) {
    1.66 +            bdistMax = bvalue;
    1.67 +          }
    1.68            if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
    1.69              bdist[bnode] = bvalue;
    1.70              bpred[bnode] = jt;
    1.71 -          }
    1.72 -          if (bvalue > bdistMax) {
    1.73 -            bdistMax = bvalue;
    1.74 -          }
    1.75 +          } else continue;
    1.76            if (bnode_matching[bnode] != INVALID) {
    1.77              Node newanode = graph->aNode(bnode_matching[bnode]);
    1.78              switch (_heap->state(newanode)) {

     2.1 --- a/lemon/unionfind.h	Sat Dec 29 15:11:41 2007 +0000
     2.2 +++ b/lemon/unionfind.h	Sun Dec 30 18:23:32 2007 +0000
     2.3 @@ -962,7 +962,7 @@
     2.4  
     2.5    private:
     2.6  
     2.7 -    static const int cmax = 3;
     2.8 +    static const int cmax = 16;
     2.9  
    2.10      ItemIntMap& index;
    2.11  
    2.12 @@ -1124,6 +1124,7 @@
    2.13          nodes[kd].parent = id;
    2.14          kd = nodes[kd].next;
    2.15        }
    2.16 +      nodes[id].right = nodes[jd].right;
    2.17      }
    2.18  
    2.19      void split(int id, int jd) {