From: Ian Jackson <ian@davenant.relativity.greenend.org.uk>
Date: Sat, 29 Dec 2007 15:47:56 +0000 (+0000)
Subject: wip; justify choice of Dijkstra
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=moebius2.git;a=commitdiff_plain;h=0cd9cfd406d72d3d40941f87937b60f0d10f1d4d

wip; justify choice of Dijkstra
---

diff --git a/bgl.cpp b/bgl.cpp
index cdfd858..774be82 100644
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -13,26 +13,20 @@ 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)
 
-/* 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.
   // This mainly means that graph_traits<Layout> has lots of stuff.
@@ -49,16 +43,6 @@ namespace boost {
     OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
   };
-  struct AnyEdgeIncrable {
-    int f;
-    AnyEdgeIncrable& operator++() {
-      f++;
-      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> {
 
@@ -95,28 +79,35 @@ namespace boost {
     }
     inline unsigned num_vertices(const Layout&) { return N; }
 
-    // Concept EdgeListGraph:
-    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);
-    }
-    
 }
 
-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().