/*
* We try to find an optimal triangle grid
- *
- * Vertices in strip are numbered as follows:
- *
- * ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3 ___ 4 __
- * Y-1 Y-1 0 0 0 0 0
- * / \ / \ / \ / \ / \ / \ / \
- * / \ / \ / \ / \ / \ / \ / \
- * X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3 ___ 4
- * Y-2 Y-2 Y-2 1 1 1 1 1
- * \ / \ / \ / \ / \ / \ / \ /
- * \ / \ / \ / \ / \ / \ / \ /
- * ___ X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3 __
- * Y-3 Y-3 Y-3 2 2 2 2
- *
- * . . . . . . . . . . . . . . .
- *
- * X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3
- * 1 1 1 1 Y-2 Y-2 Y-2 Y-2
- * \ / \ / \ / \ / \ / \ / \ /
- * \ / \ / \ / \ / \ / \ / \ /
- * ___ X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 __
- * 0 0 0 0 Y-1 Y-1 Y-1
- *
- * Node x,y for
- * 0 <= x < X x = distance along
- * 0 <= y < Y y = distance across
- *
- * Vertices are in reading order from diagram above ie x varies fastest.
- *
- * Y must be even. The actual location opposite (0,0) is (X-(Y-1)/2,0),
- * and likewise opposite (0,Y-1) is ((Y-1)/2,0).
- *
- * To label edges, we counte anticlockwise[*] from to-the-right:
- *
- * \2 /1
- * \ /
- * ___ 0 __
- * 3 1 0
- * / \
- * 4/ 5\
- *
- * [*] That is, in the direction represented as anticlockwise for
- * the vertices (0,*)..(4,*) in the diagram above; and of course
- * that is clockwise for the vertices (X-5,*)..(X-1,*). The
- * numbering has an actual discontinuity between (X-1,*) and (0,*).
- *
- * When we iterate over edges, we iterate first over vertices and then
- * over edges 0 to 2, disregarding edges 3 to 5.
*/
-#define XBITS 4
-#define X (1<<XBITS)
-#define YBITS 4
-#define Y (1<<YBITS)
-
-/* vertex number: 0000 | y | x
- * YBITS XBITS
- */
-
-#define N (X*Y)
-#define XMASK (X-1)
-#define YSHIFT XBITS
-#define Y1 (1 << YSHIFT)
-#define YMASK (Y-1 << YSHIFT)
-
/* Energy has the following parts right now:
*/
/*
* and the huge energy ought then to be sufficient for the model to
* avoid being close to R=S. */
-#define V6 6
-
-static int edge_end2(unsigned v1, int e) {
- /* The topology is equivalent to that of a square lattice with only
- * half of the diagonals. Ie, the result of shearing the triangular
- * lattice to make the lines of constant x vertical. This gives
- * these six directions:
- *
- * 2 1
- * | /
- * |/
- * 3--*--0
- * /|
- * / |
- * 4 5
- *
- * This also handily makes vertical the numbering discontinuity,
- * where the join happens.
- */
- static const unsigned dx[V6]= { +1, +1, 0, -1, -1, 0 },
- dy[V6]= { 0, +Y1, +Y1, 0, -Y1, -Y1 };
- unsigned x, y;
-
- y= (v1 & YMASK) + dy[e];
- if (y & ~YMASK) return -1;
-
- x= (v1 & XMASK) + dx[e];
- if (x & ~XMASK) {
- y= (Y-1)*Y1 - y;
- x &= XMASK;;
- }
- return x | y;
-}
-
-#define D3 3
-
-#define FOR_VERTEX(v) \
- for ((v)=0; (v)<N; (v)++)
-
-#define FOR_VPEDGE(v,e) \
- for ((e)=0; (e)<V6; (e)++)
-
-#define EDGE_END2 edge_end2
-
-#define FOR_VEDGE(v1,e,v2) \
- FOR_VPEDGE((v1),(e))
- if (((v2)= EDGE_END2((v1),(e))) < 0) ; else
-
-#define FOR_EDGE(v1,e,v2) \
- FOR_VERTEX((v1)) \
- FOR_VEDGE((v1),(e),(v2))
-
-#define FOR_COORD(k) \
- for ((k)=0; (k)<D3; (k)++)
-
-#define K FOR_COORD(k)
-
static double hypotD(const double p[], const double q[]) {
int k;
double pq[D3];
--- /dev/null
+extern "C" {
+#include "mgraph.h"
+}
+
+/*
+ * edge descriptor f = 00 | e | y | x
+ * 2 YBITS XBITS
+ *
+ * e is 0,1 or 2. The edge is edge e out of vertex (x,y).
+ */
+
+/*
+ * We use BGL's implementation of Johnson All Pairs Shortest Paths
+ */
+
+#define VMASK (YMASK|XMASK)
+#define ESHIFT (YBITS|XBITS)
+
+namespace boost {
+ struct layout_graph_traversal_category :
+ public virtual incidence_graph_tag,
+ public virtual edge_list_graph_tag
+ public virtual vertex_list_graph_tag { };
+
+ struct graph_traits<Layout> {
+ /* 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 layout_graph_traversal_category traversal_category;
+ inline int null_vertex() { return -1; }
+ }
+ struct out_edge_iterator_policies {
+ static void increment(int& f) { f += 1<<ESHIFT; }
+ static void decrement(int& f) { f -= 1<<ESHIFT; }
+
+ template <class Reference>
+ static Reference dereference(type<Reference>, const int& f)
+ { return const_cast<Reference>(f); }
+
+ static bool equal(int x, int y) { return x == y; }
+ }
+ struct graph_traits<Layout> {
+ /* Concept IncidenceGraph: */
+ typedef iterator_adaptor<int, out_edge_iterator_policies,
+ iterator<std::bidirectional_iterator_tag,int>
+ > out_edge_iterator;
+
+ 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(VE_MIN(v), VE_MAX(v));
+ }
+
+ out_edge_iterator> {
+
+
+ /* Concept VertexListGraph: */
+ typedef counting_iterator<int> vertex_iterator;
+
+}
+
+void calculate_layout_energy(const Layout*) {
+
+ FOR_VERTEX(v1) {
+ boost::dijkstra_shortest_paths(g, v1, 0);
+
+ /* weight_map(). ? */
+ /* vertex_index_map(vimap). */
+
+
+ predecessor_map().
+ distance_map()
+
+
+
--- /dev/null
+#include "mgraph.h"
+
+static const unsigned dx[V6]= { 0, +1, -1, +1, -1, 0 },
+ dy[V6]= { +Y1, +Y1, 0, 0, -Y1, -Y1 };
+
+
+int edge_end2(unsigned v1, int e) {
+ /* The topology is equivalent to that of a square lattice with only
+ * half of the diagonals. Ie, the result of shearing the triangular
+ * lattice to make the lines of constant x vertical. This gives
+ * these six directions:
+ *
+ * 0 1
+ * | /
+ * |/
+ * 2--*--3
+ * /|
+ * / |
+ * 4 5
+ *
+ * This also handily makes vertical the numbering discontinuity,
+ * where the join happens.
+ */
+ unsigned x, y;
+
+ y= (v1 & YMASK) + dy[e];
+ if (y & ~YMASK) return -1;
+
+ x= (v1 & XMASK) + dx[e];
+ if (x & ~XMASK) {
+ y= (Y-1)*Y1 - y;
+ x &= XMASK;;
+ }
+ return x | y;
+}
--- /dev/null
+/*
+ * Vertices in strip are numbered as follows:
+ *
+ * ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3 ___ 4 __
+ * Y-1 Y-1 0 0 0 0 0
+ * / \ / \ / \ / \ / \ / \ / \
+ * / \ / \ / \ / \ / \ / \ / \
+ * X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3 ___ 4
+ * Y-2 Y-2 Y-2 1 1 1 1 1
+ * \ / \ / \ / \ / \ / \ / \ /
+ * \ / \ / \ / \ / \ / \ / \ /
+ * ___ X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3 __
+ * Y-3 Y-3 Y-3 2 2 2 2
+ *
+ * . . . . . . . . . . . . . . .
+ *
+ * X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 ___ 3
+ * 1 1 1 1 Y-2 Y-2 Y-2 Y-2
+ * \ / \ / \ / \ / \ / \ / \ /
+ * \ / \ / \ / \ / \ / \ / \ /
+ * ___ X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0 ___ 1 ___ 2 __
+ * 0 0 0 0 Y-1 Y-1 Y-1
+ *
+ * Node x,y for
+ * 0 <= x < X x = distance along
+ * 0 <= y < Y y = distance across
+ *
+ * Vertices are in reading order from diagram above ie x varies fastest.
+ *
+ * Y must be even. The actual location opposite (0,0) is (X-(Y-1)/2,0),
+ * and likewise opposite (0,Y-1) is ((Y-1)/2,0).
+ *
+ * We label edges as follows:
+ *
+ * \0 /1
+ * \ /
+ * ___ 0 __
+ * 2 1 3
+ * / \
+ * 4/ 5\
+ *
+ * (This numbering permits the order-4 nodes at the strip's edge
+ * to have a contiguous edge numbering 2..5 or 0..3.)
+ *
+ * When we iterate over edges, we iterate first over vertices and then
+ * over edges 0 to 2, disregarding edges 3 to 5.
+ */
+
+#ifndef MGRAPH_H
+#define MGRAPH_H
+
+#define XBITS 4
+#define X (1<<XBITS)
+#define YBITS 4
+#define Y (1<<YBITS)
+
+/* vertex number: 0000 | y | x
+ * YBITS XBITS
+ */
+
+#define N (X*Y)
+#define XMASK (X-1)
+#define YSHIFT XBITS
+#define Y1 (1 << YSHIFT)
+#define YMASK (Y-1 << YSHIFT)
+
+#define V6 6
+
+#define D3 3
+
+#define FOR_VERTEX(v) \
+ for ((v)=0; (v)<N; (v)++)
+
+#define VE_MIN(v) ((v) & YMASK ? 0 : 2)
+#define VE_MAX(v) (~(v) & YMASK ? V6 : 4)
+
+#define FOR_VPEDGE(v,e) \
+ for ((e)=VE_MIN(v); (e)<VE_MAX(v); (e)++)
+
+extern int edge_end2(unsigned v1, int e);
+#define EDGE_END2 edge_end2
+
+#define FOR_VEDGE(v1,e) \
+ FOR_VPEDGE((v1),(e))
+ if (((v2)= EDGE_END2((v1),(e))) < 0) ; else
+
+#define FOR_EDGE(v1,e,v2) \
+ FOR_VERTEX((v1)) \
+ FOR_VEDGE((v1),(e),(v2))
+
+#define FOR_COORD(k) \
+ for ((k)=0; (k)<D3; (k)++)
+
+#define K FOR_COORD(k)
+
+typedef struct {
+ double v[N][D3];
+} Layout;
+
+#endif /*MGRAPH_H*/
~ian / moebius2.git / commitdiff