Boost Graph Library - 有向图的最小生成树

Question

我有一个问题需要我在 Boost Graph 库中找到有向图的最小生成树。

我的第一个尝试是使用深度优先搜索和 DFS-visitor。我的计划是忽略除树边回调之外的所有边。这行不通，我在下面给出了原因的示例。

我的问题是我是否可以让我的 dfs-visitor 在 BGL 中创建有向图的最小生成树。

有它的算法并已在此处讨论 (Finding a minimum spanning tree on a directed graph)，我不知道它是否已针对 BGL 实现，或者它只是对 BGL 中已有内容的简单修改。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/depth_first_search.hpp>


struct my_visitor : public boost::dfs_visitor<>
{
    template <class Edge, class Graph>
    void back_edge(Edge e, const Graph&) 
    {
        std::cout << "Back edge: " << e << std::endl;
    }

    template <class Edge, class Graph>
    void forward_or_cross_edge(Edge u, const Graph& g)
    {
        std::cout << "Forward or cross edge: " << u << std::endl;
    }

    template <class Edge, class Graph>
    void tree_edge(Edge u, const Graph& g)
    {
        std::cout << "Tree Edge: " << u << std::endl;
    }
};


int main()
{
    using namespace boost;

    typedef boost::adjacency_list< listS, vecS, bidirectionalS > digraph;

    // Construct the directed graph
    digraph g(2);

    add_edge(1, 0, g);
    //add_edge(0, 1, g);

    my_visitor vis2;
    boost::depth_first_search(g, visitor(vis2));

    return 0;
}

这是失败的例子。如果我有以下有向图

digraph G {
0;
1;
1->0 ;
}

深度优先搜索dfs-visitor，1->0被归类为前缘。

如果图形被改变使得边为0->1，则它是树边。

从前向边的严格定义和DFS的源代码来看，由于顶点0先于顶点1被访问，所以它是前向边。

然而，边 1->0 在技术意义上仍然是树边，并且从他们页面中给出的定义为 http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html。

Forward edges are non-tree edges (u,v) that connect a vertex u to a descendant v in a search tree.

那么，BGL 中是否有简单的解决方案，或者我是否必须为此实现 BGL 中的一种算法？

Answer 1

正如您可能已经知道的那样，您正在处理的问题是在我们处理有向图时寻找最小权重的跨越树状结构。树状图是具有指定根顶点 r 的图，这样所有其他顶点都可以从 r 到达，即存在从 r 到图中所有其他顶点的路径。

不幸的是，Boost Graph Library 中没有解决此问题的算法，因此您需要使用像这样的第 3 方实现 one or implement one yourself. The implementation (by atofigh on github.com) given above uses Edmond's algorithm，这是解决跨越树状结构问题的流行算法。

请记住，Kruskal 算法或 Prim 算法等算法不适用于有向图，因为 cut 属性 不适用于有向图。

Answer 2

我最终使用了 here 中的 Edmonds 算法。谢谢 HueHang，但在收到您的回复之前，我最终找到了算法并使用了它。该问题在大约 3 周内仍未得到解答。

这是我使用edmonds_optimum_branching.hpp的简单测试程序。

#include <iostream>
#include <vector>
#include <utility>
#include <iterator>
#include <cerrno>
#include <boost/concept_check.hpp>
#include <boost/operators.hpp>
#include <boost/multi_array.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>

#include "edmonds_optimum_branching.hpp"

typedef boost::property<boost::edge_weight_t, double>       EdgeProperty;
typedef boost::adjacency_list<boost::listS,
                              boost::vecS,
                              boost::directedS,
                              boost::no_property,
                              EdgeProperty>                 Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor       Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor         Edge;

void main()
{
    const int N = 3;
    Graph G(N);

    std::vector<Vertex> the_vertices;
    BOOST_FOREACH (Vertex v, vertices(G))
        the_vertices.push_back(v);

    add_edge(the_vertices[0], the_vertices[2], 1.0, G);
    add_edge(the_vertices[2], the_vertices[1], 1.0, G);
    add_edge(the_vertices[1], the_vertices[0], 1.0, G);

    std::vector<Edge> branching;
    edmonds_optimum_branching<true, false, false>(G,
        get(boost::vertex_index_t(), G),
        get(boost::edge_weight_t(), G),
        static_cast<Vertex *>(0),
        static_cast<Vertex *>(0),
        std::back_inserter(branching));

    for each (Edge e in branching)
        std::cout << "(" << boost::source(e, G) << ", " << boost::target(e, G) << ")\t" << std::endl;
}

当运行示例代码时，我得到的正确答案是 (2, 1) 和 (0, 2)。

算法returns 最佳分支的边缘。它还具有加权边，可以找到最小或最大权重树。我只是像上面的例子一样使用权重 1，因为我不需要加权图。它还可以为树状结构采根。

Boost Graph Library - 有向图的最小生成树

Boost Graph Library - Minimum Spanning Tree of a Directed Graph

algorithm

boost

graph

tree

boost-graph