BGL（boost graph Library）(0-7)

2017-05-16  本文已影响0人  vaisy

BGL官网入口
Boost库说明

BGL的用途是给某些图的结构提供接口，而隐藏其内部细节
不需要built，但是编译程序一定要--optimized
三种方式得到STL：

算法

核心算法模式和一系列图算法：
核心算法模式：

数据结构

提供两种图类型一种边列表适配器
邻接表；邻接矩阵；边列表；
其中最通用的是邻接表；高度参数化，可以针对不同情况优化

int main(int,char*[])
  {
    // create a typedef for the Graph type
    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;//使用vector来存出边和顶点集的数据结构，双向

    // Make convenient labels for the vertices
    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    const char* name = "ABCDE";

    // writing out the edges in the graph
    typedef std::pair<int, int> Edge;
    Edge edge_array[] = 
    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E) };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

    // declare a graph object
    Graph g(num_vertices);

    // add the edges to the graph object
    for (int i = 0; i < num_edges; ++i)
      add_edge(edge_array[i].first, edge_array[i].second, g);
    ...
    return 0;
  }

除了使用add_edge()接口，也可以使用迭代器：

Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);`

此外，点数也是不固定的，可以使用 add_vertex() & remove_vertex()
边集访问：edges()返回的迭代器，source()和target()为被该边连接的点

  int main(int,char*[])
  {
    // ...
    std::cout << "edges(g) = ";
    graph_traits<Graph>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
//tie接口将返回的pair分离为两个变量。在本例中为ei和ei_end;
        std::cout << "(" << index[source(*ei, g)] 
                  << "," << index[target(*ei, g)] << ") ";
    std::cout << std::endl;
    // ...
    return 0;
  }

邻接结构：
std::for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g));
使用 exercise_vertex是为了在运行遍历时保留对图像的引用。将其模板化以便在不同的图类型中重用

顶点描述符是由每个图形类型提供的，可用于通过以下部分中描述的out_edges（），in_edges（），adjacent_vertices（）和属性映射函数来访问有关图形的信息。 vertex_descriptor类型通过graph_traits类获得。下面使用的typename关键字是必需的，因为scope :: operator（graph_traits <Graph>类型）左侧的类型取决于模板参数（Graph类型）。这是我们如何定义函子的应用方法：

  template <class Graph> struct exercise_vertex {
    //...
    typedef typename graph_traits<Graph>
      ::vertex_descriptor Vertex;
    void operator()(const Vertex& v) const
    {
      //...
    }
    //...
  };

边描述：out_edges()函数，两个参数：定点和图对象。返回pair迭代器，提供该顶点所有出边的接口，出边迭代器dereference其中之一给出边描述符对象。（类似顶点描述符）

  template <class Graph> struct exercise_vertex {
    //...
    void operator()(const Vertex& v) const
    {
      typedef graph_traits<Graph> GraphTraits;
      typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);

      std::cout << "out-edges: ";
      typename GraphTraits::out_edge_iterator out_i, out_end;
      typename GraphTraits::edge_descriptor e;
      for (boost::tie(out_i, out_end) = out_edges(v, g); 
           out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout << "(" << index[src] << "," 
                  << index[targ] << ") ";
      }
      std::cout << std::endl;
      //...
    }
    //...
  };

in_edges()与之类似，（前提是双向图，且仅用于邻接表结构）
有时，算法不需要查看图形的边，只关心顶点。 因此，图形界面还包括AdjacencyGraph接口的adjacent_vertices（）函数，它提供对相邻顶点的直接访问。 此函数返回一对邻接迭代器。 dereference邻接迭代器给出相邻顶点的顶点描述符。
涂色：加权。由于一般一个算法只用到一个属性,因此属性和图对象应当分别存储.属性有两类:内部存储属性/外部存储属性.内部属性通常采用模板插件,外部属性方法较多.直接存储的方法:点或者边映射的映射.对于vecS(即vector,参见某章),这种映射型容器会自己分配索引,用vertex_index_t来查找,而边不可以(废话太多了不就加个索引么)
用访问者扩展算法
一般来讲lib中的算法足够使用,但很有可能不完全相同.比如Dij算法通常记录最短距离,但是有可能我们需要用到最短路径树.一种方法是在最短路径树中记录每个节点的前导.
在STL中,这种计算通过functor实现.这是每个算法的可选参数.在BGL中这个由游客来实现.一个游客就是一个functor,它有多种方法被调用
(会在vistor章节详细介绍.)每一个方法都可以在算法的某一个点被调用.BGL提供了一些常用任务的访问者.可以自己创建BGL到visitor,本处先介绍前缀记录的实现和使用.以Dijkstra为例,创建一个Dijkstra visitor
前缀记录访问者的功能分为两部分.为了存储可访问前缀属性,我们使用属性映射.而后,前缀访问者只对要记录的父负责.创建了一个record_predecessor属性类及模板在前缀属性映射上,由于这个访问者只有一种方法,我们继承dijkstra_visitor,为其余提供空白方法.构造函数将使用属性映射对象并将其保存在数据成员中.
回顾:m_开头说明是类成员变量,构造函数的意图是把p存进m_这个protected里去.
然后又是一个模板函数

  template <class PredecessorMap>
  class record_predecessors : public dijkstra_visitor<>
  {
  public:
    record_predecessors(PredecessorMap p)
      : m_predecessor(p) { }

    template <class Edge, class Graph>
    void edge_relaxed(Edge e, Graph& g) {
      // set the parent of the target(e) to source(e)
      put(m_predecessor, target(e, g), source(e, g));
    }
  protected:
    PredecessorMap m_predecessor;
  };

将source记录为目标顶点的前身,每次relax时覆盖之前的值,使用put来记录前缀.访客的edge_filter通知算法什么时候启用explore(),该情况下我们只在最短路径树中通知边所以制定tree_edge_tag.
为了方便的创建前缀访问,启用helper如下

//类模板外函数？总之定义了make_,返回了record_的结果
  template <class PredecessorMap>
  record_predecessors<PredecessorMap>
  make_predecessor_recorder(PredecessorMap p) {
    return record_predecessors<PredecessorMap>(p);
  }

现在可以像下文一样使用:

vector<Vertex> p(num_vertices(G), graph_traits<G>::null_vertex());
 //容器(大小,迭代器)
  dijkstra_shortest_paths(G, s, distance_map(&d[0]). 
                          visitor(make_predecessor_recorder(&p[0])));
//计算最短路径,添加visitor并存储 参数是数组的位置
  cout << "parents in the tree of shortest paths:" << endl;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
    cout << "parent(" << *vi;
    if (p[*vi] == graph_traits<G>::null_vertex())
      cout << ") = no parent" << endl; 
    else 
      cout << ") = " << p[*vi] << endl;
  }

邻接矩阵：一般用于密集图表
边列表：可以使用任意边迭代和实现

上一篇下一篇

猜你喜欢

热点阅读