Boost 图类库快速入门

图数据结构和算法在某些方面比容器更加复杂。STL 使用的抽象迭代器接口不够丰富，无法包含图算法遍历图的多种方式。相反，我们制定了一个用于图的抽象接口，与迭代器用于基本容器的目的相同（尽管迭代器仍然扮演着重要角色）。图 1 描述了 STL 和 BGL 之间的相似之处。

图抽象由一组顶点（或节点）和一组连接顶点的边（或弧）组成。图 2 描述了一个有向图，它有 5 个顶点（标记为 0 到 4）和 11 条边。离开顶点的边称为顶点的出边。边 {(0,1)，(0,2)，(0,3)，(0,4)} 都是顶点 0 的出边。进入顶点的边称为顶点的入边。边 {(0,4)，(2,4)，(3,4)} 都是顶点 4 的入边。

在接下来的部分中，我们将使用 BGL 来构造这个示例图，并以各种方式操作它。这个示例的完整源代码可以在 examples/quick_tour.cpp 中找到。下面的每一节讨论这个示例文件的一个“片段”。还将列出示例程序输出的摘录。

构造一个图

在这个例子中，我们将使用 BGL adjacency_list 类来演示 BGL 接口的主要思想。adjacency_list 类提供了经典“邻接链表”数据结构的一般化版本。adjacency_list 是一个模板类，有六个模板参数，不过这里我们只填写前三个参数，其余三个使用默认值。前两个模板参数（vecS, vecS）决定了用于表示图中每个顶点的外边的数据结构，以及用于表示图的顶点集的数据结构（请参阅 选择Edgelist 和 VertexList部分，了解不同数据结构的权衡）。第三个参数 bidirectionalS 选择一个有向图，该有向图提供对出入边的访问。第三个参数的其他选项 directedS 选择一个只有出边的有向图，undirectedS 选择无向图。

一旦我们选择了图类型，我们就可以通过声明一个图对象并使用 MutableGraph 接口的 add_edge() 函数（由 adjacency_list 实现）填充边来创建如图 2 所示的图。我们使用 edge_array 对数组只是为了方便地显式创建本例中的边。

#include <iostream>  // for std::cout
#include <utility>   // for std::pair
#include <algorithm> // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;

int main(int, char*[])
{
    // 用 typedef 的方式创建一个 Graph 类型
    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

    // 为顶点制作方便的标签
    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    const char* name = "ABCDE";

    // 写入到图中的边
    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]);

    // 定义一个图对象
    Graph g(num_vertices);

    // 将边添加到图对象中
    for (int i = 0; i < num_edges; ++i)
        add_edge(edge_array[i].first, edge_array[i].second, g);
    // ...
    return 0;
}

我们可以使用图的边迭代器构造函数，而不是为每条边调用 add_edge() 函数。这通常比使用 add_edge() 更有效。指向 edge_array 的指针可以看作是迭代器，因此可以通过传递指向数组开头和结尾的指针来调用迭代器构造函数。

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

除了从一定数量的顶点开始创建图之外，还可以使用 add_vertex() 和 remove_vertex() 函数添加和删除顶点，这也是MutableGraph 接口。

访问顶点集

现在我们已经创建了一个图，我们可以使用图接口以不同的方式访问图数据。首先，我们可以使用 VertexListGraph 接口的 vertices() 函数访问图中的所有顶点。这个函数返回一对顶点迭代器（第一个迭代器指向顶点的“开始”，第二个迭代器指向“结束后”）。解引用顶点迭代器会得到顶点对象。顶点迭代器的类型由 graph_traits 类给出。注意，不同的图类可以有不同的关联顶点迭代器类型，这就是我们需要 graph_traits类的原因。给定某种图类型，graph_traits 类将提供对 vertex_iterator 类型的访问。

下面的示例打印出图中每个顶点的索引。所有顶点和边的属性，包括索引，都可以通过属性映射对象来访问。property_map 类用于获取特定属性（由 vertex_index_t 指定，这是 BGL 预定义的属性之一）的属性映射类型，函数调用 get(vertex_index, g) 返回实际的属性映射对象。

