X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=bgl.cpp;h=3e2912ebb07bdd56c05c3a23f6104c2aa025ed06;hb=f9088d46488d2241f9a8e4a15e0cf4cecae02785;hp=20ddaa328e42f660f5604e044a9ae342451e4f0a;hpb=96318dec79e12d23d718139bca74f5d33cd52253;p=moebius2.git

diff --git a/bgl.cpp b/bgl.cpp
index 20ddaa3..3e2912e 100644
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -4,9 +4,12 @@ extern "C" {
 
 /*
  * edge descriptor f =   00 | e | y     | x
- *                            2  YBITS   XBITS
+ *                            3  YBITS   XBITS
  *
- * e is 0,1 or 2.  The edge is edge e out of vertex (x,y).
+ * e is 0..5.  The edge is edge e out of vertex (x,y).
+ *
+ * BGL expects an undirected graph's edges to have two descriptors
+ * each, one in each direction.
  */
 
 /*
@@ -15,50 +18,53 @@ extern "C" {
 
 #define VMASK (YMASK|XMASK)
 #define ESHIFT (YBITS|XBITS)
+#define FMAX ((5 << ESHIFT) | VMASK)
 
 namespace boost {
+  // We make Layout a model of various BGL Graph concepts.
+  // This mainly means that graph_traits<Layout> has lots of stuff.
+
+  // First, some definitions used later:
+  
   struct layout_graph_traversal_category : 
     public virtual incidence_graph_tag,
     public virtual edge_list_graph_tag
     public virtual vertex_list_graph_tag { };
   
+  struct OutEdgeIncrable {
+    int f;
+    OutEdgeIncrable operator++(OutEdgeIncrable f) { return f + 1<<ESHIFT; }
+    OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
+  }
+    
   struct graph_traits<Layout> {
-    /* Concept Graph: */
+
+    // Concept Graph:
+  
     typedef int vertex_descriptor; /* vertex number, -1 => none */
     typedef int edge_descriptor; /* see above */
     typedef undirected_tag directed_category;
     typedef disallow_parallel_ege edge_parallel_category;
     typedef layout_graph_traversal_category traversal_category;
     inline int null_vertex() { return -1; }
-  }
-  struct out_edge_iterator_policies {
-    static void increment(int& f) { f += 1<<ESHIFT; }
-    static void decrement(int& f) { f -= 1<<ESHIFT; }
-
-    template <class Reference>
-    static Reference dereference(type<Reference>, const int& f)
-    { return const_cast<Reference>(f); }
 
-    static bool equal(int x, int y) { return x == y; }
-  }
-  struct graph_traits<Layout> {
-    /* Concept IncidenceGraph: */
-    typedef iterator_adaptor<int, out_edge_iterator_policies,
-      iterator<std::bidirectional_iterator_tag,int>
-    > out_edge_iterator;
+    // Concept IncidenceGraph:
+    
+    typedef counting_iterator<OutEdgeIncrable,
+      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 std::pair<typename graph_traits<Layout>::out_edge_iterator,
                      typename graph_traits<Layout>::out_edge_iterator>
     out_edges(int v, const Layout& g) {
-      return std::make_pair(VE_MIN(v), VE_MAX(v));
+      return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
+			    out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
     }
-  
-    out_edge_iterator> {
-
+    out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
 
-    /* Concept VertexListGraph: */
+    // Concept VertexListGraph:
     typedef counting_iterator<int> vertex_iterator;
     
 }