bgl.cpp

   1 extern "C" {
   2 #include "mgraph.h"
   3 }
   4
   5 /*
   6  * edge descriptor f =   00 | e | y     | x
   7  *                            2  YBITS   XBITS
   8  *
   9  * e is 0,1 or 2.  The edge is edge e out of vertex (x,y).
  10  */
  11
  12 /*
  13  * We use BGL's implementation of Johnson All Pairs Shortest Paths
  14  */
  15
  16 #define VMASK (YMASK|XMASK)
  17 #define ESHIFT (YBITS|XBITS)
  18
  19 namespace boost {
  20   struct layout_graph_traversal_category :
  21     public virtual incidence_graph_tag,
  22     public virtual edge_list_graph_tag
  23     public virtual vertex_list_graph_tag { };
  24
  25   struct graph_traits<Layout> {
  26     /* Concept Graph: */
  27     typedef int vertex_descriptor; /* vertex number, -1 => none */
  28     typedef int edge_descriptor; /* see above */
  29     typedef undirected_tag directed_category;
  30     typedef disallow_parallel_ege edge_parallel_category;
  31     typedef layout_graph_traversal_category traversal_category;
  32     inline int null_vertex() { return -1; }
  33   }
  34   struct out_edge_iterator_policies {
  35     static void increment(int& f) { f += 1<<ESHIFT; }
  36     static void decrement(int& f) { f -= 1<<ESHIFT; }
  37
  38     template <class Reference>
  39     static Reference dereference(type<Reference>, const int& f)
  40     { return const_cast<Reference>(f); }
  41
  42     static bool equal(int x, int y) { return x == y; }
  43   }
  44   struct graph_traits<Layout> {
  45     /* Concept IncidenceGraph: */
  46     typedef iterator_adaptor<int, out_edge_iterator_policies,
  47       iterator<std::bidirectional_iterator_tag,int>
  48     > out_edge_iterator;
  49
  50     inline int source(int f, const Layout& g) { return f&VMASK; }
  51     inline int target(int f, const Layout& g) { return EDGE_END2(f&VMASK, f>>ESHIFT); }
  52     inline std::pair<typename graph_traits<Layout>::out_edge_iterator,
  53                      typename graph_traits<Layout>::out_edge_iterator>
  54     out_edges(int v, const Layout& g) {
  55       return std::make_pair(VE_MIN(v), VE_MAX(v));
  56     }
  57
  58     out_edge_iterator> {
  59
  60
  61     /* Concept VertexListGraph: */
  62     typedef counting_iterator<int> vertex_iterator;
  63
  64 }
  65
  66 void calculate_layout_energy(const Layout*) {
  67
  68   FOR_VERTEX(v1) {
  69     boost::dijkstra_shortest_paths(g, v1, 0);
  70
  71                             /* weight_map(). ? */
  72                             /* vertex_index_map(vimap). */
  73
  74
  75                             predecessor_map().
  76                             distance_map()
  77
  78
  79