// ...
int main(int, char*[])
{
    // ...
    typedef graph_traits<Graph>::vertex_descriptor Vertex;
  
    // 获取顶点索引的属性映射表
    typedef property_map<Graph, vertex_index_t>::type IndexMap;
    IndexMap index = get(vertex_index, g);
    
    std::cout << "vertices(g) = ";
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    std::pair<vertex_iter, vertex_iter> vp;
    for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
        Vertex v = *vp.first;
        std::cout << index[v] <<  " ";
    }
    std::cout << std::endl;
    // ...
    return 0;
}

输出：

vertices(g) = 0 1 2 3 4

访问边集

可以使用 EdgeListGraph 接口的 edges() 函数访问图的边集。与 vertex() 函数类似，该函数返回一对迭代器，但在本例中，迭代器是边迭代器。对边迭代器解引用会得到一个边对象。source() 和 target() 函数返回由边连接的两个顶点。这次我们将使用 boost::tie() 辅助函数，而不是显式地为迭代器创建 std::pair。这个便捷函数可以用来将 std::pair 的部分赋值给两个独立的变量，在本例中是 ei 和 ei_end。这通常比创建 std::pair 更方便，也是我们为 BGL 选择的方法。

// ...
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)
        std::cout << "(" << index[source(*ei, g)]
                  << "," << index[target(*ei, g)] << ") ";
    std::cout << std::endl;
    // ...
    return 0;
}

输出：

edges(g) = (0,1) (0,3) (2,0) (3,2) (2,4) (1,3) (3,4)

临接结构

在接下来的几个例子中，我们将从特定顶点的角度探索图的邻接结构。我们将查看顶点的入边、出边及其相邻顶点。我们将其封装在 “exercise vertex” 函数中，并将其应用于图中的每个顶点。为了演示 BGL 的 STL 互操作性，我们将使用 STL for_each() 函数来迭代顶点并应用该函数。

//...
int main(int,char*[])
{
    //...
    std::for_each(vertices(g).first, vertices(g).second,
                  exercise_vertex<Graph>(g));
    return 0;
}

对于 exercise_vertex，我们使用了一个函子而不是一个函数，因为当我们访问每个顶点的信息时，需要用到图对象；使用函子可以在 std::for_each() 执行期间保留对图对象的引用。此外，我们还在图类型上模板了函数函数，以便它可以在不同的图类中重用。下面是exercise_vertex 函子的开头：

template <class Graph> 
struct exercise_vertex {
    exercise_vertex(Graph& g_) : g(g_) {}
    //...
    Graph& g;
};

顶点描述子

为了编写函子的 operator() 方法，我们首先需要知道图的顶点对象的类型。顶点的类型将作为 operator() 方法的参数。确切地说，我们不处理实际的顶点对象，而是处理顶点描述子。许多图表示（如邻接链表）不存储实际的顶点对象，而是其他（如指针链表图）。这种差异隐藏在顶点描述子对象的“黑盒”下面。顶点描述子是由每种图类型提供的，可用于通过 out_edges()，in_edges()， adjacent_vertices() 和属性映射函数访问有关图的信息，这些函数将在下面的部分中介绍。顶点描述子的类型是通过 graph_traits 类获得的。下例中使用的 typename 关键字是必要的，因为 :: 操作符左侧的类型（graph_traits<Graph> 类型）依赖于模板参数（Graph 类型）。下面演示我们如何定义函子的调用操作符：

template <class Graph>
struct exercise_vertex {
    //...
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

    void operator()(const Vertex& v) const
    {
        //...
    }
    //...
};

出边、入边以及边描述子

使用 IncidenceGraph 接口的 out_edges() 函数，可以访问顶点的所有出边。out_edges() 函数接受两个参数：第一个参数是顶点，第二个参数是图对象。该函数返回一对迭代器，用于访问一个顶点的所有出边（类似于 vertices() 函数返回的迭代器对儿）。这个迭代器被称为出边迭代器，对其解引用就能得到一个边描述子对象。边描述子扮演者与顶点描述子相同的角色，它是图类提供的一个“黑盒”。如下代码片段以来源-目标的形式打印出了顶点 v 的每一条出边：

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;
        //...
    }
    //...
};

针对顶点 0 产生的输出：

out-edges: (0,1) (0,2) (0,3) (0,4)

BidirectionalGraph 接口的 in_edges 函数通过入边迭代器为一个顶点的所有入边提供了访问。如果为Directed 模板参数提供了 bidirectionalS，则 in_edges() 函数仅对 adjacency_list 可用。当指定 bidirectionalS 而不是 directedS 时会有额外的开销。

