Changeset 2550:f26368148b9c in lemon-0.x

Timestamp:

12/30/07 19:23:32 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3427

Message:

Changing degree of tournament tree
Bug fix in union find
Small efficiency improvment in bipartite matchings

Location:

lemon

Files:

• bipartite_matching.h (modified) (6 diffs)
• unionfind.h (modified) (2 diffs)

lemon/bipartite_matching.h

@@ -579 +579 @@
   /// \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;
@@ -592 +592 @@
     ///
     /// 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.
@@ -645 +645 @@
   template <typename _BpUGraph, 
             typename _WeightMap = typename _BpUGraph::template UEdgeMap<int>,
-            typename _Traits = WeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
+            typename _Traits = 
+            MaxWeightedBipartiteMatchingDefaultTraits<_BpUGraph, _WeightMap> >
 #endif
   class MaxWeightedBipartiteMatching {
@@ -865 +866 @@
           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]);
@@ -1242 +1243 @@
   template <typename _BpUGraph, 
             typename _CostMap = typename _BpUGraph::template UEdgeMap<int>,
-            typename _Traits = MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
+            typename _Traits = 
+            MinCostMaxBipartiteMatchingDefaultTraits<_BpUGraph, _CostMap> >
 #endif
   class MinCostMaxBipartiteMatching {
@@ -1452 +1454 @@
           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]);

lemon/unionfind.h

@@ -963 +963 @@
   private:
 
-    static const int cmax = 3;
+    static const int cmax = 16;
 
     ItemIntMap& index;
@@ -1125 +1125 @@
         kd = nodes[kd].next;
       }
+      nodes[id].right = nodes[jd].right;
     }