发表关于计算的公理陈述通常是一个热门辩论的问题。 但是，图论是现代计算最重要的理论Struts之一，并不是其中一种说法。 从设计路由器和网络到设计构成移动设备核心的芯片的无数工程领域不过是图论的应用。
作为C++应用程序软件开发人员，我们经常直接需要将实际的工程问题转换为等效的图论问题。 拥有一个强大的基于C++的通用图形库可以帮助我们做到这一点显然是值得欢迎的：Boost Graph Library（BGL）填补了这个精确的空白。
在本文中，您将创建一个无向图，然后创建一个有向图，然后再执行通常的遍历例程。 然后，您可以应用一些经典算法-所有这些都无需添加大量代码。 这就是BGL的魔力。
下载并安装
BGL可从Boost站点免费下载（请参阅参考资料中的链接）。 BGL是仅标头的库，因此，在应用程序代码中对该库的后续使用要求在源代码中包括相关标头。 但是，BGL确实需要序列化库进行链接。 这是一个典型的命令行：
root# g++ test_bgl.cpp I/usr/boost/boost_1_44/ -L/usr/boost/boost_1_44/lib
出于本文的目的，您需要Boost 1.44版本。
邻接表
任何图实现的核心都是邻接表或矩阵。 清单1显示了如何在Boost标头adjacency_list.hpp中声明邻接列表。
清单1.在Boost中声明一个邻接表
template <class OutEdgeListS = vecS,
// a Sequence or an AssociativeContainer class VertexListS = vecS,
// a Sequence or a RandomAccessContainer class DirectedS = directedS,
class VertexProperty = no_property,
class EdgeProperty = no_property,
class GraphProperty = no_property,
class EdgeListS = listS>
class adjacency_list { };
为简单起见，让我们集中讨论前三个模板参数。
OutEdgeList模板参数决定将使用哪种容器来存储边缘列表信息。 从图论基础上回想一下，对于有向图，所有仅具有输入边的顶点都有一个空的对应邻接表。 默认值设置为vecS ，它对应于std::vector 。 VertexList模板参数决定用于表示图形顶点列表的容器类型，默认容器为std::vector 。 DirectedS模板参数根据所提供的值是directedS还是undirectedS确定这是有向图还是无向图。
在BGL中创建图形
通过在列表中声明邻接表， 清单2中的代码在BGL中创建了一个简单的无向图。 边缘信息将存储在std::list ，顶点存储在std::vector 。
清单2.创建一个无向图
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef boost::adjacency_list<listS, vecS, undirectedS> mygraph;
int main()
{
mygraph g;
add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);
}
在清单2中，图g的创建没有在构造函数中提供任何顶点或边的细节。 边和顶点将在运行时使用add_edge和add_vertex等辅助函数add_vertex 。 add_edge函数的名称含义是：在图形的两个顶点之间添加一条边。 在清单2的执行结束时， g应该有四个标记为0、1、2和3的顶点，其中1连接到0和2，依此类推。
遍历图
遍历图涉及使用vertex_iterator和adjacency_iterator类。 前者遍历图的所有顶点；前者遍历图的所有顶点。 后者在相应的相邻顶点上迭代。 清单3显示了代码。
清单3.使用BGL遍历图
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef boost::adjacency_list<listS, vecS, undirectedS> mygraph;
int main()
{
mygraph g;
add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);
mygraph::vertex_iterator vertexIt, vertexEnd;
mygraph::adjacency_iterator neighbourIt, neighbourEnd;
tie(vertexIt, vertexEnd) = vertices(g);
for (; vertexIt != vertexEnd; ++vertexIt)
{
cout << *vertexIt << " is connected with ";
tie(neighbourIt, neighbourEnd) = adjacent_vertices(*vertexIt, g);
for (; neighbourIt != neighbourEnd; ++neighbourIt)
cout << *neighbourIt << " ";
cout << "\n";
}
}
创建有向图
要创建一个有向图，只需将清单3中的图类型修改为directedS ：
#include <boost/graph/adjacency_list.hpp> using namespace boost; typedef boost::adjacency_list<listS, vecS, directedS> mygraph; int main() { mygraph g; add_edge (0, 1, g); add_edge (0, 3, g); add_edge (1, 2, g); add_edge (2, 3, g); // Same as Listing 3 }
辅助函数顶点返回std::pair<vertex_iterator和vertex_iterator> ，前者指向图形中的第一个顶点。 将结果捕获到元组关系（ vertexIt, vertexEnd ）中，随后将使用vertexIt遍历图形。 同样，帮助器函数adjacent_vertices返回std::pair<adjacency_iterator, adjacency_iterator> ，其中第一个adjacency_iterator指向邻接表中的第一个元素。
关于BGL的很酷的事情之一是它是高度可配置的。 BGL允许您使用以下任何一种选择器类型（这些都在标头中定义；您需要做的就是在声明图形时使用它们）来配置顶点集和边的集合：
vecS选择std::vector lists为std::list slistS选择std::slist setS选择std::set multiSetS选择std::multiset hash_setS选择std::hash_set
如果您的代码将插入许多顶点但没有多少删除，则VertexList可以是vecS或listS 。 push_back通常是恒定时间，除非需要重新分配向量的时间。 如果您将有许多插入和删除操作，那么listS比vecS更好，因为从向量上删除元素通常会更昂贵，而且很方便。
创建无向图的另一种方法
可以使用BGL提供的undirected_graph类（在undirected_graph.hpp中定义）来代替使用基于邻接表的版本创建无向图。 但是，此类在内部使用邻接表，并且使用基于邻接表的图总是可以提供更大的灵活性。 清单4显示了代码。
清单4.使用undirected_graph.hpp创建一个无向图
#include <undirected_graph.hpp> #include <iostream> using namespace boost;
using namespace std;
int main( )
{
undirected_graph<>g;
undirected_graph<>:vertex_descriptor u = g.add_vertex();
undirected_graph<>:vertex_descriptor v = g.add_vertex();
undirected_graph<>:vertex_descriptor w = g.add_vertex();
undirected_graph<>:vertex_descriptor x = g.add_vertex();
add_edge(u, v, g); add_edge(u, w, g); add_edge(u, x, g);
cout << "Degree of u: " << degree(u, g);
return 0;
}
在清单4中，我使用add_vertex将单个顶点添加到图中，并使用add_edge边缘添加到图中。 最后，使用degree方法调用显示单个顶点的degree 。 清单5提供了undirected_graph的声明和定义（来自Boost来源）。
清单5.解密BGL undirected_graph
template < typename VertexProp = no_property,
typename EdgeProp = no_property,
typename GraphProp = no_property> class undirected_graph
{ // public:
typedef adjacency_list<listS,
listS, undirectedS,
vertex_property,
edge_property,
GraphProp,
listS> graph_type;
private: graph_type m_graph; //
};
跟踪顶点的边缘和边缘
您可以使用out_edges辅助函数访问顶点的输出边缘； 要访问传入的边缘，请使用in_edges 。 关于BGL的一个很棒的事情是，您可以使用cout直接输出一条边，它显示了连接的顶点。 清单6显示了代码。
清单6.遍历有向图的边缘
#include <boost/graph/adjacency_list.hpp> using namespace boost;
typedef boost::adjacency_list<listS, vecS, directedS> mygraph;
int main()
{
mygraph g;
add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);
mygraph::vertex_iterator vertexIt, vertexEnd;
mygraph::in_edge_iterator inedgeIt, inedgeEnd;
mygraph::in_edge_iterator outedgeIt, outedgeEnd; tie(vertexIt, vertexEnd) = vertices(g);
for (; vertexIt != vertexEnd; ++vertexIt)
{
cout << "incoming edges for " << *vertexIt << ": ";
tie(inedgeIt, inedgeEnd) = in_edges(*vertexIt, g);
for(; inedgeIt != inedgeEnd; ++inedgeIt)
{
cout << *inedgeIt << " ";
}
cout << "\n";
}
for (; vertexIt != vertexEnd; ++vertexIt)
{
std::cout << "out-edges for " << *vertexIt << : ;
tie(outedgeIt, outedgeEnd) = out_edges(*vertexIt, g); // Similar to incoming edges
}
}
如果编译清单6中的代码，则会得到错误。 要修复这些错误，只需更换directedS与bidirectionalS在声明mygraph 。 在BGL中使用directedS标签时，只允许使用out_edges帮助函数和关联的迭代器。 使用in_edges需要改变图形类型到bidirectionalS ，尽管这仍然或多或少有向图。
注意：使用in_edges会带来额外的空间成本（如果将其与directedS进行比较，则每边缘成本是其两倍），因此请确保它是您可以接受的东西。
一些有用的BGL功能
现在，让我们来回顾一下BGL提供的，尚未讨论的一些更重要的效用函数。
您可以使用以下功能进行图形访问：
std::pair<edge_iterator, edge_iterator> edges(const adjacency_list& g) 。 返回与图g中的边相对应的迭代器对 vertices_size_type num_vertices(const adjacency_list& g) 。 返回以g为单位的顶点数 edges_size_type num_edges(const adjacency_list& g) 。 返回以g为单位的边数 vertex_descriptor source(edge_descriptor e, const adjacency_list& g) 。 返回边的源顶点 vertex_descriptor target(edge_descriptor e, const adjacency_list& g) 。 返回边的目标顶点 degree_size_type in_degree(vertex_descriptor u, const adjacency_list& g) 。 返回顶点的度数 degree_size_type out_degree(vertex_descriptor u, const adjacency_list& g) 。 返回顶点的出度
清单7显示了执行大量图形访问的代码。
清单7.使用BGL进行图访问
// usual typedefs here, refer to previous listings
int main()
{
mygraph g;
add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
cout << "Number of edges: " << num_edges(g) << "\n";
cout << "Number of vertices: " << num_vertices(g) << "\n";
mygraph::vertex_iterator vertexIt, vertexEnd; tie(vertexIt, vertexEnd) = vertices(g);
for (; vertexIt != vertexEnd; ++vertexIt)
{
std::cout << "in-degree for " << *vertexIt << ": "
<< in_degree(*vertexIt, g) << "\n";
std::cout << "out-degree for " << *vertexIt << ": "
<< out_degree(*vertexIt, g) << "\n";
}
mygraph::edge_iterator edgeIt,
edgeEnd; tie(edgeIt, edgeEnd) = edges(g);
for (; edgeIt!= edgeEnd; ++edgeIt)
{ std::cout << "edge " << source(*edgeIt, g) << "-->"
<< target(*edgeIt, g) << "\n";
}
}
您可以使用以下功能进行图形修改：
void remove_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g) 。 从g移除边缘 void remove_edge(edge_descriptor e, adjacency_list& g) 。 从g移除边缘 void clear_vertex(vertex_descriptor u, adjacency_list& g) 。 删除所有边缘和从u void clear_out_edges(vertex_descriptor u, adjacency_list& g) 。 从有向图g中的顶点u移除所有出线边（不适用于无向图） void clear_in_edges(vertex_descriptor u, adjacency_list& g) 。 从有向图g中的顶点u删除所有传入边（不适用于无向图） void remove_vertex(vertex_descriptor u, adjacency_list& g) 。 从图形g中删除一个顶点（预计已经使用clear_vertex或其他适当的函数删除了与该顶点关联的所有边。）
使用BGL创建有向加权图
既然您对有向图感到满意，接下来的逻辑任务是使用BGL创建加权有向图。 如果回头看一下清单1中邻接表的声明，您会发现模板参数之一称为EdgeProperty 。 使用此模板参数来构造图形。
属性是可以同时分配给顶点和边的参数。 您可以使用标签名称和与该属性相对应的类型来定义属性。 BGL有几个可用的标签名称，包括edge_weight_t和vertex_name_t 。 例如，要在图形顶点中存储名称，可以将属性定义为typedef property<vertex_name_t, std::string> VertexNameProperty ，然后将此属性传递给图形的模板声明中的VertexProperty参数。
这是边缘权重属性的声明：
typedef property<edge_weight_t, int> EdgeWeightProperty;
现在你已经创建EdgeWeightProperty ，调整你的定义mygraph ：
typedef boost::adjacency_list<listS,
vecS, directedS,
no_property,
EdgeWeightProperty> mygraph;
最后，在图形中添加边缘时，请使用add_edge的重载版本，该版本接受权重作为第三个参数。 清单8提供了完整的代码。
清单8.创建加权有向图
#include <boost/graph/adjacency_list.hpp> using namespace boost;
typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<listS, vecS, directedS, no_property,
EdgeWeightProperty > mygraph;
int main()
{
mygraph g;
add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
}
BGL中的最小生成树
关于BGL的最好的事情之一是，它带有大量可在图形上运行的预定义算法。 克鲁斯卡尔（Kruskal），普里姆（Prim），迪杰斯特拉（Dijkstra）–您将其命名，BGL拥有它。 要了解我的意思，请修改清单8中的代码，使之具有带加权边的无向图，然后在其上使用Kruskal算法获取最小生成树。 BGL在单独的标题中提供了单独的算法，因此要使用Kruskal，必须包含boost / graph / kruskal_min_spanning_tree.hpp。 清单9显示了代码。
清单9.使用Kruskal算法的最小生成树
#include <boost/graph/adjacency_list.hpp> // typedef boost::adjacency_list<listS,
vecS, directedS, no_property, EdgeWeightProperty > mygraph;
typedef mygraph::edge_descriptor Edge;
int main()
{
mygraph g;
add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
std::list < Edge > spanning_tree;
kruskal_minimum_spanning_tree (g, std::back_inserter(spanning_tree));
for (std::list < Edge >::iterator ei = spanning_tree.begin(); ei != spanning_tree.end();
++ei)
{
cout << *ei << " ";
}
cout << "\n";
}
函数kruskal_minimum_spanning_tree在幕后发挥了魔力。 它将图形和一个迭代器放入存储边缘的容器中。 注意spanning_tree的声明：我在这里使用了一个列表，但是它可以是任何东西，例如向量。 BGL只关心第二个参数必须是标准模板库（STL）输出迭代器类型。
使用BGL的深度优先搜索
广度优先搜索和深度优先搜索（DFS）构成了图遍历的症结，而BGL为这些操作提供了很多支持。 要包含的相关头文件是boost / graph / depth_first_search.hpp; 相应的例程是depth_first_search 。 BGL为depth_first_search提供了多个接口； 它们都需要传递给方法的所谓的访问者对象。
BGL中的访问者在STL中扮演函子的角色，但它的功能更多。 访客没有像operator ( )这样的单一方法，而是可以灵活地定义几种方法，例如initialize_index ， start_index ， discover_index和examine_edge 。 可以肯定地说，BGL使您可以通过提供这些挂钩来自定义DFS。 让我们首先看一下使用DFS的示例代码（ 清单10 ）。
清单10.使用BGL的DFS
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
using namespace std;
using namespace boost;
typedef property<edge_weight_t, int>
EdgeWeightProperty;
typedef boost::adjacency_list
< listS, vecS, undirectedS, no_property, EdgeWeightProperty>
mygraph;
class custom_dfs_visitor : public boost::default_dfs_visitor
{ public: template < typename Vertex, typename Graph >
void discover_vertex(Vertex u, const Graph & g)
const { std::cout << "At " << u << std::endl; }
template < typename Edge, typename Graph >
void examine_edge(Edge e, const Graph& g)
const { std::cout << "Examining edges " << e << std::endl;
}
};
int main()
{
mygraph g; add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
custom_dfs_visitor vis;
depth_first_search(g, visitor(vis));
}
清单10声明了一个名为custom_dfs_visitor的类，该类定义了两个钩子： discover_vertex和examine_edges 。 第一次遇到顶点时调用前者； 发现顶点后，将在顶点的每个出站边调用后者。
那么，什么会在访问者（发生，如果vis ），你有vis是类型boost_default_visitor ？ 是的，您猜对了：显示屏上没有任何内容。 表1简要概述了BGL提供的一些挂钩。
表1.使用DFS进行遍历的BGL挂钩
钩 目的
start_vertex(u, g) 遍历开始之前在源顶点上调用 discover_vertex(u, g) 首次调用顶点时调用 finish_vertex(u, g) 如果u是树的根，则在树的所有其他元素上调用finish_vertex之后将调用finish_vertex 。 如果u是叶子，则在检查了所有从u传出的边之后，将调用此方法。 examine_edge(u, g) 发现u后在其每个输出边缘调用 tree_edge(u, g) 成为构成搜索树的边的成员后在边上调用 back_edge(u, g) 在图形的后边缘调用； 用于无向图，并且由于(u, v)和(v, u)是相同的边，因此tree_edge和back_edge都被调用
请注意，BGL支持其他访问者，例如dijkstra_visitor ， bellman_visitor和astar_visitor 。
结论
本文就是这样。 您已经了解了如何在BGL中创建无向图，有向图和加权图。 与访问器和修饰符函数一起玩； 并尝试在创建的图形上实现一些经典的图形算法。 BGL提供了更多功能，本文只是略述了表面。 请务必查看BGL文档以获取详细信息。
翻译自: https://www.ibm.com/developerworks/aix/library/au-aix-boost-graph/index.html
相关资源：boost graph library