template <class Graph>
struct exercise_vertex {
    //...
    void operator()(const Vertex& v) const
    {
        //...
        std::cout << "in-edges: ";
        typedef typename graph_traits<Graph> GraphTraits;
        typename GraphTraits::in_edge_iterator in_i, in_end;
        for (boost::tie(in_i, in_end) = in_edges(v,g);
             in_i != in_end; ++in_i) {
            e = *in_i;
            Vertex src = source(e, g), targ = target(e, g);
            std::cout << "(" << index[src] << "," << index[targ] << ") ";
        }
        std::cout << std::endl;
        //...
    }
    //...
};

针对顶点 0 产生的输出：

in-edges: (2,0) (3,0) (4,0)

相邻顶点

给定顶点的出边，这些出边的目标顶点与源顶点相邻。有时算法不需要看图的边，只关心顶点。因此，图接口还包括 AdjacencyGraph 接口的 adjacent_vertices() 函数，它提供对相邻顶点的直接访问。这个函数返回一对邻接迭代器。解引用一个邻接迭代器会得到一个相邻顶点的顶点描述子。

template <class Graph>
struct exercise_vertex {
    //...
    void operator()(Vertex v) const
    {
        //...
        std::cout << "adjacent vertices: ";
        typename graph_traits<Graph>::adjacency_iterator ai;
        typename graph_traits<Graph>::adjacency_iterator ai_end;
        for (boost::tie(ai, ai_end) = adjacent_vertices(v, g);
             ai != ai_end; ++ai)
            std::cout << index[*ai] <<  " ";
        std::cout << std::endl;
    }
    //...
};

针对顶点 4 产生的输出：

adjacent vertices: 0 1

为你的图添加颜色

BGL 试图在使属性附加到图的方面做到尽可能地灵活。例如，像边权重这样的属性可能需要在图对象的整个生命周期中使用，因此让图对象也管理的属性存储会很方便。另一方面，像顶点颜色这样的属性可能只需要在单个算法的持续时间内使用，因此并且最好将该属性与图对象分开存储。第一类属性称为内部存储属性，而第二类属性称为外部存储属性。BGL 使用一种统一的机制来访问图算法中的这两种属性，称为属性映射接口（在属性映射概念一节中描述）。此外，PropertyGraph 概念定义了用于获取内部存储属性的属性映射对象的接口。

BGL 的 adjacency_list 类允许用户通过图类的插件模板参数指定内部存储的属性。如何做到这一点将在内部属性部分详细讨论。外部存储的属性可以通过多种不同的方式创建，尽管它们最终作为单独的参数传递给图算法。存储属性的一种直接方法是创建一个按顶点或边索引来索引的数组。在为VertexList 模板参数指定 vecS 的 adjacency_list 中，顶点被自动分配索引，可以通过vertex_index_t 的属性映射访问。边不会自动分配索引。然而，属性机制可用于将索引附加到可用于索引到其他外部存储属性的边。

在下面的示例中，我们构造一个图并应用 dijkstra_shortest_paths()。该实例的完整源代码详见 examples/dijkstra-example.cpp。Dijkstra 算法用于计算从起始顶点到图中每个其他顶点的最短距离。

Dijkstra 算法要求每个边都有一个权重属性，每个顶点都有一个距离属性。这里我们用一个内部属性表示权重，用一个外部属性表示距离。对于权重属性，我们使用属性类并指定 int 作为表示权重值的类型，并指定edge_weight_t 作为属性标记（这是 BGL 预定义的属性标记之一）。然后将 weight 属性用作adjacency_list 的模板参数。

listS 和 vecS 类型是决定在邻接列表中使用的数据结构的选择器（参见选择 Edgelist 和 VertexList 部分）。directedS 类型指定图应该是有向的（而不是无向的）。下面的代码显示了图类型具现以及是图的初始化。边和权值以迭代器的形式传递给图的构造函数（指针符合RandomAccessIterator 的要求）。

typedef adjacency_list<listS, vecS, directedS, no_property,
                       property<edge_weight_t, int>> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef std::pair<int,int> E;
const int num_nodes = 5;
E edges[] = { E(0,2),
              E(1,1), E(1,3), E(1,4),
              E(2,1), E(2,3),
              E(3,4),
              E(4,0), E(4,1) };
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
Graph G(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);

