使用C++ Boost图形库

Question

我对使用boost库创建图表的具体方法感到困惑，我查看了示例代码，但没有注释解释其作用。

在进行操作时如何创建图表以及添加顶点和边缘？

- Jim

---

可能是 https://dev59.com/BHA75IYBdhLWcg3wy8br 的重复问题，该问题有一个很好的答案（包括自定义顶点、边类型的操作说明）。 - Gabriel Devillers

Answer 1

这里有一个简单的例子，使用邻接表并执行拓扑排序：

#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文档可能令人望而生畏，但值得一看。

我记不清印刷版的内容是否相同，但我认为它会更加容易理解。我实际上是从这本书中学会使用boost:graph的。学习曲线可能会感觉非常陡峭。我所提到的书和评论可以在这里找到。

- Liam M

---

我已经将那段代码放在 ideone 上了，我不得不为一些打字错误进行微调。 - Aaron McDaid

即使将boost和std的命名空间加入代码中，该代码仍无法编译。 - gsamaras

@AaronMcDaid，你的链接有误。也许你可以编辑答案中的代码，以便它能够编译？我可以看出num tasks 部分肯定行不通。 - Agostino

@LiamM 当我能提供更正时，我会做出贡献。然而，这不是现在的情况。我无法理解这个问题，最好的办法就是向比我更有经验的人寻求帮助。谢谢。 - Agostino

我同意boost::graph文档可能会让人望而生畏。我建议你看一下下面的链接。我不禁感到，如果他们需要销售参考手册才能使用Boost库，那么他们在实现有用、易于访问和免费的库的目标方面完全失败了。大多数Boost库都很好，并且有良好的文档。我几乎觉得这里的文档需要被彻底重写。 - user650261

Answer 2

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

- Yuushi

---

那么，将A和D之间的最短路径打印出来怎么样？ - user1182183

Answer 3

我认为您会发现以下资源非常有用。

图论基础知识

如果您对图论不熟悉或需要复习，请查看boost的基础图论回顾： http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html

这篇文章有助于理解术语，数据结构如何表示图（邻接矩阵，邻接表等），以及算法（广度优先搜索，深度优先搜索，最短路径等）。

详细描述的示例代码

如果您需要详细描述创建图形的示例代码，请查看Boris Schäling在线书籍的以下部分- The Boost C++ Libraries： http://theboostcpplibraries.com/boost.graph-vertices-and-edges

Boris解释了如何使用adjacenty_list处理顶点和边缘。代码有详细的解释，因此您可以理解每个示例。

了解邻接表模板参数

了解邻接表的模板参数是非常重要的。例如，您需要一个有向图还是无向图？您需要图包含具有相同终节点的多条边（即多重图）吗？性能也很重要。Boris的书籍解释了其中一些，但您可以在此处找到有关使用adjacency_list的其他信息： http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html

使用自定义对象作为顶点、边或图

如果您想要使用自定义对象用于顶点、边甚至是图本身，则需要使用bundled properties。以下链接对于使用捆绑属性将非常有帮助： http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html

我举个例子： 将自定义顶点添加到boost图表中

检测循环依赖（循环）

有多种方法可以检测循环依赖，包括：

深度优先搜索： 一种简单的方法是执行深度优先搜索，并检测搜索是否遇到当前搜索树中已发现的顶点。以下是使用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

- jrupe

---

在我看来，最好的答案应该被接受。它可能不提供任何代码（theboostcpplibraries.com 上有相关内容），但是详细地解释了所有内容。 - PatrykB

Answer 4

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文件，您可以快速将其传递给GraphViz附带的dot实用程序。

- tlehman

Answer 5

这里提供了一些简短而直观的食谱，以便开始使用Boost C ++库：

使用Boost Graph Library

这里列出的代码示例似乎相当新，并且编译和工作正常。 我发现一些关于使用Boost Graph Library的在线文档似乎已经过时或会产生编译错误。

这里有许多工作示例，包括创建有向和无向图，打印边缘权重，使用Kruskal算法查找最小生成树以及最大流问题。

- AndyUK