mgraph.h

   1 /*
   2  * Vertices in strip are numbered as follows:
   3  *
   4  *     ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3   ___ 4   __
   5  *         Y-1     Y-1      0       0       0       0       0
   6  *        /  \    /  \    /  \    /  \    /  \    /  \    /  \
   7  *       /    \  /    \  /    \  /    \  /    \  /    \  /    \
   8  *     X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___  3  ___ 4
   9  *     Y-2     Y-2     Y-2      1       1       1       1       1
  10  *       \    /  \    /  \    /  \    /  \    /  \    /  \    /
  11  *        \  /    \  /    \  /    \  /    \  /    \  /    \  /
  12  *     ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3   __
  13  *         Y-3     Y-3     Y-3      2       2       2       2
  14  *
  15  *       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
  16  *
  17  *      X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3
  18  *       1       1       1       1      Y-2     Y-2     Y-2     Y-2
  19  *        \    /  \    /  \    /  \    /  \    /  \    /  \    /
  20  *         \  /    \  /    \  /    \  /    \  /    \  /    \  /
  21  *      ___ X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   __
  22  *           0       0       0       0      Y-1     Y-1     Y-1
  23  *
  24  * Node x,y for
  25  *   0 <= x < X     x = distance along
  26  *   0 <= y < Y     y = distance across
  27  *
  28  * Vertices are in reading order from diagram above ie x varies fastest.
  29  *
  30  * Y must be even.  The actual location opposite (0,0) is (X-(Y-1)/2,0),
  31  * and likewise opposite (0,Y-1) is ((Y-1)/2,0).
  32  *
  33  * We label edges as follows:
  34  *
  35  *                          \0   /1
  36  *                           \  /
  37  *                        ___ 0   __
  38  *                        2    1   3
  39  *                           /  \
  40  *                         4/   5\
  41  *
  42  * (This numbering permits the order-4 nodes at the strip's edge
  43  *  to have a contiguous edge numbering 2..5 or 0..3.)
  44  *
  45  * When we iterate over edges, we iterate first over vertices and then
  46  * over edges 0 to 2, disregarding edges 3 to 5.
  47  */
  48
  49 #ifndef MGRAPH_H
  50 #define MGRAPH_H
  51
  52 #define XBITS 4
  53 #define X (1<<XBITS)
  54 #define YBITS 4
  55 #define Y (1<<YBITS)
  56
  57 /* vertex number:   0000 | y     | x
  58  *                        YBITS   XBITS
  59  */
  60
  61 #define N (X*Y)
  62 #define XMASK (X-1)
  63 #define YSHIFT XBITS
  64 #define Y1 (1 << YSHIFT)
  65 #define YMASK (Y-1 << YSHIFT)
  66
  67 #define V6 6
  68
  69 #define D3 3
  70
  71 #define FOR_VERTEX(v) \
  72   for ((v)=0; (v)<N; (v)++)
  73
  74 #define VE_MIN(v) ((v) & YMASK ? 0 : 2)
  75 #define VE_MAX(v) (~(v) & YMASK ? V6 : 4)
  76
  77 #define FOR_VPEDGE(v,e) \
  78   for ((e)=VE_MIN(v); (e)<VE_MAX(v); (e)++)
  79
  80 extern int edge_end2(unsigned v1, int e);
  81 #define EDGE_END2 edge_end2
  82
  83 #define FOR_VEDGE(v1,e) \
  84   FOR_VPEDGE((v1),(e))
  85     if (((v2)= EDGE_END2((v1),(e))) < 0) ; else
  86
  87 #define FOR_EDGE(v1,e,v2) \
  88   FOR_VERTEX((v1)) \
  89     FOR_VEDGE((v1),(e),(v2))
  90
  91 #define FOR_COORD(k) \
  92   for ((k)=0; (k)<D3; (k)++)
  93
  94 #define K FOR_COORD(k)
  95
  96 typedef struct {
  97   double v[N][D3];
  98 } Layout;
  99
 100 #endif /*MGRAPH_H*/