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)
24 // We make Layout a model of various BGL Graph concepts.
25 // This mainly means that graph_traits<Layout> has lots of stuff.
27 // First, some definitions used later:
29 struct layout_graph_traversal_category :
30 public virtual incidence_graph_tag,
31 public virtual vertex_list_graph_tag,
32 public virtual edge_list_graph_tag { };
34 struct OutEdgeIncrable {
36 OutEdgeIncrable operator++(OutEdgeIncrable i) {
40 OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
42 struct AnyEdgeIncrable {
44 AnyEdgeIncrable operator++(AnyEdgeIncrable f) {
47 if (!(f & YMASK) && (f & EMASK) < (2 << EMASK)) { f += Y1; }
50 return f + 1<<ESHIFT; }
52 struct graph_traits<Layout> {
56 typedef int vertex_descriptor; /* vertex number, -1 => none */
57 typedef int edge_descriptor; /* see above */
58 typedef undirected_tag directed_category;
59 typedef disallow_parallel_ege edge_parallel_category;
60 typedef layout_graph_traversal_category traversal_category;
61 inline int null_vertex() { return -1; }
63 // Concept IncidenceGraph:
65 typedef counting_iterator<OutEdgeIncrable,
66 forward_iterator_tag> out_edge_iterator;
67 typedef int degree_size_type;
69 inline int source(int f, const Layout& g) { return f&VMASK; }
70 inline int target(int f, const Layout& g) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
71 inline std::pair<out_edge_iterator,out_edge_iterator>
72 out_edges(int v, const Layout& g) {
73 return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
74 out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
76 out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
78 // Concept VertexListGraph:
79 typedef counting_iterator<int> vertex_iterator;
80 typedef unsigned vertices_size_type;
81 inline std::pair<vertex_iterator,vertex_iterator>
82 vertices(const Layout& g) {
83 return std::make_pair(vertex_iterator(0), vertex_iterator(N));
85 inline unsigned num_vertices(const Layout& g) { return N; }
87 // Concept EdgeListGraph:
88 typedef counting_iterator<int> edge_iterator;
93 void calculate_layout_energy(const Layout*) {
96 boost::dijkstra_shortest_paths(g, v1, 0);
99 /* vertex_index_map(vimap). */