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 /* 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.
  29  */
  30
  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)
  35
  36 namespace boost {
  37   // We make Layout a model of various BGL Graph concepts.
  38   // This mainly means that graph_traits<Layout> has lots of stuff.
  39
  40   // First, some definitions used later:
  41
  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 { };
  46
  47   struct OutEdgeIncrable {
  48     int f;
  49     OutEdgeIncrable& operator++() { f += 1<<ESHIFT; return self; }
  50     OutEdgeIncrable(int v, int e) : f(v | (e << ESHIFT)) { }
  51   };
  52   struct AnyEdgeIncrable {
  53     int f;
  54     AnyEdgeIncrable& operator++() {
  55       f++;
  56       if (f == F_ALL_SKIP_AT) f |= F_ALL_SKIP_SET
  57       return self;
  58     }
  59     AnyEdgeIncrable(int _f) : f(_f) { }
  60     AnyEdgeIncrable() : f(F_ALL_MIN) { }
  61   };
  62
  63   struct graph_traits<Layout> {
  64
  65     // Concept Graph:
  66
  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; }
  73
  74     // Concept IncidenceGraph:
  75
  76     typedef counting_iterator<OutEdgeIncrable,
  77       forward_iterator_tag> out_edge_iterator;
  78     typedef int degree_size_type;
  79
  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))));
  86     }
  87     out_degree(int v, const Layout&) { return VE_MAX(v) - VE_MIN(v); }
  88
  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));
  95     }
  96     inline unsigned num_vertices(const Layout&) { return N; }
  97
  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)));
 106     }
 107     unsigned num_edges(const Layout&) {
 108       return F_ALL_MAX - F_ALL_MIN - ((F_SKIP_SET|F_SKIP_AT) - F_SKIP_AT);
 109     }
 110
 111 }
 112
 113 void calculate_layout_energy(const Layout*) {
 114
 115   FOR_VERTEX(v1) {
 116     boost::dijkstra_shortest_paths(g, v1, 0);
 117
 118                             /* weight_map(). ? */
 119                             /* vertex_index_map(vimap). */
 120
 121
 122                             predecessor_map().
 123                             distance_map()
 124
 125
 126