mgraph.h

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