c++ - 不允许循环引用的 boost 图

Question

我是 boost 图表的新手，正在研究最适合我需要的图表。我需要创建一个依赖图并给定一个顶点，我需要访问进出边。我在想一个带有 Directed=bidirectionalS 的 adjacency_list。

但是我需要确保当我调用 add_edge 并且它导致循环引用时它必须出错。我似乎找不到如何执行此操作。

Answer 1

一般来说，只有一种方法可以发现图是否是非循环的:遍历所有节点。

因此您只需要在添加每条边后检查图形是否仍然是非循环的。

但是，根据您添加节点的方式，您可以进行优化。如果，例如您通过按 DFS 顺序从源遍历节点来添加边，您可以只跟踪当前路径中“看到”的节点，并拒绝向这些节点添加出边。

基于topological_sort 的简单示例 Live On Coliru :

#include <iostream>  // for std::cout
#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/graphviz.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/function_output_iterator.hpp>

using namespace boost;

int main()
{
    srand(time(0));

    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
    const int num_vertices = 10;
    Graph g(num_vertices);

    // add random edges to the graph object
    for (size_t i = 0; i < 10; ++i)
    {
        auto f = rand()%num_vertices,
             s = rand()%num_vertices;

        add_edge(f, s, g);
        try {
            topological_sort(g, boost::make_function_output_iterator([](int){}));
        } catch(not_a_dag const& e)
        {
            remove_edge(f, s, g);
            std::cerr << "dropped edge: " << e.what() << "\n";
        }
    }

    write_graphviz(std::cout, g);
}

创建随机 DAG，如