Changeset 2506:216c6bd5c18c in lemon-0.x

Timestamp:

10/30/07 21:44:53 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Change to new union-find interface

Location:

lemon

Files:

• nagamochi_ibaraki.h (modified) (3 diffs)
• unionfind.h (modified) (2 diffs)

lemon/nagamochi_ibaraki.h

@@ -1375 +1375 @@
       for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) {
         if (ufe.size(c) == 1) continue;
+        Node cn = ufe.item(c);
         for (typename Ufe::ItemIt r(ufe, c); r != INVALID; ++r) {
-          if (static_cast<Node>(r) == static_cast<Node>(c)) continue;
-          _next->set((*_last)[c], (*_first)[r]);
-          _last->set(c, (*_last)[r]);
+          if (static_cast<Node>(r) == static_cast<Node>(cn)) continue;
+          _next->set((*_last)[cn], (*_first)[r]);
+          _last->set(cn, (*_last)[r]);
           remnodes.push_back(r);
           --_node_num;
@@ -1389 +1390 @@
       for (typename AuxGraph::UEdgeIt e(*_aux_graph);
            e != INVALID; ++e) {
-        Node sn = ufe.find(_aux_graph->source(e));
-        Node tn = ufe.find(_aux_graph->target(e));
-        if ((ufe.size(sn) == 1 && ufe.size(tn) == 1)) {
+        int sc = ufe.find(_aux_graph->source(e));
+        int tc = ufe.find(_aux_graph->target(e));
+        if ((ufe.size(sc) == 1 && ufe.size(tc) == 1)) {
           continue;
         }
-        if (sn == tn) {
+        if (sc == tc) {
           remedges.push_back(e);
           continue;
         }
+        Node sn = ufe.item(sc);
+        Node tn = ufe.item(tc);
+
         EdgeInfo info;
         if (sn < tn) {
@@ -1436 +1440 @@
       for (typename Ufe::ClassIt c(ufe); c != INVALID; ++c) {
         if (ufe.size(c) == 1) continue;
+        Node cn = ufe.item(c);
         Value cutvalue = 0;
-        for (typename AuxGraph::IncEdgeIt e(*_aux_graph, c);
+        for (typename AuxGraph::IncEdgeIt e(*_aux_graph, cn);
              e != INVALID; ++e) {
           cutvalue += (*_aux_capacity)[e];
         }
         
-        (*_aux_cut_value)[c] = cutvalue;
+        (*_aux_cut_value)[cn] = cutvalue;
         
       }

lemon/unionfind.h

@@ -475 +475 @@
       }
 
-    }    
+    }
+
+    /// \brief Gives back a representant item of the component.
+    ///
+    /// Gives back a representant item of the component.
+    Item item(int cls) const {
+      return items[classes[cls].firstItem].item;
+    }
 
     /// \brief Removes the component of the given element from the structure.
@@ -733 +740 @@
       return items[index[item]].cls;
     }
+
+    /// \brief Gives back a representant item of the component.
+    ///
+    /// Gives back a representant item of the component.
+    Item item(int cls) const {
+      return items[classes[cls].firstItem].item;
+    }
     
     /// \brief Removes the given element from the structure.