Changeset 1703:eb90e3d6bddc in lemon-0.x for lemon/full_graph.h

Timestamp:

10/05/05 15:15:47 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Proper sized map type

File:

• lemon/full_graph.h (modified) (7 diffs)

lemon/full_graph.h

@@ -23 +23 @@
 #include <lemon/bits/iterable_graph_extender.h>
 #include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
+#include <lemon/bits/static_map.h>
 
 #include <lemon/bits/undir_graph_extender.h>
@@ -196 +196 @@
   typedef IterableGraphExtender<AlterableFullGraphBase> 
   IterableFullGraphBase;
-  typedef MappableGraphExtender<
+  typedef StaticMappableGraphExtender<
     IterableGraphExtender<
     AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
@@ -299 +299 @@
     /// the next edge from \c u to \c v after \c prev.
     /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
-    {
-      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
-    }
+    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
+      if (prev.id != -1 || u.id <= v.id) return -1;
+      return Edge(u.id * (u.id - 1) / 2 + v.id);
+    }
+
+    typedef True FindEdgeTag;
     
       
@@ -329 +331 @@
       Edge(int _id) : id(_id) {}
 
-      Edge(const UndirFullGraphBase& _graph, int source, int target) 
-        : id(_graph._nodeNum * target+source) {}
     public:
       Edge() { }
@@ -340 +340 @@
 
     void first(Node& node) const {
-      node.id = _nodeNum-1;
+      node.id = _nodeNum - 1;
     }
 
@@ -348 +348 @@
 
     void first(Edge& edge) const {
-      edge.id = _edgeNum-1;
+      edge.id = _edgeNum - 1;
     }
 
@@ -356 +356 @@
 
     void firstOut(Edge& edge, const Node& node) const {      
-      edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
+      int src = node.id;
+      int trg = 0;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
     }
 
     /// \todo with specialized iterators we can make faster iterating
-    void nextOut(Edge& e) const {
-      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
-      int target = e.id - (source) * (source - 1) / 2; 
-      ++target;
-      e.id = target < source ? source * (source - 1) / 2 + target : -1;
+    void nextOut(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++trg;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
     }
 
     void firstIn(Edge& edge, const Node& node) const {
-      edge.id = node.id * (node.id + 1) / 2 - 1;
-    }
-    
-    void nextIn(Edge& e) const {
-      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
-      int target = e.id - (source) * (source - 1) / 2; ++target;
-      ++source;
-      e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
+      int src = node.id + 1;
+      int trg = node.id;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
+    }
+    
+    void nextIn(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++src;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
     }
 
   };
 
-  typedef MappableUndirGraphExtender<
+  typedef StaticMappableUndirGraphExtender<
     IterableUndirGraphExtender<
     AlterableUndirGraphExtender<