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 #define FMAX ((5 << ESHIFT) | VMASK)
  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 edge_list_graph_tag
  32     public virtual vertex_list_graph_tag { };
  33
  34   struct OutEdgeIncrable {
  35     int f;
  36     OutEdgeIncrable operator++(OutEdgeIncrable f) { return f + 1<<ESHIFT; }
  37     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
  38   }
  39
  40   struct graph_traits<Layout> {
  41
  42     // Concept Graph:
  43
  44     typedef int vertex_descriptor; /* vertex number, -1 => none */
  45     typedef int edge_descriptor; /* see above */
  46     typedef undirected_tag directed_category;
  47     typedef disallow_parallel_ege edge_parallel_category;
  48     typedef layout_graph_traversal_category traversal_category;
  49     inline int null_vertex() { return -1; }
  50
  51     // Concept IncidenceGraph:
  52
  53     typedef counting_iterator<OutEdgeIncrable,
  54       forward_iterator_tag> out_edge_iterator;
  55     typedef int degree_size_type;
  56
  57     inline int source(int f, const Layout& g) { return f&VMASK; }
  58     inline int target(int f, const Layout& g) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
  59     inline std::pair<typename graph_traits<Layout>::out_edge_iterator,
  60                      typename graph_traits<Layout>::out_edge_iterator>
  61     out_edges(int v, const Layout& g) {
  62       return std::make_pair(out_edge_iterator(OutEdgeIncrable(v, VE_MIN(v))),
  63                             out_edge_iterator(OutEdgeIncrable(v, VE_MAX(v))));
  64     }
  65     out_degree(int v, const Layout& g) { return VE_MAX(v) - VE_MIN(v); }
  66
  67     // Concept VertexListGraph:
  68     typedef counting_iterator<int> vertex_iterator;
  69
  70 }
  71
  72 void calculate_layout_energy(const Layout*) {
  73
  74   FOR_VERTEX(v1) {
  75     boost::dijkstra_shortest_paths(g, v1, 0);
  76
  77                             /* weight_map(). ? */
  78                             /* vertex_index_map(vimap). */
  79
  80
  81                             predecessor_map().
  82                             distance_map()
  83
  84
  85