1. Introduction

1.2 Graph Concepts

BGL定义了一组概念来描述如何对图进行查询和修改。

1.2.1 Vertex and Edge Descriptors

在BGL中，图的节点和边分别通过节点描述符（vertex descriptors）和边描述符（edge descriptors）进行表达和操作。

不同的图可能采用不同的描述符。

一个图类型（graph type）的描述符类型可以通过 graph_traits 类进行访问。

缺省情况下，节点描述符具有一些基本的功能，包括：构造、复制、比较。缺省情况下，边描述符除了这几种基本功能之外，还能访问当前边的源节点和目标节点。

下面的函数模版实现了如下功能：判断一个边的两端是否是相同的节点。

template <typename Graph>
bool is_self_loop(typename graph_traits<Graph>::edge_descriptor e, const Graph & g)
{
    typename graph_traits<Graph>::vertex_descriptor u, v;
    u = source(e, g);
    v = target(e, g);
    return (u == v);
}

1.2.2 Property Maps

图作为特定问题的模型的一个重要原因在于可以为图中的节点和边关联特定的信息。在BGL中，我们将节点和边关联的信息称为属性（property），并使用属性映射（property map）这一概念实现对属性的存取。

一个属性映射是一个对象，其将一组键对象（key objects）映射到一组值对象（value objects）。属性映射概念定义了3个函数：

  1. get(p_map, key): 返回key对应的值对象
  2. put(p_map, key, value): 将value设为key对应的值对象
  3. p_map[key]: 返回key对应的值对象的引用

下面的模版函数实现了如下功能：给定一个名字属性映射（name property map），打印出一个节点的名字。

template <typename VertexDescriptor, typename VertexNameMap>
void print_vertex_name(VertexDescriptor v, VertexNameMap name_map)
{
    std::cout << get(name_map, v); 
}

类似的，图1.1中边上的传输延迟值可以用如下函数打印出来：

template <typename Graph, typename TransDelayMap, typename VertexNameMap>
void print_trans_delay(typename graph_traits<Graph>::edge_descriptor e, const Graph & g, TransDelayMap delay_map, VertexNameMap name_map)
{
    std::cout << "trans_delay(" << get(name_map, source(e, g)) << "," << get(name_map, target(e, g)) << ")= " << get(delay_map, e);
}

1.2.3 Graph Traversal

图中存在几种不同类型的collections：节点，边，每一个节点的出边、入边、邻接节点。与STL类似，BGL使用遍历器（iterator）来实现对这些collections的访问。具体而言，BGL定义了5种类型的图遍历器：

  1. 节点遍历器（vertex iterator）：用于遍历一个图中的所有节点。节点遍历器的值类型是节点描述符（vertex descriptor）

  2. 边遍历器（edge iterator）：用于遍历一个图中的所有边。边遍历器的值类型是边描述符（edge descriptor）

  3. 出边遍历器（out-edge iterator）：用于遍历图中给定节点u的所有出边。其值类型是边描述符。

  4. 入边遍历器（in-edge iterator）：用于遍历图中给定节点v的所有入边。其值类型是边描述符。

  5. 邻接点遍历器（adjacency iterator）：用于遍历图中给定节点的所有邻接节点。其值类型是节点描述符。

类似于描述符，一个图类型具有自己的遍历器类型，且这些遍历器类型可以通过graph_traits类进行访问。

对上述任何一种遍历器，BGL定义了一个函数，其返回std::pair，其中包含了一对遍历器对象：第一个对象指向序列中的第一个元素；第二个对象指向序列中的最后一个元素。例如，下面的函数实现了“打印一个图中所有节点的名称”这一功能：

template <typename Graph, typename VertexNameMap>
void print_vertex_names(const Graph & g, VertexNameMap name_map)
{
    std::cout << "vertices(g) = { ";
    typedef typename graph_traits<Graph>::vertex_iterator iter_t;
    for (std::pair<iter_t, iter_t> p = vertices(g); p.first != p.second; ++p.first)
    {
        print_vertex_name(*p.first, name_map); std::cout << " ";
    }
    std::cout << "} " << std::endl;
}

下面的代码则实现了“打印图1.1中边上的传输延迟值”的功能. 其中使用了tie()函数（来自于boost/tuple/tuple.hpp），将std::pair中的两个元素直接赋值给两个变量first和last.

