bgl.cpp

   1 extern "C" {
   2 #include "mgraph.h"
   3 }
   4
   5 /*
   6  * edge descriptor f =   00 | e | y     | x
   7  *                            3  YBITS   XBITS
   8  *
   9  * e is 0..5.  The edge is edge e out of vertex (x,y).
  10  *
  11  * BGL expects an undirected graph's edges to have two descriptors
  12  * each, one in each direction.
  13  */
  14
  15 /*
  16  * We use BGL's implementation of Johnson All Pairs Shortest Paths
  17  */
  18
  19 #define VMASK (YMASK|XMASK)
  20 #define ESHIFT (YBITS|XBITS)
  21
  22
  23 namespace boost {
  24   // We make Layout a model of various BGL Graph concepts.
  25   // This mainly means that graph_traits<Layout> has lots of stuff.
  26
  27   // First, some definitions used later:
  28
  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 { };
  33
  34   struct OutEdgeIncrable {
  35     int f;
  36     OutEdgeIncrable operator++(OutEdgeIncrable i) {
  37       f += 1<<ESHIFT;
  38       return self;
  39     }
  40     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
  41   }
  42   struct AnyEdgeIncrable {
  43     int f;
  44     AnyEdgeIncrable operator++(AnyEdgeIncrable f) {
  45       f++;
  46       if (!(f & XMASK)) {
  47         if (!(f & YMASK) && (f & EMASK) < (2 << EMASK)) { f += Y1; }
  48
  49
  50       return f + 1<<ESHIFT; }
  51
  52   struct graph_traits<Layout> {
  53
  54     // Concept Graph:
  55
  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; }
  62
  63     // Concept IncidenceGraph:
  64
  65     typedef counting_iterator<OutEdgeIncrable,
  66       forward_iterator_tag> out_edge_iterator;
  67     typedef int degree_size_type;
  68
  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))));
  75     }
  76     out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
  77
  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));
  84     }
  85     inline unsigned num_vertices(const Layout& g) { return N; }
  86
  87     // Concept EdgeListGraph:
  88     typedef counting_iterator<int> edge_iterator;
  89     inline std::pair
  90
  91 }
  92
  93 void calculate_layout_energy(const Layout*) {
  94
  95   FOR_VERTEX(v1) {
  96     boost::dijkstra_shortest_paths(g, v1, 0);
  97
  98                             /* weight_map(). ? */
  99                             /* vertex_index_map(vimap). */
 100
 101
 102                             predecessor_map().
 103                             distance_map()
 104
 105
 106