* e is 0..5. The edge is edge e out of vertex (x,y).
*
* BGL expects an undirected graph's edges to have two descriptors
- * each, one in each direction.
+ * each, one in each direction (otherwise e would be just 0..2).
*/
/*
using namespace boost;
-struct OutEdgeIterator :
+/*
+ * We use the following alternative numbering for iterating over edges:
+ *
+ * ix: \0 /1
+ * \ /
+ * ___ 0 __
+ * 2 1 3
+ * / \
+ * 4/ 5\
+ *
+ *
+ * This numbering permits the order-4 nodes at the strip's edge
+ * to have a contiguous edge iterator values 2..5 or 0..3.
+ */
+static const int oee_edgemap[V6]=
+ { 2<<ESHIFT, 1<<ESHIFT, 3<<ESHIFT, 2<<ESHIFT, 4<<ESHIFT, 5<<ESHIFT };
+
+class OutEdgeIterator :
public iterator_facade<
OutEdgeIterator,
int const,
forward_traversal_tag
> {
- int f;
- void increment() { f += 1<<ESHIFT; }
- bool equal(OutEdgeIterator const& other) const { return f == other.f; }
+ int v, ix, f;
+
+ void setf() { f= v | oee_edgemap[ix]; }
+ public:
+ void increment() { ix++; setf(); }
+ bool equal(OutEdgeIterator const& other) const { return ix == other.ix; }
int const& dereference() const { return f; }
OutEdgeIterator() { }
- OutEdgeIterator(int _f) : f(_f) { }
- OutEdgeIterator(int v, int e) : f(e << ESHIFT | v) { }
+ OutEdgeIterator(int _v, int _ix) : v(_v), ix(_ix) { setf(); }
+
+ static int voe_min(int _v) { return _v & YMASK ? 0 : 2; }
+ static int voe_max(int _v) { return ~_v & YMASK ? V6 : 4; }
};
typedef counting_iterator<int> VertexIterator;
inline int target(int f, const Graph&) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
inline std::pair<OutEdgeIterator,OutEdgeIterator>
out_edges(int v, const Graph&) {
- return std::make_pair(OutEdgeIterator(v, VE_MIN(v)),
- OutEdgeIterator(v, VE_MAX(v)));
+ return std::make_pair(OutEdgeIterator(v, OutEdgeIterator::voe_min(v)),
+ OutEdgeIterator(v, OutEdgeIterator::voe_max(v)));
}
inline unsigned out_degree(int v, const Graph&) {
- return VE_MAX(v) - VE_MIN(v);
+ return OutEdgeIterator::voe_max(v) - OutEdgeIterator::voe_min(v);
}
// Concept VertexListGraph:
#include "mgraph.h"
-static const unsigned dx[V6]= { 0, +1, -1, +1, -1, 0 },
- dy[V6]= { +Y1, +Y1, 0, 0, -Y1, -Y1 };
-
+static const unsigned dx[V6]= { +1, +1, 0, -1, -1, 0 },
+ dy[V6]= { 0, +Y1, +Y1, 0, -Y1, -Y1 };
int edge_end2(unsigned v1, int e) {
/* The topology is equivalent to that of a square lattice with only
* lattice to make the lines of constant x vertical. This gives
* these six directions:
*
- * 0 1
+ * 2 1
* | /
* |/
- * 2--*--3
+ * 3--*--0
* /|
* / |
* 4 5
*
* We label edges as follows:
*
- * \0 /1
+ * e: \2 /1
* \ /
* ___ 0 __
- * 2 1 3
+ * 3 1 0
* / \
* 4/ 5\
- *
- * (This numbering permits the order-4 nodes at the strip's edge
- * to have a contiguous edge numbering 2..5 or 0..3.)
- *
- * When we iterate over edges, we iterate first over vertices and then
- * over edges 0 to 2, disregarding edges 3 to 5.
*/
#ifndef MGRAPH_H
#define FOR_VERTEX(v) \
for ((v)=0; (v)<N; (v)++)
-#define VE_MIN(v) ((v) & YMASK ? 0 : 2)
-#define VE_MAX(v) (~(v) & YMASK ? V6 : 4)
-
#define FOR_VPEDGE(v,e) \
- for ((e)=VE_MIN(v); (e)<VE_MAX(v); (e)++)
+ for ((e)=0; (e)<V6; (e)++)
extern int edge_end2(unsigned v1, int e);
#define EDGE_END2 edge_end2