使用 C++ Boost 的图形库
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8812466/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using C++ Boost's Graph Library
提问by Jim
I am confused about how to actually create a Graph using the boost library, I have looked at the example code and there are no comments explaining what it does.
我对如何使用 boost 库实际创建图形感到困惑，我查看了示例代码，但没有解释它的作用的注释。
How do you make a graph, and add vertices and edges as you go?
您如何制作图形并随时添加顶点和边？
采纳答案by Liam M
Here's a simple example, using an adjacency list and executing a topological sort:
这是一个简单的例子，使用邻接表并执行拓扑排序：
#include <iostream>
#include <deque>
#include <iterator>
#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/topological_sort.hpp"
int main()
{
// Create a n adjacency list, add some vertices.
boost::adjacency_list<> g(num tasks);
boost::add_vertex(0, g);
boost::add_vertex(1, g);
boost::add_vertex(2, g);
boost::add_vertex(3, g);
boost::add_vertex(4, g);
boost::add_vertex(5, g);
boost::add_vertex(6, g);
// Add edges between vertices.
boost::add_edge(0, 3, g);
boost::add_edge(1, 3, g);
boost::add_edge(1, 4, g);
boost::add_edge(2, 1, g);
boost::add_edge(3, 5, g);
boost::add_edge(4, 6, g);
boost::add_edge(5, 6, g);
// Perform a topological sort.
std::deque<int> topo_order;
boost::topological_sort(g, std::front_inserter(topo_order));
// Print the results.
for(std::deque<int>::const_iterator i = topo_order.begin();
i != topo_order.end();
++i)
{
cout << tasks[v] << endl;
}
return 0;
}
I agree that the boost::graph documentation can be intimidating, but it's worth having a look.
我同意了boost ::图形文件可以恐吓，而是有它的价值的外观。
I can't recall if the contents of the printed book is the same, I suspect it's a bit easier on the eyes. I actually learnt to use boost:graph from the book. The learning curve can feel pretty steep though. The book I refer to and reviews can be found here.
我不记得印刷书的内容是否相同，我怀疑它在眼睛上更容易一些。我实际上从书中学会了使用 boost:graph。不过，学习曲线可能会感觉很陡峭。我参考的书和评论可以在这里找到。
回答by Yuushi
This is based off the example given on the boost::graph website, with comments added:
这是基于 boost::graph 网站上给出的示例，并添加了评论：
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.hpp"
using namespace boost;
int main(int argc, char *argv[])
{
//create an -undirected- graph type, using vectors as the underlying containers
//and an adjacency_list as the basic representation
typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;
//Our set of edges, which basically are just converted into ints (0-4)
enum {A, B, C, D, E, N};
const char *name = "ABCDE";
//An edge is just a connection between two vertitices. Our verticies above
//are an enum, and are just used as integers, so our edges just become
//a std::pair<int, int>
typedef std::pair<int, int> Edge;
//Example uses an array, but we can easily use another container type
//to hold our edges.
std::vector<Edge> edgeVec;
edgeVec.push_back(Edge(A,B));
edgeVec.push_back(Edge(A,D));
edgeVec.push_back(Edge(C,A));
edgeVec.push_back(Edge(D,C));
edgeVec.push_back(Edge(C,E));
edgeVec.push_back(Edge(B,D));
edgeVec.push_back(Edge(D,E));
//Now we can initialize our graph using iterators from our above vector
UndirectedGraph g(edgeVec.begin(), edgeVec.end(), N);
std::cout << num_edges(g) << "\n";
//Ok, we want to see that all our edges are now contained in the graph
typedef graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
//Tried to make this section more clear, instead of using tie, keeping all
//the original types so it's more clear what is going on
std::pair<edge_iterator, edge_iterator> ei = edges(g);
for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
}
std::cout << "\n";
//Want to add another edge between (A,E)?
add_edge(A, E, g);
//Print out the edge list again to see that it has been added
for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
}
//Finally lets add a new vertex - remember the verticies are just of type int
int F = add_vertex(g);
std::cout << F << "\n";
//Connect our new vertex with an edge to A...
add_edge(A, F, g);
//...and print out our edge set once more to see that it was added
for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
}
return 0;
}
回答by tlehman
Boost's adjacency_listis a good way to go, this example creates a directed graph and outputs an image of the graph using AT&T's GraphViz:
Boostadjacency_list是一个很好的方法，这个例子创建了一个有向图，并使用 AT&T 的 GraphViz 输出了该图的图像：
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
int main()
{
using namespace std;
using namespace boost;
/* define the graph type
listS: selects the STL list container to store
the OutEdge list
vecS: selects the STL vector container to store
the vertices
directedS: selects directed edges
*/
typedef adjacency_list< listS, vecS, directedS > digraph;
// instantiate a digraph object with 8 vertices
digraph g(8);
// add some edges
add_edge(0, 1, g);
add_edge(1, 5, g);
add_edge(5, 6, g);
add_edge(2, 3, g);
add_edge(2, 4, g);
add_edge(3, 5, g);
add_edge(4, 5, g);
add_edge(5, 7, g);
// represent graph in DOT format and send to cout
write_graphviz(cout, g);
return 0;
}
The output is a DOT file that you can quickly feed into the dotutility that comes with GraphViz.
输出是一个 DOT 文件，您可以将其快速输入到dotGraphViz 附带的实用程序中。
回答by jrupe
I think you will find the following resources very helpful.
我认为您会发现以下资源非常有帮助。
Graph Theory Primer
图论入门
If you are unfamiliar with graph theory or need a refresher, then take a look at boost's Review of Elementary Graph Theory: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html
如果您不熟悉图论或需要复习，请查看 boost 的基本图论综述：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html
This primer is helpful in understanding the terminology, how data structures represent graphs (adjacency matrix, adjacency list, etc…), and algorithms (breadth-first search, depth-first search, shortest-path, etc…).
这本入门读物有助于理解术语、数据结构如何表示图（邻接矩阵、邻接表等）和算法（广度优先搜索、深度优先搜索、最短路径等）。
Sample Code Described in Detail
示例代码详述
For sample code for creating graphs that is described in detail, then take a look at the following section of Boris Sch?ling's online book - The Boost C++ Libraries: http://theboostcpplibraries.com/boost.graph-vertices-and-edges
有关创建详细描述的图形的示例代码，请查看 Boris Sch?ling 的在线书籍 - The Boost C++ Libraries的以下部分：http: //theboostcpplibraries.com/boost.graph-vertices-and-edges
Boris explains how to work with vertices and edges using the adjacenty_list. The code is thoroughly explained so you can understand each example.
Boris 解释了如何使用 nexty_list 处理顶点和边。对代码进行了彻底的解释，因此您可以理解每个示例。
Understanding adjacency_list Template Parameters
了解 adjacency_list 模板参数
It is important to understand the template parameters for the adjacency_list. For example, do you want a directed or undirected graph? Do you want your graph to contain multiple edges with the same end nodes (i.e. multigraphs)? Performance also comes into play. Boris' book explains some of these, but you will find additional information on using the adjacenty_list here: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html
了解 adjacency_list 的模板参数很重要。例如，您想要有向图还是无向图？您是否希望您的图包含具有相同末端节点的多条边（即多重图）？性能也发挥作用。鲍里斯的书解释了其中的一些，但您可以在此处找到有关使用邻接表的更多信息：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html
Using Custom Objects for Vertices, Edges, or Graphs
为顶点、边或图形使用自定义对象
If you want to use custom objects for the vertices, edges, or even the graph itself, then you will want to use bundled properties. The following links will be helpful for using bundled properties: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html
如果您想为顶点、边甚至图形本身使用自定义对象，那么您将需要使用捆绑属性。以下链接将有助于使用捆绑属性：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html
And perhaps this one too for an example: adding custom vertices to a boost graph
也许这也是一个例子： 将自定义顶点添加到提升图
Detecting Circular Dependencies (Cycles)
检测循环依赖（循环）
There are multiple ways to detect circular dependencies including:
有多种方法可以检测循环依赖，包括：
Depth-First Search: One simple way is by performing a depth-first search and detecting if the search runs into an already discovered vertex in the current search tree. Here is an example of detecting cyclic dependencies using boost's depth-first search: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles
深度优先搜索：一种简单的方法是执行深度优先搜索并检测搜索是否遇到当前搜索树中已发现的顶点。以下是使用 boost 的深度优先搜索检测循环依赖的示例：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec: cycles
Topological Sort: One can also detect cycles using a topological sort. boost provides a topological_sort algorithm: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html
拓扑排序：还可以使用拓扑排序来检测循环。boost 提供了一种拓扑排序算法：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html
A topological sort works on a directed acyclic graph (DAG). If a cyclic graph is passed in, then an exception is thrown, thus indicating that the graph has a circular dependency. topological_sort includes a depth-first search, but also provides a linear ordering of the vertices. Here is an example: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles
拓扑排序适用于有向无环图 (DAG)。如果传入一个循环图，则抛出异常，从而表明该图具有循环依赖。topological_sort 包括深度优先搜索，但也提供顶点的线性排序。这是一个例子：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec: cycles
Strongly Connected Components: Additionally, finding strongly connected components can indicate whether or not a graph has cycles: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm
强连通分量：此外，查找强连通分量可以表明图是否有环：http: //www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm
boost's strong_components function computes the strongly connected components of a directed graph using Tarjan's algorithm. http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/strong_components.html
boost 的 strong_components 函数使用 Tarjan 算法计算有向图的强连通分量。 http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/strong_components.html
File Dependency Example
文件依赖示例
Another helpful link is one that was already provided - boost's File Dependency Examplethat shows how to setup a graph of source code files, order them based on their compilation order (topological sort), determine what files can be compiled simultaneously, and determine cyclic dependencies: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html
另一个有用的链接是已经提供的 - boost 的文件依赖示例，它展示了如何设置源代码文件的图形，根据它们的编译顺序（拓扑排序）对它们进行排序，确定哪些文件可以同时编译，并确定循环依赖：http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html
回答by AndyUK
Some short and to-the-point recipes in getting started with the Boost C++ libraries can be found here:
可以在此处找到有关 Boost C++ 库入门的一些简短而中肯的方法：
These code samples listed on here appear reasonably up to date and appear to compile and work fine. I am finding that some of the online documentation concerning the use of the Boost Graph Library seems to be out of date or produces compilation errors.
此处列出的这些代码示例似乎是最新的，并且似乎可以编译并正常工作。我发现一些关于使用 Boost Graph Library 的在线文档似乎已经过时或产生编译错误。
There are a number of working examples here including creating directed and undirected graphs, printing the weights of edges, finding minimal spanning trees using Kruskal's algorithm, and maximum flow problems.
这里有许多工作示例，包括创建有向图和无向图、打印边的权重、使用 Kruskal 算法找到最小生成树以及最大流问题。
