使用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：
这是基于在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量问题。
