使用c++ Boost的图形库

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?

如何制作一个图形，并添加顶点和边?

5 个解决方案

#1

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. I suggest you have a look at the link below:

我同意boost::图形文档可能令人生畏。我建议你看看下面的链接:

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

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

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:书中的图表。但是学习曲线会很陡峭。我参考的书和评论可以在这里找到:

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

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

#2

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;
}

#3

Boost's adjacency_list is a good way to go, this example creates a directed graph and outputs an image of the graph using AT&T's GraphViz:

Boost的邻接_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 dot utility that comes with GraphViz.

输出是一个点文件，您可以快速地将它提供给GraphViz附带的点实用程序。

#4

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/graphs/doc/graph_定理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 Schaling的在线书籍的以下部分——Boost c++库:http://theboostcpplibraries.com/boost.graph-vertices-and-edge。

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解释了如何使用邻接列表处理顶点和边。对代码进行了全面的解释，以便您能够理解每个示例。

Understanding adjacency_list Template Parameters

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

理解邻接_list的模板参数是很重要的。例如，你想要一个有向图还是无向图?您希望您的图包含具有相同末端节点的多条边(即多图)吗?表演也开始发挥作用。Boris的书解释了其中的一些，但是您将在这里找到使用邻接列表的附加信息:http://www.boost. org/doc/libs/1_58_0/libs/graphs/doc/using_neighbour ency_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_doc0/libs/graph/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:循环。

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提供了一个topological_sort算法:http://www.boost.org/doc/libs/1_58_docs/libs/graph/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:cycle

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/算法/ myalgorithm /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 Example that 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/docs/libs/1_58_libs/graphs/graph/doc/file_depend_example.html

#5

Some short and to-the-point recipes in getting started with the Boost C++ libraries can be found here:

在Boost c++库中，可以找到一些简短且切中要害的方法:

Using the Boost Graph Library

使用Boost图形库

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图形库的一些在线文档似乎已经过时或产生编译错误。

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算法找到最小生成树，以及最大流量问题。