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  * We label edges as follows:
  37  *
  38  *                          \0   /1
  39  *                           \  /
  40  *                        ___ 0   __
  41  *                        2    1   3
  42  *                           /  \
  43  *                         4/   5\
  44  *
  45  * (This numbering permits the order-4 nodes at the strip's edge
  46  *  to have a contiguous edge numbering 2..5 or 0..3.)
  47  *
  48  * When we iterate over edges, we iterate first over vertices and then
  49  * over edges 0 to 2, disregarding edges 3 to 5.
  50  */
  51
  52 #ifndef MGRAPH_H
  53 #define MGRAPH_H
  54
  55 #define XBITS 4
  56 #define X (1<<XBITS)
  57 #define YBITS 4
  58 #define Y (1<<YBITS)
  59
  60 /* vertex number:   0000 | y     | x
  61  *                        YBITS   XBITS
  62  */
  63
  64 #define N (X*Y)
  65 #define XMASK (X-1)
  66 #define YSHIFT XBITS
  67 #define Y1 (1 << YSHIFT)
  68 #define YMASK (Y-1 << YSHIFT)
  69
  70 #define V6 6
  71
  72 #define FOR_VERTEX(v) \
  73   for ((v)=0; (v)<N; (v)++)
  74
  75 #define VE_MIN(v) ((v) & YMASK ? 0 : 2)
  76 #define VE_MAX(v) (~(v) & YMASK ? V6 : 4)
  77
  78 #define FOR_VPEDGE(v,e) \
  79   for ((e)=VE_MIN(v); (e)<VE_MAX(v); (e)++)
  80
  81 extern int edge_end2(unsigned v1, int e);
  82 #define EDGE_END2 edge_end2
  83
  84 #define FOR_VEDGE_X(v1,e,v2,init,otherwise)     \
  85   FOR_VPEDGE((v1),(e))                          \
  86     if (((v2)= EDGE_END2((v1),(e)),             \
  87          (init),                                \
  88          (v2)) < 0) { otherwise } else
  89
  90 #define NOTHING ((void)0)
  91
  92 #define FOR_VEDGE(v1,e,v2)                      \
  93   FOR_VEDGE_X(v1,e,v2,NOTHING,NOTHING)
  94
  95 #define FOR_EDGE(v1,e,v2)                       \
  96   FOR_VERTEX((v1))                              \
  97     FOR_VEDGE((v1),(e),(v2))
  98
  99 #define FOR_COORD(k) \
 100   for ((k)=0; (k)<D3; (k)++)
 101
 102 #define K FOR_COORD(k)
 103
 104 #define FOR_RIM_VERTEX(vy,vx,v)                                 \
 105   for ((vy)=0; (vy)<Y; (vy)+=Y-1)                               \
 106     for ((vx)=0; (v)= (vy)<<YSHIFT | (vx), (vx)<X; (vx)++)
 107
 108 typedef double Vertices[N][D3];
 109
 110 #endif /*MGRAPH_H*/