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

diff --git a/bgl.cpp b/bgl.cpp
index 3e2912e..774be82 100644
--- 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().