6 * edge descriptor f = 00 | e | y | x
9 * e is 0..5. The edge is edge e out of vertex (x,y).
11 * BGL expects an undirected graph's edges to have two descriptors
12 * each, one in each direction.
16 * We use BGL's implementation of Johnson All Pairs Shortest Paths
19 #define VMASK (YMASK|XMASK)
20 #define ESHIFT (YBITS|XBITS)
22 /* When we enumerate the edges we mainly just increment f.
23 * To avoid nonexistent edges
24 * we start with e=0 | y=1 | x=0
25 * and explicitly skip e=1 | y=0 | ...
26 * We go only up to e=2 | YMAX | XMAX
27 * ie we stop just before e=3 | y=0 | x=0
28 * so that we get each edge once rather than twice.
31 #define F_ALL_MIN (1 << YSHIFT)
32 #define F_ALL_MAX (3 << ESHIFT)
33 #define F_ALL_SKIP_AT (1 << ESHIFT)
34 #define F_ALL_SKIP_SET (1 << YSHIFT)
37 // We make Layout a model of various BGL Graph concepts.
38 // This mainly means that graph_traits<Layout> has lots of stuff.
40 // First, some definitions used later:
42 struct layout_graph_traversal_category :
43 public virtual incidence_graph_tag,
44 public virtual vertex_list_graph_tag,
45 public virtual edge_list_graph_tag { };
47 struct OutEdgeIncrable {
49 OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
50 OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
52 struct AnyEdgeIncrable {
54 AnyEdgeIncrable& operator++() {
56 if (f == F_ALL_SKIP_AT) f |= F_ALL_SKIP_SET
59 AnyEdgeIncrable(int _f) : f(_f) { }
60 AnyEdgeIncrable() : f(F_ALL_MIN) { }
63 struct graph_traits<Layout> {
67 typedef int vertex_descriptor; /* vertex number, -1 => none */
68 typedef int edge_descriptor; /* see above */
69 typedef undirected_tag directed_category;
70 typedef disallow_parallel_ege edge_parallel_category;
71 typedef layout_graph_traversal_category traversal_category;
72 inline int null_vertex() { return -1; }
74 // Concept IncidenceGraph:
76 typedef counting_iterator<OutEdgeIncrable,
77 forward_iterator_tag> out_edge_iterator;
78 typedef int degree_size_type;
80 inline int source(int f, const Layout&) { return f&VMASK; }
81 inline int target(int f, const Layout&) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
82 inline std::pair<out_edge_iterator,out_edge_iterator>
83 out_edges(int v, const Layout&) {
84 return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
85 out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
87 out_degree(int v, const Layout&) { return VE_MAX(v) - VE_MIN(v); }
89 // Concept VertexListGraph:
90 typedef counting_iterator<int> vertex_iterator;
91 typedef unsigned vertices_size_type;
92 inline std::pair<vertex_iterator,vertex_iterator>
93 vertices(const Layout&) {
94 return std::make_pair(vertex_iterator(0), vertex_iterator(N));
96 inline unsigned num_vertices(const Layout&) { return N; }
98 // Concept EdgeListGraph:
99 typedef counting_iterator<AnyEdgeIncrable,
100 forward_iterator_tag> edge_iterator;
101 typedef unsigned edges_size_type;
102 inline std::pair<edge_iterator,edge_iterator>
103 edges(const Layout&) {
104 return std::make_pair(edge_iterator(AnyEdgeIncrable()),
105 edge_iterator(AnyEdgeIncrable(F_ALL_MAX)));
107 unsigned num_edges(const Layout&) {
108 return F_ALL_MAX - F_ALL_MIN - ((F_SKIP_SET|F_SKIP_AT) - F_SKIP_AT);
113 void calculate_layout_energy(const Layout*) {
116 boost::dijkstra_shortest_paths(g, v1, 0);
118 /* weight_map(). ? */
119 /* vertex_index_map(vimap). */