+/*
+ * Everything that needs the Boost Graph Library and C++ templates etc.
+ * (and what a crazy set of stuff that all is)
+ */
+
+#include <math.h>
+
+#include <iterator>
+
+#include <boost/config.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/iterator/counting_iterator.hpp>
+#include <boost/iterator/iterator_categories.hpp>
+
extern "C" {
+#include "bgl.h"
#include "mgraph.h"
}
/*
- * edge descriptor f = 00 | e | y | x
- * 3 YBITS XBITS
+ * edge descriptor f = 0000 | e | y | x
+ * 3 YBITS XBITS
*
- * e is 0..5. The edge is edge e out of vertex (x,y).
+ * e is 0..6. The edge is edge e out of vertex (x,y), or if
+ * e==6 it's the `at end' value for the out edge iterator.
*
* BGL expects an undirected graph's edges to have two descriptors
- * each, one in each direction.
+ * each, one in each direction (otherwise e would be just 0..2).
*/
/*
- * 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)
+#define ESHIFT (YBITS+XBITS)
+
+using namespace boost;
+
+/*
+ * We iterate over edges in the following order:
+ *
+ * \#0 /1#
+ * \ /
+ * ___ 0 __
+ * #2 1 #3
+ * / \
+ * #4/ #5\ and finally #6 is V6
+ *
+ *
+ * This ordering permits the order-4 nodes at the strip's edge
+ * to have a contiguous edge iterator values. The iterator
+ * starts at #0 which is edge 2 (see mgraph.h), or #2 (edge 3).
+ */
+static const int oei_edge_delta[V6]=
+ /* 0 1 2 3 4 5 initial e
+ * #3 #1 #0 #2 #4 #5 initial ix
+ * #4 #2 #1 #3 #5 #6 next ix
+ * 4 3 1 0 5 V6 next e
+ */ {
+ 4<<ESHIFT, 2<<ESHIFT, -1<<ESHIFT,
+ -3<<ESHIFT, 1<<ESHIFT, (V6-5)<<ESHIFT
+};
+
+class OutEdgeIterator :
+ public iterator_facade<
+ OutEdgeIterator,
+ int const,
+ forward_traversal_tag
+> {
+ int f;
+ public:
+ void increment() {
+ //printf("incrementing f=%03x..",f);
+ f += oei_edge_delta[f>>ESHIFT];
+ //printf("%03x\n",f);
+ }
+ bool equal(OutEdgeIterator const& other) const { return f == other.f; }
+ int const& dereference() const { return f; }
+ OutEdgeIterator() { }
+ OutEdgeIterator(int _f) : f(_f) { }
+ OutEdgeIterator(int v, int e) : f(e<<ESHIFT | v) {
+ //printf("constructed v=%02x e=%x f=%03x\n",v,e,f);
+ }
+
+ static int voe_min(int _v) { return (_v & YMASK) ? 2 : 3; }
+ static int voe_max(int _v) { return (_v & YMASK)==(Y-1) ? V6 : 4; }
+ static int voe_degree(int _v) { return RIM_VERTEX_P(_v) ? 4 : V6; }
+};
+
+typedef counting_iterator<int> VertexIterator;
namespace boost {
- // We make Layout a model of various BGL Graph concepts.
- // This mainly means that graph_traits<Layout> has lots of stuff.
+ class Graph { }; // this is a dummy as our graph has no actual representation
+
+ // 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:
struct layout_graph_traversal_category :
public virtual incidence_graph_tag,
- public virtual edge_list_graph_tag
- public virtual vertex_list_graph_tag { };
-
- struct OutEdgeIncrable {
- int f;
- OutEdgeIncrable operator++(OutEdgeIncrable f) { return f + 1<<ESHIFT; }
- OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
- }
-
- struct graph_traits<Layout> {
+ public virtual vertex_list_graph_tag,
+ public virtual edge_list_graph_tag { };
+ template<>
+ struct graph_traits<Graph> {
// Concept Graph:
-
typedef int vertex_descriptor; /* vertex number, -1 => none */
typedef int edge_descriptor; /* see above */
typedef undirected_tag directed_category;
- typedef disallow_parallel_ege edge_parallel_category;
+ typedef disallow_parallel_edge_tag edge_parallel_category;
typedef layout_graph_traversal_category traversal_category;
- inline int null_vertex() { return -1; }
// Concept IncidenceGraph:
-
- typedef counting_iterator<OutEdgeIncrable,
- 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) {
- 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); }
+ typedef OutEdgeIterator out_edge_iterator;
+ typedef unsigned degree_size_type;
// Concept VertexListGraph:
- typedef counting_iterator<int> vertex_iterator;
+ typedef VertexIterator vertex_iterator;
+ typedef unsigned vertices_size_type;
+ };
-}
+ // Concept Graph:
+ inline int null_vertex() { return -1; }
-void calculate_layout_energy(const Layout*) {
-
- FOR_VERTEX(v1) {
- boost::dijkstra_shortest_paths(g, v1, 0);
-
- /* weight_map(). ? */
- /* vertex_index_map(vimap). */
+ // Concept IncidenceGraph:
+ inline int source(int f, const Graph&) { return f&VMASK; }
+ inline int target(int f, const Graph&) {
+ int v2= EDGE_END2(f&VMASK, f>>ESHIFT);
+ //printf("traversed %03x..%02x\n",f,v2);
+ return v2;
+ }
+ inline std::pair<OutEdgeIterator,OutEdgeIterator>
+ out_edges(int v, const Graph&) {
+ return std::make_pair(OutEdgeIterator(v, OutEdgeIterator::voe_min(v)),
+ OutEdgeIterator(v, OutEdgeIterator::voe_max(v)));
+ }
+ inline unsigned out_degree(int v, const Graph&) {
+ return OutEdgeIterator::voe_degree(v);
+ }
+
+ // Concept VertexListGraph:
+ inline
+ std::pair<VertexIterator,VertexIterator> vertices(const Graph&) {
+ return std::make_pair(VertexIterator(0), VertexIterator(N));
+ }
+ inline unsigned num_vertices(const Graph&) { return N; }
+};
-
- predecessor_map().
- distance_map()
+static void single_source_shortest_paths(int v1,
+ const double edge_weights[/*f*/],
+ double vertex_distances[/*v*/]) {
+ Graph g;
+ dijkstra_shortest_paths(g, v1,
+ weight_map(edge_weights).
+ vertex_index_map(identity_property_map()).
+ distance_map(vertex_distances));
+}
+
+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 double d2_epsilon= 1e-6;
+
+ double edge_weights[V6<<ESHIFT], vertex_distances[N], total_cost=0;
+ int v1,v2,e,f;
+ FOR_VERTEX(v1)
+ 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) {
+ if (v1 == v2) continue;
+ double a2= vertex_areas[v2];
+ double d2= hypotD2plus(v[v1],v[v2], d2_epsilon);
+ double s= vertex_distances[v2];
+ double s2= s*s + d2_epsilon;
+ double sd2= s2 / d2;
+ double cost_contrib= a1*a2 * (sd2 - 1) / (d2*d2);
+ if (cost_contrib < -1e-4) {
+ printf("layout %03x..%03x (a=%g,%g) s=%g s2=%g d2=%g sd2=%g"
+ " cost+=%g\n", v1,v2, a1,a2, s,s2,d2,sd2, cost_contrib);
+ abort();
+ }
+ total_cost += cost_contrib;
+ }
+ }
+ return total_cost;
+}