使用C ++ Boost的graphics库

我很困惑如何实际创build一个graphics使用boost库,我已经看了示例代码,并没有解释它是什么意见。

你如何做一个graphics,并添加顶点和边缘?

下面是一个简单的例子,使用一个邻接表并执行一个拓扑sorting:

#include <iostream> #include <deque> #include <iterator> #include "boost/graph/adjacency_list.hpp" #include "boost/graph/topological_sort.hpp" int main() { // Create an 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; } 

我同意boost :: graph文档可能是令人生畏的。 我build议你看看下面的链接:

http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/table_of_contents.html

我不记得印刷书的内容是否相同,我怀疑它的眼睛更容易一些。 我实际上学会了使用书中的boost:图。 学习曲线虽然可以感觉很陡。 我提到的这本书和评论可以在这里find:

http://www.amazon.com/Boost-Graph-Library-Reference-Manual/dp/0201729148/ref=sr_1_1?ie=UTF8&qid=1326242972&sr=8-1

这是基于在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; } 

Boost的adjacency_list是一个好的方法,这个例子创build一个有向图,并使用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; } 

输出是一个DOT文件,您可以快速input到GraphViz附带的dot实用程序中。

我想你会发现以下资源非常有用。

图论理论入门

如果你不熟悉图论或者需要复习,那么看一下boost的基本图论回顾 : http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html

这篇入门书有助于理解术语,数据结构如何表示图(邻接matrix,邻接表等)和algorithm(广度优先search,深度优先search,最短path等)。

示例代码详细描述

有关创build详细描述的graphics的示例代码,请参阅BorisSchäling在线书籍 – Boost C ++库的以下部分: http ://theboostcpplibraries.com/boost.graph-vertices-and-edges

Boris解释了如何使用adjacenty_list来处理顶点和边缘。 代码被彻底解释,所以你可以理解每个例子。

了解adjacency_list模板参数

理解adjacency_list的模板参数是很重要的。 例如,你想要一个有向图还是无向图? 你想让你的图包含相同的末端节点(即多图)的多条边? 性能也起作用。 鲍里斯的书解释了其中的一些,但你会发现在这里使用adjacenty_list的更多信息: http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html

使用自定义对象的顶点,边缘或graphics

如果你想使用自定义对象的顶点,边缘,甚至graphics本身,那么你会想要使用捆绑属性 。 以下链接将有助于使用捆绑的属性: http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html

也许这也是一个例子: 添加自定义顶点到一个提升图

检测循环依赖(循环)

有多种方法来检测循环依赖包括:

深度优先search :一种简单的方法是通过执行深度优先search并检测search是否运行到当前search树中已经发现的顶点。 这里是一个使用boost的深度优先search来检测循环依赖的例子: http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec : cycles

拓扑sorting :也可以使用拓扑sorting来检测周期。 boost提供了一个topological_sortalgorithm: http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html

拓扑sorting适用于有向无环图(DAG)。 如果传入循环图,则会引发exception,从而表明该图具有循环依赖性。 topological_sort包括深度优先search,但也提供了顶点的线性sorting。 这是一个例子: http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec : cycles

强连通组件 :另外,查找强连通组件可以指示一个图是否有循环: http : //www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm

boost的strong_components函数使用Tarjanalgorithm计算有向图的强连通分量。 http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/strong_components.html

文件相关性示例

另一个有用的链接是已经提供的链接 – boost的文件依赖性示例 ,展示了如何设置源代码文件的graphics,根据它们的编译顺序sorting(拓扑sorting),确定哪些文件可以同时编译,并确定循环依赖: http : //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html

在这里可以find一些关于Boost C ++库的简短和简单的配方:

使用Boost图库

这里列出的这些代码示例显示为合理更新,似乎编译和工作正常。 我发现一些关于使用Boost Graph Library的在线文档似乎已经过时或者会产生编译错误。

这里有许多工作示例,包括创build有向图和无向图,打印边权重,使用Kruskalalgorithm寻找最小生成树,以及最大stream量问题。