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  *                        ^ join, where there is
  37  *                           a discontinuity in numbering
  38  *
  39  * Node x,y for
  40  *   0 <= x < X = 2^XBITS     x = distance along
  41  *   0 <= y < Y = 2^YBITS-1     y = distance across
  42  *
  43  * Vertices are in reading order from diagram above ie x varies fastest.
  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:
  51  *
  52  *                  \2   /1
  53  *                   \  /
  54  *                ___ 0   __
  55  *                3    1   0
  56  *                   /  \
  57  *                 4/   5\
  58  */
  59
  60 #ifndef MGRAPH_H
  61 #define MGRAPH_H
  62
  63 #include "common.h"
  64
  65 #define DIMBITS 4
  66
  67 #define XBITS DIMBITS
  68 #define X (1<<XBITS)
  69 #define YBITS DIMBITS
  70 #define Y ((1<<YBITS) - 1)
  71
  72 /* vertex number:   0000 | y     | x
  73  *                        YBITS   XBITS
  74  */
  75
  76 #define N (X*Y)
  77 #define XMASK (X-1)
  78 #define YSHIFT XBITS
  79 #define Y1 (1 << YSHIFT)
  80 #define YMASK (Y << YSHIFT)
  81
  82 #define DIM (N*D3)
  83
  84 #define V6 6
  85
  86 #define FOR_VERTEX(v) \
  87   for ((v)=0; (v)<N; (v)++)
  88
  89 #define FOR_VPEDGE(v,e) \
  90   for ((e)=0; (e)<V6; (e)++)
  91
  92 extern int edge_end2(unsigned v1, int e);
  93 #define EDGE_END2 edge_end2
  94
  95 #define RIM_VERTEX_P(v) (((v) & YMASK) == 0 || ((v) & YMASK) == (Y-1)*Y1)
  96
  97 #define FOR_VEDGE_X(v1,e,v2,init,otherwise)     \
  98   FOR_VPEDGE((v1),(e))                          \
  99     if (((v2)= EDGE_END2((v1),(e)),             \
 100          (init),                                \
 101          (v2)) < 0) { otherwise; } else
 102
 103 #define NOTHING ((void)0)
 104
 105 #define FOR_VEDGE(v1,e,v2)                      \
 106   FOR_VEDGE_X(v1,e,v2,NOTHING,NOTHING)
 107
 108 #define FOR_EDGE(v1,e,v2)                       \
 109   FOR_VERTEX((v1))                              \
 110     FOR_VEDGE((v1),(e),(v2))
 111
 112 #define FOR_RIM_VERTEX(vy,vx,v)                                 \
 113   for ((vy)=0; (vy)<Y; (vy)+=Y-1)                               \
 114     for ((vx)=0; (v)= (vy)<<YSHIFT | (vx), (vx)<X; (vx)++)
 115
 116 typedef double Vertices[N][D3];
 117
 118 #endif /*MGRAPH_H*/