From 96318dec79e12d23d718139bca74f5d33cd52253 Mon Sep 17 00:00:00 2001 From: Ian Jackson Date: Fri, 28 Dec 2007 17:19:48 +0000 Subject: [PATCH] found stuff, before some rearrangement of edge iterator --- anneal.c | 120 ------------------------------------------------------- bgl.cpp | 79 ++++++++++++++++++++++++++++++++++++ mgraph.c | 35 ++++++++++++++++ mgraph.h | 100 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 214 insertions(+), 120 deletions(-) create mode 100644 bgl.cpp create mode 100644 mgraph.c create mode 100644 mgraph.h diff --git a/anneal.c b/anneal.c index 4ddddb8..32c06d9 100644 --- a/anneal.c +++ b/anneal.c @@ -1,70 +1,7 @@ /* * 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< { + /* 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< + static Reference dereference(type, const int& f) + { return const_cast(f); } + + static bool equal(int x, int y) { return x == y; } + } + struct graph_traits { + /* Concept IncidenceGraph: */ + typedef iterator_adaptor + > 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::out_edge_iterator, + typename graph_traits::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 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() + + + diff --git a/mgraph.c b/mgraph.c new file mode 100644 index 0000000..3233890 --- /dev/null +++ b/mgraph.c @@ -0,0 +1,35 @@ +#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; +} diff --git a/mgraph.h b/mgraph.h new file mode 100644 index 0000000..9f02e88 --- /dev/null +++ b/mgraph.h @@ -0,0 +1,100 @@ +/* + * 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<