chiark / gitweb /
before delete edgelistgraph
authorIan Jackson <ian@davenant.relativity.greenend.org.uk>
Sat, 29 Dec 2007 13:01:41 +0000 (13:01 +0000)
committerIan Jackson <ian@davenant.relativity.greenend.org.uk>
Sat, 29 Dec 2007 13:01:41 +0000 (13:01 +0000)
bgl.cpp

diff --git a/bgl.cpp b/bgl.cpp
index 4ed2537..cdfd858 100644 (file)
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -19,6 +19,19 @@ extern "C" {
 #define VMASK (YMASK|XMASK)
 #define ESHIFT (YBITS|XBITS)
 
+/* When we enumerate the edges we mainly just increment f.
+ * To avoid nonexistent edges
+ *  we start with                           e=0 | y=1  | x=0
+ *  and explicitly skip                     e=1 | y=0  | ...
+ * We go only up to                         e=2 | YMAX | XMAX
+ *  ie we stop just before                  e=3 | y=0  | x=0
+ *  so that we get each edge once rather than twice.
+ */
+
+#define F_ALL_MIN      (1 << YSHIFT)
+#define F_ALL_MAX      (3 << ESHIFT)
+#define F_ALL_SKIP_AT  (1 << ESHIFT)
+#define F_ALL_SKIP_SET (1 << YSHIFT)
 
 namespace boost {
   // We make Layout a model of various BGL Graph concepts.
@@ -33,21 +46,19 @@ namespace boost {
   
   struct OutEdgeIncrable {
     int f;
-    OutEdgeIncrable operator++(OutEdgeIncrable i) {
-      f += 1<<ESHIFT;
-      return self;
-    }
+    OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
-  }
+  };
   struct AnyEdgeIncrable {
     int f;
-    AnyEdgeIncrable operator++(AnyEdgeIncrable f) {
+    AnyEdgeIncrable& operator++() {
       f++;
-      if (!(f & XMASK)) {
-       if (!(f & YMASK) && (f & EMASK) < (2 << EMASK)) { f += Y1; }
-       
-
-      return f + 1<<ESHIFT; }
+      if (f == F_ALL_SKIP_AT) f |= F_ALL_SKIP_SET
+      return self;
+    }
+    AnyEdgeIncrable(int _f) : f(_f) { }
+    AnyEdgeIncrable() : f(F_ALL_MIN) { }
+  };
  
   struct graph_traits<Layout> {
 
@@ -66,27 +77,36 @@ namespace boost {
       forward_iterator_tag> out_edge_iterator;
     typedef int degree_size_type;
     
-    inline int source(int f, const Layout& g) { return f&VMASK; }
-    inline int target(int f, const Layout& g) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
+    inline int source(int f, const Layout&) { return f&VMASK; }
+    inline int target(int f, const Layout&) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
     inline std::pair<out_edge_iterator,out_edge_iterator>
-    out_edges(int v, const Layout& g) {
+    out_edges(int v, const Layout&) {
       return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
                            out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
     }
-    out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
+    out_degree(int v, const Layout&) { return VE_MAX(v) - VE_MIN(v); }
 
     // Concept VertexListGraph:
     typedef counting_iterator<int> vertex_iterator;
     typedef unsigned vertices_size_type;
     inline std::pair<vertex_iterator,vertex_iterator>
-    vertices(const Layout& g) {
+    vertices(const Layout&) {
       return std::make_pair(vertex_iterator(0), vertex_iterator(N));
     }
-    inline unsigned num_vertices(const Layout& g) { return N; }
+    inline unsigned num_vertices(const Layout&) { return N; }
 
     // Concept EdgeListGraph:
-    typedef counting_iterator<int> edge_iterator;
-    inline std::pair
+    typedef counting_iterator<AnyEdgeIncrable,
+      forward_iterator_tag> edge_iterator;
+    typedef unsigned edges_size_type;
+    inline std::pair<edge_iterator,edge_iterator>
+    edges(const Layout&) {
+      return std::make_pair(edge_iterator(AnyEdgeIncrable()),
+                           edge_iterator(AnyEdgeIncrable(F_ALL_MAX)));
+    }
+    unsigned num_edges(const Layout&) {
+      return F_ALL_MAX - F_ALL_MIN - ((F_SKIP_SET|F_SKIP_AT) - F_SKIP_AT);
+    }
     
 }