Lia*_*m M 36
这是一个简单的例子,使用邻接列表并执行拓扑排序:
#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;
}
我同意boost :: graph文档可能令人生畏.我建议你看看下面的链接:
http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/table_of_contents.html
我不记得印刷书籍的内容是否相同,我怀疑它的眼睛有点容易.我实际上学会了使用本书中的boost:graph.虽然学习曲线可能会非常陡峭.我参考和评论的书可以在这里找到:
Yuu*_*shi 25
这是基于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;
}
tle*_*man 14
Boost adjacency_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;
}
输出是一个DOT文件,您可以快速输入dotGraphViz附带的实用程序.
jru*_*upe 12
我想你会发现以下资源非常有用.
如果您不熟悉图论或需要复习,那么请看一下boost的基本图理论评论:http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html
本入门手册有助于理解术语,数据结构如何表示图形(邻接矩阵,邻接列表等)和算法(广度优先搜索,深度优先搜索,最短路径等).
有关创建详细描述的图形的示例代码,请查看BorisSchäling的在线书籍 - Boost C++库的以下部分:http: //theboostcpplibraries.com/boost.graph-vertices-and-edges
Boris解释了如何使用adjacenty_list处理顶点和边.代码已经过彻底解释,因此您可以了解每个示例.
了解adjacency_list的模板参数非常重要.例如,您想要有向图还是无向图？您是否希望图形包含具有相同端节点的多个边(即多图)？表现也发挥作用.Boris的书中解释了其中一些,但您可以在此处找到有关使用adjacenty_list的更多信息:http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html
如果要为顶点,边缘甚至图形本身使用自定义对象,则需要使用捆绑属性.以下链接将有助于使用捆绑的属性:http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html
也许这也是一个例子: 将自定义顶点添加到增强图
有多种方法可以检测循环依赖关系,包括:
深度优先搜索:一种简单的方法是执行深度优先搜索并检测搜索是否在当前搜索树中运行已发现的顶点.以下是使用boost深度优先搜索检测循环依赖关系的示例:http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec : cycles
拓扑排序:还可以使用拓扑排序检测循环.boost提供了topological_sort算法:http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html
拓扑排序适用于有向无环图(DAG).如果传入循环图,则抛出异常,从而指示该图具有循环依赖性.topological_sort包括深度优先搜索,但也提供顶点的线性排序.以下是一个示例: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函数使用Tarjan算法计算有向图的强连通分量. http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/strong_components.html
另一个有用的链接是已经提供的链接 - boost的文件依赖性示例,显示如何设置源代码文件的图形,根据它们的编译顺序(拓扑排序)对它们进行排序,确定可以同时编译哪些文件,以及确定循环依赖性:http: //www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html