# HG changeset patch
# User deba
# Date 1199039012 0
# Node ID f26368148b9cf6d4a603bc6c1e84ca6416f72294
# Parent  88b81ec599ed77ff8caad2e634c213a522e8ec91
Changing degree of tournament tree
Bug fix in union find
Small efficiency improvment in bipartite matchings

diff -r 88b81ec599ed -r f26368148b9c lemon/bipartite_matching.h
--- a/lemon/bipartite_matching.h	Sat Dec 29 15:11:41 2007 +0000
+++ b/lemon/bipartite_matching.h	Sun Dec 30 18:23:32 2007 +0000
@@ -578,7 +578,7 @@
   /// \param _BpUGraph The bipartite undirected graph type.
   /// \param _WeightMap Type of weight map.
   template <typename _BpUGraph, typename _WeightMap>
-  struct WeightedBipartiteMatchingDefaultTraits {
+  struct MaxWeightedBipartiteMatchingDefaultTraits {
     /// \brief The type of the weight of the undirected edges.
     typedef typename _WeightMap::Value Value;
 
@@ -591,8 +591,8 @@
     /// \brief The cross reference type used by heap.
     ///
     /// The cross reference type used by heap.
-    /// Usually it is \c Graph::NodeMap<int>.
-    typedef typename BpUGraph::template NodeMap<int> HeapCrossRef;
+    /// Usually it is \c Graph::ANodeMap<int>.
+    typedef typename BpUGraph::template ANodeMap<int> HeapCrossRef;
 
     /// \brief Instantiates a HeapCrossRef.
     ///
@@ -644,7 +644,8 @@
 #else
   template <typename _BpUGraph, 
             typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>,
-            typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
+            typename _Traits = 
+	    MaxWeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
 #endif
   class MaxWeightedBipartiteMatching {
   public:
@@ -864,13 +865,13 @@
           Node bnode = graph->bNode(jt);
           Value bvalue = avalue  - (*weight)[jt] +
             anode_potential[anode] + bnode_potential[bnode];
+          if (bvalue > bdistMax) {
+            bdistMax = bvalue;
+          }
           if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
             bdist[bnode] = bvalue;
             bpred[bnode] = jt;
-          }
-          if (bvalue > bdistMax) {
-            bdistMax = bvalue;
-          }
+          } else continue;
           if (bnode_matching[bnode] != INVALID) {
             Node newanode = graph->aNode(bnode_matching[bnode]);
             switch (_heap->state(newanode)) {
@@ -1241,7 +1242,8 @@
 #else
   template <typename _BpUGraph, 
             typename _CostMap = typename _BpUGraph::template UEdgeMap<int>,
-            typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
+            typename _Traits = 
+	    MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
 #endif
   class MinCostMaxBipartiteMatching {
   public:
@@ -1451,13 +1453,13 @@
           Node bnode = graph->bNode(jt);
           Value bvalue = avalue + (*cost)[jt] + 
             anode_potential[anode] - bnode_potential[bnode];
+          if (bvalue > bdistMax) {
+            bdistMax = bvalue;
+          }
           if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
             bdist[bnode] = bvalue;
             bpred[bnode] = jt;
-          }
-          if (bvalue > bdistMax) {
-            bdistMax = bvalue;
-          }
+          } else continue;
           if (bnode_matching[bnode] != INVALID) {
             Node newanode = graph->aNode(bnode_matching[bnode]);
             switch (_heap->state(newanode)) {
diff -r 88b81ec599ed -r f26368148b9c lemon/unionfind.h
--- a/lemon/unionfind.h	Sat Dec 29 15:11:41 2007 +0000
+++ b/lemon/unionfind.h	Sun Dec 30 18:23:32 2007 +0000
@@ -962,7 +962,7 @@
 
   private:
 
-    static const int cmax = 3;
+    static const int cmax = 16;
 
     ItemIntMap& index;
 
@@ -1124,6 +1124,7 @@
         nodes[kd].parent = id;
         kd = nodes[kd].next;
       }
+      nodes[id].right = nodes[jd].right;
     }
 
     void split(int id, int jd) {