/*
* edge descriptor f = 00 | e | y | x
- * 2 YBITS XBITS
+ * 3 YBITS XBITS
*
- * e is 0,1 or 2. The edge is edge e out of vertex (x,y).
+ * 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.
*/
/*
#define VMASK (YMASK|XMASK)
#define ESHIFT (YBITS|XBITS)
+#define FMAX ((5 << ESHIFT) | VMASK)
namespace boost {
+ // We make Layout a model of various BGL Graph concepts.
+ // This mainly means that graph_traits<Layout> has lots of stuff.
+
+ // First, some definitions used later:
+
struct layout_graph_traversal_category :
public virtual incidence_graph_tag,
public virtual edge_list_graph_tag
public virtual vertex_list_graph_tag { };
+ struct OutEdgeIncrable {
+ int f;
+ OutEdgeIncrable operator++(OutEdgeIncrable f) { return f + 1<<ESHIFT; }
+ OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
+ }
+
struct graph_traits<Layout> {
- /* Concept Graph: */
+
+ // Concept Graph:
+
typedef int vertex_descriptor; /* vertex number, -1 => none */
typedef int edge_descriptor; /* see above */
typedef undirected_tag directed_category;
typedef disallow_parallel_ege edge_parallel_category;
typedef layout_graph_traversal_category traversal_category;
inline int null_vertex() { return -1; }
- }
- struct out_edge_iterator_policies {
- static void increment(int& f) { f += 1<<ESHIFT; }
- static void decrement(int& f) { f -= 1<<ESHIFT; }
-
- template <class Reference>
- static Reference dereference(type<Reference>, const int& f)
- { return const_cast<Reference>(f); }
- static bool equal(int x, int y) { return x == y; }
- }
- struct graph_traits<Layout> {
- /* Concept IncidenceGraph: */
- typedef iterator_adaptor<int, out_edge_iterator_policies,
- iterator<std::bidirectional_iterator_tag,int>
- > out_edge_iterator;
+ // Concept IncidenceGraph:
+
+ typedef counting_iterator<OutEdgeIncrable,
+ 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 std::pair<typename graph_traits<Layout>::out_edge_iterator,
typename graph_traits<Layout>::out_edge_iterator>
out_edges(int v, const Layout& g) {
- return std::make_pair(VE_MIN(v), VE_MAX(v));
+ return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
+ out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
}
-
- out_edge_iterator> {
-
+ out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
- /* Concept VertexListGraph: */
+ // Concept VertexListGraph:
typedef counting_iterator<int> vertex_iterator;
}