wip; justify choice of Dijkstra

[moebius2.git] / bgl.cpp

diff --git a/bgl.cpp b/bgl.cpp
index 20ddaa328e42f660f5604e044a9ae342451e4f0a..774be825a1cc53bc017884e94876ddd49c134984 100644 (file)
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -4,72 +4,110 @@ 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.
  */
 
 /*
- * We use BGL's implementation of Johnson All Pairs Shortest Paths
+ * We use BGL's implementation of Dijkstra's single source shortest
+ * paths.  We really want all pairs shortest paths, so Johnson All
+ * Pairs Shortest Paths would seem sensible.  But actually Johnson's
+ * algorithm is just a wrapper around Dijkstra's; the extra
+ * functionality is just to deal with -ve edge weights, which we don't
+ * have.  So we can use Dijkstra directly and save some cpu (and some
+ * code: we don't have to supply all of the machinery needed for
+ * Johnson's invocation of Bellman-Ford).  The overall time cost is
+ * O(VE log V); I think the space used is O(E).
  */
 
 #define VMASK (YMASK|XMASK)
 #define ESHIFT (YBITS|XBITS)
 
 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 { };
+    public virtual vertex_list_graph_tag,
+    public virtual edge_list_graph_tag { };
   
+  struct OutEdgeIncrable {
+    int f;
+    OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
+    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:
     
-    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));
+    typedef counting_iterator<OutEdgeIncrable,
+      forward_iterator_tag> out_edge_iterator;
+    typedef int degree_size_type;
+    
+    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&) {
+      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&) { return VE_MAX(v) - VE_MIN(v); }
 
-
-    /* Concept VertexListGraph: */
+    // Concept VertexListGraph:
     typedef counting_iterator<int> vertex_iterator;
-    
+    typedef unsigned vertices_size_type;
+    inline std::pair<vertex_iterator,vertex_iterator>
+    vertices(const Layout&) {
+      return std::make_pair(vertex_iterator(0), vertex_iterator(N));
+    }
+    inline unsigned num_vertices(const Layout&) { return N; }
+
 }
 
-void calculate_layout_energy(const Layout*) {
+struct VertexIndexMap;
+
+namespace boost {
+  struct property_traits<VertexIndexMap> {
+    // Concept Readable Property Map:
+    typedef int value_type, reference, key_type;
+    category 
+class Boost
+  }};
+
+void single_source_shortest_paths(int v1,
+                                 const double edge_weights[/*f*/],
+                                 ) {
+  boost::dijkstra_shortest_paths
+    (g, v1,
+     weight_map(edge_weights).
+     vertex_index_map(identity_property_map()).
+     
+    
+void all_pairs_shortest_paths(const Layout *g) {
   
   FOR_VERTEX(v1) {
-    boost::dijkstra_shortest_paths(g, v1, 0);
+       
+ 0);
     
                            /* weight_map(). ? */
-                           /* vertex_index_map(vimap). */
+                           /* 
 
                            
                            predecessor_map().