mgraph.h

   1 /*
   2  * Graph topology
   3  */
   4 /*
   5  * Vertices in strip are numbered as follows:
   6  *
   7  *     ___ X-2 ___ X-1 ___  0  ___  1  ___  2  ___  3  ___  4  __
   8  *         Y-1     Y-1     0       0       0       0       0
   9  *        /  \    /  \    /  \    /  \    /  \    /  \    /  \
  10  *       /    \  /    \  /    \  /    \  /    \  /    \  /    \
  11  *     X-3 ___ X-2 ___ X-1 ___  0  ___  1  ___  2  ___  3  ___  4
  12  *     Y-2     Y-2     Y-2     1       1       1       1       1
  13  *       \    /  \    /  \    /  \    /  \    /  \    /  \    /
  14  *        \  /    \  /    \  /    \  /    \  /    \  /    \  /
  15  *     ___ X-3 ___ X-2 ___ X-1 ___  0  ___  1  ___  2  ___  3  __
  16  *         Y-3     Y-3     Y-3     2       2       2       2
  17  *
  18  *       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
  19  *
  20  *      X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3
  21  *       1       1       1       1      Y-2     Y-2     Y-2     Y-2
  22  *        \    /  \    /  \    /  \    /  \    /  \    /  \    /
  23  *         \  /    \  /    \  /    \  /    \  /    \  /    \  /
  24  *      ___ X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   __
  25  *           0       0       0       0      Y-1     Y-1     Y-1
  26  *
  27  * Node x,y for
  28  *   0 <= x < X     x = distance along
  29  *   0 <= y < Y     y = distance across
  30  *
  31  * Vertices are in reading order from diagram above ie x varies fastest.
  32  *
  33  * Y must be even.  The actual location opposite (0,0) is (X-(Y-1)/2,0),
  34  * and likewise opposite (0,Y-1) is ((Y-1)/2,0).
  35  *
  36  * Note that though presentation above is equilateral triangles, this
  37  * is not the case.  It's actually a square lattice with half of the
  38  * diagonals added.  We can't straighten it out because at the join
  39  * the diagonals point the other way!
  40  *
  41  * We label edges as follows:        Or in the square view:
  42  *
  43  *                  \2   /1                 2  1
  44  *                   \  /                   | /
  45  *                ___ 0   __                |/
  46  *                3    1   0             3--*--0
  47  *                   /  \                  /|
  48  *                 4/   5\                / |
  49  *                                       4  5
  50  *
  51  *                                   (This makes the numbering
  52  *                                   discontinuity, at the join,
  53  *                                   vertical and thus tractable.)
  54  */
  55
  56 #ifndef MGRAPH_H
  57 #define MGRAPH_H
  58
  59 #include "common.h"
  60
  61 #define DIMBITS 5
  62
  63 #define XBITS DIMBITS
  64 #define X (1<<XBITS)
  65 #define YBITS DIMBITS
  66 #define Y (1<<YBITS)
  67
  68 /* vertex number:   0000 | y     | x
  69  *                        YBITS   XBITS
  70  */
  71
  72 #define N (X*Y)
  73 #define XMASK (X-1)
  74 #define YSHIFT XBITS
  75 #define Y1 (1 << YSHIFT)
  76 #define YMASK ((Y-1) << YSHIFT)
  77
  78 #define DIM (N*D3)
  79
  80 #define V6 6
  81
  82 #define FOR_VERTEX(v) \
  83   for ((v)=0; (v)<N; (v)++)
  84
  85 #define FOR_VPEDGE(v,e) \
  86   for ((e)=0; (e)<V6; (e)++)
  87
  88 extern int edge_end2(unsigned v1, int e);
  89 #define EDGE_END2 edge_end2
  90
  91 #define FOR_VEDGE_X(v1,e,v2,init,otherwise)     \
  92   FOR_VPEDGE((v1),(e))                          \
  93     if (((v2)= EDGE_END2((v1),(e)),             \
  94          (init),                                \
  95          (v2)) < 0) { otherwise; } else
  96
  97 #define NOTHING ((void)0)
  98
  99 #define FOR_VEDGE(v1,e,v2)                      \
 100   FOR_VEDGE_X(v1,e,v2,NOTHING,NOTHING)
 101
 102 #define FOR_EDGE(v1,e,v2)                       \
 103   FOR_VERTEX((v1))                              \
 104     FOR_VEDGE((v1),(e),(v2))
 105
 106 #define FOR_RIM_VERTEX(vy,vx,v)                                 \
 107   for ((vy)=0; (vy)<Y; (vy)+=Y-1)                               \
 108     for ((vx)=0; (v)= (vy)<<YSHIFT | (vx), (vx)<X; (vx)++)
 109
 110 typedef double Vertices[N][D3];
 111
 112 #endif /*MGRAPH_H*/