wip; justify choice of Dijkstra

[moebius2.git] / bgl.cpp

diff --git a/bgl.cpp b/bgl.cpp
index 3e2912ebb07bdd56c05c3a23f6104c2aa025ed06..774be825a1cc53bc017884e94876ddd49c134984 100644 (file)
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -13,12 +13,19 @@ extern "C" {
  */
 
 /*
- * 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)
-#define FMAX ((5 << ESHIFT) | VMASK)
 
 namespace boost {
   // We make Layout a model of various BGL Graph concepts.
@@ -28,15 +35,15 @@ namespace boost {
   
   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++(OutEdgeIncrable f) { return f + 1<<ESHIFT; }
+    OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
-  }
-    
+  };
+ 
   struct graph_traits<Layout> {
 
     // Concept Graph:
@@ -54,28 +61,53 @@ 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 std::pair<typename graph_traits<Layout>::out_edge_iterator,
-                     typename graph_traits<Layout>::out_edge_iterator>
-    out_edges(int v, const Layout& g) {
+    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_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&) {
+      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().