我们使用一个 std::vector 来存储外部距离属性。BGL 算法将随机访问迭代器视为属性映射，因此我们可以将距离向量的起始迭代器传递给 Dijkstra 算法。继续上面的示例，下面的代码显示了距离向量的创建、对 Dijkstra 算法的调用（隐式地使用内部边权重属性），然后是结果的输出。

// 用 vector 存储距离属性
std::vector<int> d(num_vertices(G));
// 获取第一个顶点
Vertex s = *(vertices(G).first);
// 调用 Dijkstra 算法的变体 2
dijkstra_shortest_paths(G, s, distance_map(&d[0]));
std::cout << "distances from start vertex:" << std::endl;
graph_traits<Graph>::vertex_iterator vi;
for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
    std::cout << "distance(" << index(*vi) << ") = "
              << d[*vi] << std::endl;
std::cout << std::endl;

输出：

distances from start vertex:
distance(0) = 0
distance(1) = 6
distance(2) = 1
distance(3) = 4
distance(4) = 5

使用访问子拓展算法

通常情况下，库中的算法几乎可以满足您的需要，但并不完全满足。例如，在上一节中，我们使用 Dijkstra 算法来计算到每个顶点的最短距离，但也许我们还想记录最短路径树。一种方法是记录最短路径树中每个节点的前身（父节点）。

如果我们能避免重写 Dijkstra 算法就好了，只需要添加一些额外的东西来记录前导[1]。在 STL 中，这种可扩展性是由函子提供的，它是每个算法的可选参数。在 BGL 中，这个角色由访问子来完成。

访问子类似于函子，但它不是只有一个“调用”方法，而是有好几个。这些方法中的每一个都将在算法中特定定义的恰当调用点被调用。访问子的方法在访问子概念的部分中有详细解释。BGL 为一些常见任务提供了一些访问子，包括一个前导记录访问子。鼓励用户编写自己的访问子，作为扩展 BGL 的一种方式。在这里，我们将快速查看前导记录器的实现和使用。因为我们将使用 dijkstra_shortest_paths() 算法，所以我们创建的访问子必须是 Dijkstra Visitor。

record_predecessor 访问子的功能分为两部分。对于前导属性的存储和访问，我们将使用属性映射。前导访问子将只负责记录哪个父级。为了实现这一点，我们创建了一个 record_predecessor 类，并将其作为前导属性映射 PredecessorMap 的模板。由于此访问子将只填充访问子方法中的一个，因此我们将继承 dijkstra_visitor，后者将为其余的访问子提供空方法。predecessor_recorder 的构造函数将获取属性映射对象并将其保存在一个数据成员中。

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) {
        // 将 target(e) 父级设置为 source(e) 
        put(m_predecessor, target(e, g), source(e, g));
    }
protected:
    PredecessorMap m_predecessor;
};

记录前导的工作很简单。当 Dijkstra 算法放松一条边（可能将其添加到最短路径树中）时，我们将源顶点记录为目标顶点的前身。稍后，如果再次放松边，则前一个属性将被新的前导覆盖。这里，我们使用与属性映射相关联的put() 函数来记录前导。访问子的 edge_filter 告诉算法何时调用 explore() 方法。在这种情况下，我们只想得到关于最短路径树中的边的通知，所以我们指定了 tree_edge_tag。

最后，我们创建了一个辅助函数，以便更方便地创建前导访问子。所有 BGL 访问子都有这样的辅助函数。

template <class PredecessorMap>
record_predecessors<PredecessorMap>
make_predecessor_recorder(PredecessorMap p) {
    return record_predecessors<PredecessorMap>(p);
}

现在我们准备在 Dijkstra 算法中使用 record_predecessor。幸运的是，BGL 的 Dijkstra 算法已经具备了处理访问子的能力，所以我们只需传递新访问子即可。在本例中，我们只需要使用一个访问子，但是 BGL 也可以在同一算法中处理多个访问子的使用（参见访问子概念部分）。

using std::vector;
using std::cout;
using std::endl;

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])));

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;
}

输出：

parents in the tree of shortest paths:
parent(0) = no parent
parent(1) = 4
parent(2) = 0
parent(3) = 2
parent(4) = 3

注意

[1] Dijkstra 算法的新版本现在包含了一个用于记录前导的命名参数，因此不再需要前导访问子，尽管如此，这仍然是一个很好的示例。