mgraph.h

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