template <typename Graph, typename TransDelayMap, typename VertexNameMap>
void print_trans_delays(const Graph & g, TransDelayMap trans_delay_map, VertexNameMap name_map)
{
    typename graph_traits<Graph>::edge_iterator first, last;
    for (tie(first, last) = edges(g); first != last; ++first)
    {
        print_trans_delay(*first, g, trans_delay_map, name_map);
        std::cout << std::endl;
    }
}

除了vertices()和edges()，还有另外三个函数：out_edges()，in_edges()，adjacent_vertices()。这三个函数接收两个参数：一个节点描述符（vertex descriptor），一个图对象（graph object），然后返回一对遍历器。

大多数图算法不会同时用到这五种遍历，且一些图类型对特定的遍历类型无法提供有效的算法。因此，在将一个图对象传入某个图算法时，要确保这个图支持图算法所依赖的遍历类型。

一个图类型所支持的操作、以及一个图算法所依赖的操作，在相应的文档中可以查询到。

1.2.4 Graph Construction and Modification

BGL还定义从图中删除节点/边以及向图中增加节点/边的接口。本节，我们通过程序展示如何构造图1.1中的图：首先，使用add_vertex()函数向图中增加节点；然后，使用add_edge函数向图中增加边。

template <typename Graph, typename VertexNameMap, typename TransDelayMap>
void build_router_network(Graph & g, VertexNameMap name_map, TransDelayMap delay_map)
{
    <Add routers to the network 9a>
    <Add connections to the network 9b>
}

add_vertex()函数返回一个节点描述符。我们使用这个节点描述符在名字属性映射对象中为节点赋予一个名字。

<<Add routers to the network 9a>> =
typename graph_traits<Graph>::vertex_descriptor a, b, c, d, e;
a = add_vertex(g); name_map[a] = 'a';
b = add_vertex(g); name_map[b] = 'b';
c = add_vertex(g); name_map[c] = 'c';
d = add_vertex(g); name_map[d] = 'd';
e = add_vertex(g); name_map[e] = 'e';

add_edge()函数返回一个std::pair，其中：第一个元素是一个边描述符；第二个参数是一个Boolean标记，表示是否加入了一个新边（一些图类型在已经存在具有相同源节点和目标节点的边的情况下，将不会加入新的边）。

<Add connections to the network 9b>
typename graph_traits<Graph>::edge_descriptor ed;
bool inserted;
tie(ed, inserted) = add_edge(a,b,g); delay_map[ed] = 1.2;
tie(ed, inserted) = add_edge(a,d,g); delay_map[ed] = 4.5;
tie(ed, inserted) = add_edge(b,d,g); delay_map[ed] = 1.8;
tie(ed, inserted) = add_edge(c,a,g); delay_map[ed] = 2.6;
tie(ed, inserted) = add_edge(c,e,g); delay_map[ed] = 5.2;
tie(ed, inserted) = add_edge(d,c,g); delay_map[ed] = 0.4;
tie(ed, inserted) = add_edge(d,e,g); delay_map[ed] = 3.3;

BGL也提供了批量添加/删除节点/边的功能。

1.2.5 Algorithm Visitors

STL中的很多算法具有一个函数对象参数，以实现对算法行为的定制。例如，std::sort()函数包含了一个比较器参数compare。

template <typename RandomAccessIterator, typename BinaryPredicate>
void sort(RandomAccessIterator first, RandomAccessIterator last, BinaryPredicate compare)

compare参数是一个函数对象（也被称为functor）。下面展示它的用法。

假设一个程序要维护一个地址簿。通过联系人的姓对一组地址进行排序可以通过std::sort加上一个合适的函数对象来实现。这个函数对象的一个实例如下：

struct compare_last_name
{
    bool operator()(const address_info & x, const address_info & y) const
    {
        return x.last_name < y.last_name;
    }
}

然后，可以通过下面的代码实现对地址信息的排序：

std::vector<address_info> addresses;
compare_last_name compare;
std::sort(addresses.begin(), address.end(), compare);

BGL使用了类似机制实现对图算法行为的定制。其中，传入算法的函数对象称为算法访问器（algorithm visitor）。BGL vistor定义了多个函数，每个函数在算法中特定的事件点（event point）被调用。

在下面的例子中，我们对图1.1中的节点采用宽度优先的方式进行遍历并打印。实现方式即是使用一个访问器来调用breadth_first_search()函数。访问器在“发现节点”事件上打印出节点的名称（宽度优先搜索算法）。

访问器类的定义是按照BFSVistor概念进行的。

