#define VMASK (YMASK|XMASK)
#define ESHIFT (YBITS|XBITS)
+/* When we enumerate the edges we mainly just increment f.
+ * To avoid nonexistent edges
+ * we start with e=0 | y=1 | x=0
+ * and explicitly skip e=1 | y=0 | ...
+ * We go only up to e=2 | YMAX | XMAX
+ * ie we stop just before e=3 | y=0 | x=0
+ * so that we get each edge once rather than twice.
+ */
+
+#define F_ALL_MIN (1 << YSHIFT)
+#define F_ALL_MAX (3 << ESHIFT)
+#define F_ALL_SKIP_AT (1 << ESHIFT)
+#define F_ALL_SKIP_SET (1 << YSHIFT)
namespace boost {
// We make Layout a model of various BGL Graph concepts.
struct OutEdgeIncrable {
int f;
- OutEdgeIncrable operator++(OutEdgeIncrable i) {
- f += 1<<ESHIFT;
- return self;
- }
+ OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
- }
+ };
struct AnyEdgeIncrable {
int f;
- AnyEdgeIncrable operator++(AnyEdgeIncrable f) {
+ AnyEdgeIncrable& operator++() {
f++;
- if (!(f & XMASK)) {
- if (!(f & YMASK) && (f & EMASK) < (2 << EMASK)) { f += Y1; }
-
-
- return f + 1<<ESHIFT; }
+ if (f == F_ALL_SKIP_AT) f |= F_ALL_SKIP_SET
+ return self;
+ }
+ AnyEdgeIncrable(int _f) : f(_f) { }
+ AnyEdgeIncrable() : f(F_ALL_MIN) { }
+ };
struct graph_traits<Layout> {
forward_iterator_tag> out_edge_iterator;
typedef int degree_size_type;
- inline int source(int f, const Layout& g) { return f&VMASK; }
- inline int target(int f, const Layout& g) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
+ inline int source(int f, const Layout&) { return f&VMASK; }
+ inline int target(int f, const Layout&) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
inline std::pair<out_edge_iterator,out_edge_iterator>
- out_edges(int v, const Layout& g) {
+ out_edges(int v, const Layout&) {
return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
}
- out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
+ out_degree(int v, const Layout&) { return VE_MAX(v) - VE_MIN(v); }
// Concept VertexListGraph:
typedef counting_iterator<int> vertex_iterator;
typedef unsigned vertices_size_type;
inline std::pair<vertex_iterator,vertex_iterator>
- vertices(const Layout& g) {
+ vertices(const Layout&) {
return std::make_pair(vertex_iterator(0), vertex_iterator(N));
}
- inline unsigned num_vertices(const Layout& g) { return N; }
+ inline unsigned num_vertices(const Layout&) { return N; }
// Concept EdgeListGraph:
- typedef counting_iterator<int> edge_iterator;
- inline std::pair
+ typedef counting_iterator<AnyEdgeIncrable,
+ forward_iterator_tag> edge_iterator;
+ typedef unsigned edges_size_type;
+ inline std::pair<edge_iterator,edge_iterator>
+ edges(const Layout&) {
+ return std::make_pair(edge_iterator(AnyEdgeIncrable()),
+ edge_iterator(AnyEdgeIncrable(F_ALL_MAX)));
+ }
+ unsigned num_edges(const Layout&) {
+ return F_ALL_MAX - F_ALL_MIN - ((F_SKIP_SET|F_SKIP_AT) - F_SKIP_AT);
+ }
}