starting to make it compile

[moebius2.git] / bgl.cpp

diff --git a/bgl.cpp b/bgl.cpp
index 774be825a1cc53bc017884e94876ddd49c134984..fbc5b7db955017e34a19e28c004ce945cc5becfe 100644 (file)
--- a/bgl.cpp
+++ b/bgl.cpp
@@ -1,5 +1,14 @@
+/*
+ * Everything that needs the Boost Graph Library and C++ templates etc.
+ * (and what a crazy set of stuff that all is)
+ */
+
+#include <math.h>
+
 extern "C" {
+#include "bgl.h"
 #include "mgraph.h"
+#include "common.h"
 }
 
 /*
@@ -27,9 +36,11 @@ extern "C" {
 #define VMASK (YMASK|XMASK)
 #define ESHIFT (YBITS|XBITS)
 
+class Graph { }; // this is a dummy as our graph has no actual representation
+
 namespace boost {
-  // We make Layout a model of various BGL Graph concepts.
-  // This mainly means that graph_traits<Layout> has lots of stuff.
+  // We make Graph a model of various BGL Graph concepts.
+  // This mainly means that graph_traits<Graph> has lots of stuff.
 
   // First, some definitions used later:
   
@@ -44,7 +55,7 @@ namespace boost {
     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
   };
  
-  struct graph_traits<Layout> {
+  struct graph_traits<Graph> {
 
     // Concept Graph:
   
@@ -61,57 +72,74 @@ namespace boost {
       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 int source(int f, const Graph&) { return f&VMASK; }
+    inline int target(int f, const Graph&) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
     inline std::pair<out_edge_iterator,out_edge_iterator>
-    out_edges(int v, const Layout&) {
+    out_edges(int v, const Graph&) {
       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&) { return VE_MAX(v) - VE_MIN(v); }
+    inline out_degree(int v, const Graph&) { 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&) {
+    vertices(const Graph&) {
       return std::make_pair(vertex_iterator(0), vertex_iterator(N));
     }
-    inline unsigned num_vertices(const Layout&) { return N; }
-
-}
-
-struct VertexIndexMap;
+    inline unsigned num_vertices(const Graph&) { return N; }
+  };
+};
 
-namespace boost {
-  struct property_traits<VertexIndexMap> {
-    // Concept Readable Property Map:
-    typedef int value_type, reference, key_type;
-    category 
-class Boost
-  }};
+static void single_source_shortest_paths(int v1,
+                                        const double edge_weights[/*f*/],
+                                        double vertex_distances[/*v*/]) {
+  Graph g;
 
-void single_source_shortest_paths(int v1,
-                                 const double edge_weights[/*f*/],
-                                 ) {
-  boost::dijkstra_shortest_paths
-    (g, v1,
+  boost::dijkstra_shortest_paths(g, v1,
      weight_map(edge_weights).
      vertex_index_map(identity_property_map()).
-     
+     distance_map(vertex_distances));
+}
     
-void all_pairs_shortest_paths(const Layout *g) {
+double graph_layout_cost(const Vertices v, const double vertex_areas[N]) {
+  /* For each (vi,vj) computes shortest path s_ij = |vi..vj|
+   * along edges, and actual distance d_ij = |vi-vj|.
+   *
+   * We will also use the `vertex areas': for each vertex vi the
+   * vertex area a_vi is the mean area of the incident triangles.
+   * This is computed elsewhere.
+   *
+   * Energy contribution is proportional to
+   *
+   *               -4          2
+   *    a  a   .  d   . [ (s/d)  - 1 ]
+   *     vi vj
+   *
+   * (In practice we compute d^2+epsilon and use it for the
+   *  divisions, to avoid division by zero.)
+   */
+  static const d2_epsilon= 1e-6;
   
-  FOR_VERTEX(v1) {
-       
- 0);
-    
-                           /* weight_map(). ? */
-                           /* 
-
-                           
-                           predecessor_map().
-                           distance_map()
-
+  double edge_weights[N*V6], vertex_distances[N], total_cost;
+  int v1,v2,e,f;
 
+  FOR_VEDGE_X(v1,e,v2,
+             f= v1 | e << ESHIFT,
+             edge_weights[f]= NaN)
+    edge_weights[f]= hypotD(v[v1], v[v2]);
 
+  FOR_VERTEX(v1) {
+    double a1= vertex_areas[v1];
+    single_source_shortest_paths(v1, edge_weights, vertex_distances);
+    FOR_VERTEX(v2) {
+      double a2= vertex_areas[v2];
+      double d2= hypotD2plus(v[v1],v[v2], d2_epsilon);
+      double sd= vertex_distances[v2] / d2;
+      double sd2= sd*sd;
+      total_cost += a1*a2 * (sd2 - 1) / (d2*d2);
+    }
+  }
+  return total_cost;
+}