template <typename VertexNameMap>
class bfs_name_printer : public default_bfs_vistor
{
   public:
      bfs_name_printer(VertexNameMap n_map) : m_name_map(n_map){}   
      template <typename Vertex, typename Graph>
      void discover_vertex(Vertex u, const Graph &) const 
      {
          std::cout << get(m_name_map, u) << ' ';
      }

   private:
      VertexNameMap m_name_map;
};

然后，我们创建了一个bfs_name_printer类型的访问器，然后将它传入breadth_first_search()。vistor()函数对象是通过带名参数技术（named-parameter technique）来使用的（见2.7节）。

bfs_name_printer<VertexNameMap> vis(name_map);
std::cout << "BFS vertex discover order: ";
breadth_first_search(g,a, vistor(vis));
std::cout << std::endl;

这段程序的输出是：

BFS vertex discover order: a b d c e

1.3 Graph Classes and Adaptors

BGL提供的图类型可以分为两类。第一类是图类（graph class）主要用于在内存中存放图。第二类是图适配器（graph adaptor）：它创建了图的一个可修改的视图（modified view of a graph），或者基于若干其他类型创建了一个BGL图接口。

1.3.1 Graph Classes

BGL包含了两个主要的图类型：adjacency_list和adjacency_matrix。

adjacency_list对传统基于邻接表的图存储方式进行了扩展。一个图被存储为一组节点；每一个节点，还存储了该节点的所有出边。具体的实现会因情况而稍有不同。adjaceny_list类具有几个模版参数：EdgeList, VertexList, Directed, VertexProperties, EdgeProperties, GraphProperties。

  • EdgeList和VertexList定义了用于存储边列表和节点列表的类。这些参数的不同设定提供了在遍历速度、插入/删除速度、内存消耗等几个方面的折中。另外，EdgeList还决定了是否可以在图中插入重边。

  • Directed规定了图是有向的（directed）、无向的（undirected）、或是双向的（bidirectional）。一般情况下，一个有向图只提供了对一个节点出边的访问功能，而一个双向图还另外提供了对节点入边的访问功能。

  • VertexProperties, EdgeProperties, GraphProperties规定了附着在边、点、图上的属性类型。

adjacency_list的完整文档参见14.1.1节。

adjacency_matrix更加适用于存储稠密图。在一个adjacency_matrix图中，对任意边的访问在常量时间完成，非常高效。adjacency_matrix可以用来表示有向图和无向图，也提供了在点/边上附着属性的机制。adjacency_matrix的完整文档参见14.1.2节。

需要指出的是，本书的所有例子中图的规模都非常小（主要为方便展示）。但BGL的图具有很好的健壮性和空间效率，可以用来表达包含数百万个节点的图。

1.3.2 Graph Adaptors

BGL提供了数量众多的图适配器。第一种类型的图适配器可以对任何的BGL图进行适配，从而提供新的行为。

  • reverse_graph：将一个有向图适配为对应的反向图。

  • filtered_graph：通过适配，形成原来图的一个子图。通过两个谓词函数对象控制哪些点和边会被保留在视图中。

BGL也为不是BGL图类的其他图数据结构提供了支持。

  • edge_list：基于一组边适配形成一个BGL图。

  • Stanford GraphBase 通过头文件boost/graph/stanford_graph.hpp中的重载函数（overloaded functions）得到了支持。这样，GraphBase中的Graph*就满足了BGL的图接口。

  • 头文件boost/graph/leda_graph.hpp中的重载函数实现了对LEDA中图类型GRAPH<vtype, etype>的支持。

  • 头文件boost/graph/vector_as_graph.hpp中的重载函数可以将组合类型std::vector<std::list<int>>适配为一个BGL图。

BGL接口的完整描述见第12章。

1.4 Generic Graph Algorithms

BGL中的图算法是泛型算法（generic algorithm）。本节，我们首先展示如何将topological_sort()函数应用在两种不同类型的图上；然后，我们展示了如何使用泛型函数depth_first_search()来实现topological_sort()函数。

1.4.1 The Topological Sort Generic Algorithm

BGL的topological_sort()函数实现对一个有向图的节点进行拓扑排序的功能。这个函数模版具有两个参数：被排序的图，输出遍历器。这个算法将节点按照反向拓扑顺序写入输出遍历器中。

拓扑排序的一个用途是任务规划。图1.3中的图展示了一组任务节点及其之间的依赖关系。下面我们展示如何利用BGL拓扑排序算法求解这个问题。

