chiark / gitweb /
found stuff, before some rearrangement of edge iterator
authorIan Jackson <ian@davenant.relativity.greenend.org.uk>
Fri, 28 Dec 2007 17:19:48 +0000 (17:19 +0000)
committerIan Jackson <ian@davenant.relativity.greenend.org.uk>
Fri, 28 Dec 2007 17:19:48 +0000 (17:19 +0000)
anneal.c
bgl.cpp [new file with mode: 0644]
mgraph.c [new file with mode: 0644]
mgraph.h [new file with mode: 0644]

index 4ddddb8..32c06d9 100644 (file)
--- 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<<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];
diff --git a/bgl.cpp b/bgl.cpp
new file mode 100644 (file)
index 0000000..20ddaa3
--- /dev/null
+++ b/bgl.cpp
@@ -0,0 +1,79 @@
+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()
+
+
+
diff --git a/mgraph.c b/mgraph.c
new file mode 100644 (file)
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 (file)
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<<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*/