remove dead wood; reenable graph_layout_cost

[moebius2.git] / mgraph.h

diff --git a/mgraph.h b/mgraph.h
index 08704894f7ab41841f11f44937a981f26c588a75..9cc20eb407e4d4779da311f0f3df661befbf8a6b 100644 (file)
--- a/mgraph.h
+++ b/mgraph.h
@@ -4,53 +4,57 @@
 /*
  * Vertices in strip are numbered as follows:
  *
- *     ___ X-2 ___ X-1 ___  0  ___  1  ___  2  ___  3  ___  4  __
- *         Y-1     Y-1     0       0       0       0       0 
+ *                       |
+ *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4  __
+ *         Y-1     Y-1    |0       0       0       0       0
  *        /  \    /  \    /  \    /  \    /  \    /  \    /  \
- *       /    \  /    \  /    \  /    \  /    \  /    \  /    \
- *     X-3 ___ X-2 ___ X-1 ___  0  ___  1  ___  2  ___  3  ___  4
- *     Y-2     Y-2     Y-2     1       1       1       1       1
- *       \    /  \    /  \    /  \    /  \    /  \    /  \    /
+ *       /    \  /    \  /|   \  /    \  /    \  /    \  /    \
+ *     X-3 ___ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  4
+ *     Y-2     Y-2     Y-2|    1       1       1       1       1
+ *       \    /  \    /  \|   /  \    /  \    /  \    /  \    /
  *        \  /    \  /    \  /    \  /    \  /    \  /    \  /
- *     ___ X-3 ___ X-2 ___ X-1 ___  0  ___  1  ___  2  ___  3  __
- *         Y-3     Y-3     Y-3     2       2       2       2 
- *
- *       .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
- *
- *      X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   ___ 3
- *       1       1       1       1      Y-2     Y-2     Y-2     Y-2
- *        \    /  \    /  \    /  \    /  \    /  \    /  \    /
- *         \  /    \  /    \  /    \  /    \  /    \  /    \  /
- *      ___ X-4 ___ X-3 ___ X-2 ___ X-1 ___ 0   ___ 1   ___ 2   __
- *           0       0       0       0      Y-1     Y-1     Y-1
+ *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  __   4 ___
+ *         Y-3     Y-3    |2       2       2       2      2
+ *        /  \    /  \    /  \    /  \    /  \    /  \    /  \
+ *       /    \  /    \  /|   \  /    \  /    \  /    \  /    \
+ *     X-3 ___ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  4
+ *     Y-4     Y-4     Y-4|    3       3       3       3       3
+ *                       |
+ *       .   .   .   .   .|  .   .   .   .   .   .   .   .   .   .
+ *                       |
+ *     ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4 ___
+ *         2       2      |Y-3     Y-3     Y-3     Y-3     Y-3
+ *        /  \    /  \    /  \    /  \    /  \    /  \    /  \
+ *       /    \  /    \  /|   \  /    \  /    \  /    \  /    \
+ *          __ X-2 ___ X-1|___  0  ___  1  ___  2  ___  3  ___  3  ___  4
+ *             1       1  |    Y-2     Y-2     Y-2     Y-2     Y-2     Y-2
+ *    /  \    /  \    /  \|   /  \    /  \    /         \    /  \    /
+ *   /    \  /    \  /    \  /    \  /    \  /   \  /    \  /
+ *  -3 ___ X-2 ___ X-1 ___| 0  ___  1  ___  2  ___  3  ___  4 ___
+ *  0      0       0      |Y-1     Y-1     Y-1     Y-1     Y-1
+ *                       |
+ *                        ^ join, where there is
+ *                           a discontinuity in numbering
  *
  * Node x,y for
- *   0 <= x < X     x = distance along
- *   0 <= y < Y     y = distance across
+ *   0 <= x < X = 2^XBITS     x = distance along
+ *   0 <= y < Y = 2^YBITS-1     y = distance across
  *
  * Vertices are in reading order from diagram above ie x varies fastest.
  *
- * Y must be even.  The actual location opposite (0,0) is (X-(Y-1)/2,0),
- * and likewise opposite (0,Y-1) is ((Y-1)/2,0).
- *
  * Note that though presentation above is equilateral triangles, this
  * is not the case.  It's actually a square lattice with half of the
  * diagonals added.  We can't straighten it out because at the join
  * the diagonals point the other way!
  *
- * We label edges as follows:        Or in the square view:
- *
- *                 \2   /1                 2  1  
- *                  \  /                   | /   
- *               ___ 0   __                |/    
- *               3    1   0             3--*--0  
- *                  /  \                  /|     
- *                4/   5\                / |     
- *                                      4  5
+ * We label edges as follows:
  *
- *                                   (This makes the numbering
- *                                   discontinuity, at the join,
- *                                   vertical and thus tractable.)
+ *                 \2   /1
+ *                  \  /
+ *               ___ 0   __
+ *               3    1   0
+ *                  /  \
+ *                4/   5\
  */
 
 #ifndef MGRAPH_H
@@ -58,12 +62,10 @@
 
 #include "common.h"
 
-#define DIMBITS 5
-
-#define XBITS DIMBITS
+#define XBITS 4/*3*/
 #define X (1<<XBITS)
-#define YBITS DIMBITS
-#define Y (1<<YBITS)
+#define YBITS 3/*3*/
+#define Y ((1<<YBITS) - 1)
 
 /* vertex number:   0000 | y     | x
  *                        YBITS   XBITS
@@ -73,7 +75,7 @@
 #define XMASK (X-1)
 #define YSHIFT XBITS
 #define Y1 (1 << YSHIFT)
-#define YMASK ((Y-1) << YSHIFT)
+#define YMASK (Y << YSHIFT)
 
 #define DIM (N*D3)
 
@@ -88,6 +90,8 @@
 extern int edge_end2(unsigned v1, int e);
 #define EDGE_END2 edge_end2
 
+#define RIM_VERTEX_P(v) (((v) & YMASK) == 0 || ((v) & YMASK) == (Y-1)*Y1)
+
 #define FOR_VEDGE_X(v1,e,v2,init,otherwise)    \
   FOR_VPEDGE((v1),(e))                         \
     if (((v2)= EDGE_END2((v1),(e)),            \