Using Topological Sort with a Vector of Lists

首先我们将拓扑排序算法应用于一个基于std::vector<std::list<int>>形成的图上。下面是这个程序的框架。

<"topo-sort1.cpp" 15a> =
    #include <deque>
    #include <vector>
    #include <list>
    #include <iostream>
    #include <boost/graph/vector_as_graph.hpp>
    #include <boost/graph/topological_sort.hpp>

    int main()
    {
        using namespace boost;
        <Create labels for each of the tasks 15b>
        <Create the graph 15c>
        <Perform the topological sort and output the results 16>
        return EXIT_SUCCESS;
    }

图中的7个节点用0,1,2,3,4,5,6这七个整数进行表示。这些节点的标签被存放在一个数组中。

<Create labels for each of the tasks 15b> = 
    const char* tasks[] = 
    {
        "pick up kids from school",
        "buy groceries (and snacks)",
        "get cash at ATM",
        "drop off kids at soccer practice",
        "cook dinner",
        "pick up kids from soccer",
        "eat dinner"
    };

    const int n_tasks = sizeof(tasks)/sizeof(char*);

这个图被存储为由一组list构成的vector。图中的每一个节点在vector中占据一个位置。在vector任一位置上的list存储了当前位置节点的所有邻接节点。基于boost/graph/vector_as_graph.hpp中定义的函数，这个由一组list构成的vector符合BGL中VertexListGraph这一概念，因此可以被用于topological_sort()函数中。

<Create the Graph 15c> = 
    std::vector<std::list<int>> g(n_tasks);
    g[0].push_back(3);
    g[1].push_back(3);
    g[1].push_back(4);
    g[2].push_back(1);
    g[3].push_back(5);
    g[4].push_back(6);
    g[5].push_back(6);

在调用topological_sort()函数前，我们需要创建合适的数据结构来存放输出结果。BGL的拓扑排序算法会输出反向的拓扑顺序（实现上的高效性）。因此，我们需要在真正输出时恢复正向的拓扑顺序。下面的例子中使用std:deque（双向队列）作为存储输出的数据结构。另外，...。

由于这个例子中节点已经被表示为整数，我们只需要将identity_property_map作为节点索引映射（vertex index map）。vertex_index_map()函数用于传入一个带名字的参数（见2.7节）。

<Perform the topological sort and output the results 16>
    std::deque<int> topo_order;

    topological_sort(g, std::front_inserter(topo_order), vertex_index_map(identity_property_map()));

    int n = 1;
    for (std::deque<int>::iterator i = topo_order.begin(); 
         i != topo_order.end(); ++i, ==n)
    {
        std::cout << task[*i] << std::endl;
    }

程序的输出给出了顺序执行这些任务的一个顺序。

Using Topological Sort with the adjacency_list class

<Create an adjacency list object 17a> = 
    adjacency_list<listS, vecS, directedS> g(n_tasks);

<Add edges to the adjacency list 17b> =
    add_edge(0, 3, g);
    add_edge(1, 3, g);
    add_edge(1, 4, g);
    add_edge(2, 1, g);
    add_edge(3, 5, g);
    add_edge(4, 6, g);
    add_edge(5, 6, g);

<"topo-sort2.cpp" 18> =
    #include <vector>
    #include <deque>
    #include <boost/graph/topological_sort.hpp>
    #include <boost/graph/adjacency_list.hpp>
    int main()
    {
         using namespace boost;
        <Create labels for each of the tasks 15b>
        <Create an adjacency list object 17a>
        <Add edges to the adjacency list 17b>
        <Perform the topological sort and output the results 16>

        return EXIT_SUCCESS;
    }

1.4.2 The Depth-First Search Generic Algorithm

BGL中topological_sort()函数的实现只有几行，因为它调用了depth_first_search()函数。

template <typename OutputIterator>
class topo_sort_visitor : public default_dfs_visitor
{
   public:
      topo_sort_visitor(OutputIterator iter) : m_iter(iter){}
      template <typename Vertex, typename Graph>
      void finish_vertex(Vertex u, const Graph &) {*m_iter++ = u;}
  private:
     OutputIterator m_iter;    
}

template <typename Graph, typename OutputIterator>
void topological_sort(Graph & g, OutputIterator result_iter)
{
    topo_sort_visitor<OutputIterator> vis(result_iter);
    depth_first_search(g, visitor(vis))
}

2. Generic Programming in C++

z x y

results matching ""

    No results matching ""