+/*
+ * 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"
}
/*
#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:
OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
};
- struct graph_traits<Layout> {
+ struct graph_traits<Graph> {
// Concept Graph:
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; }
-
-}
+ inline unsigned num_vertices(const Graph&) { return N; }
+ };
+};
static void single_source_shortest_paths(int v1,
const double edge_weights[/*f*/],
double vertex_distances[/*v*/]) {
- boost::dijkstra_shortest_paths
- (g, v1,
+ Graph g;
+
+ boost::dijkstra_shortest_paths(g, v1,
weight_map(edge_weights).
vertex_index_map(identity_property_map()).
distance_map(vertex_distances));
}
-double graph_layout_cost(const Layout *g, const double vertex_areas[N]) {
+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|.
*
* (In practice we compute d^2+epsilon and use it for the
* divisions, to avoid division by zero.)
*/
+ static const d2_epsilon= 1e-6;
+
double edge_weights[N*V6], vertex_distances[N], total_cost;
- int v1, e, f;
+ int v1,v2,e,f;
- FOR_VEDGE_X(v1,e,
+ FOR_VEDGE_X(v1,e,v2,
f= v1 | e << ESHIFT,
edge_weights[f]= NaN)
- edge_weights[f]= hypotD(g.v[v1], g.v[v2]);
+ 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(g->v[v1],g->v[v2], d2_epsilon);
+ double d2= hypotD2plus(v[v1],v[v2], d2_epsilon);
double sd= vertex_distances[v2] / d2;
double sd2= sd*sd;
- total_cost= fma_fast(a1*a2, (sd2 - 1.0)/(d2*d2), total_cost);
+ total_cost += a1*a2 * (sd2 - 1) / (d2*d2);
}
}
return total_cost;