Boost Graph Library - 有向图的最小生成树 [英] Boost Graph Library - Minimum Spanning Tree of a Directed Graph

问题描述

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

I have a problem that requires me to find the minimum spanning tree of a directed graph in Boost Graph Library.

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

My first try was to use the depth first search and DFS-visitor. My plan was to ignore all the edges except the tree edges callback. This doesn't work and I give the example below on why.

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

My question is if I can make my dfs-visitor create a minimum spanning tree of a directed graph in BGL.

有它的算法并且已经在这里讨论(在有向图上找到最小生成树)，我不知道它是否已为 BGL 实现，或者它只是对 BGL 中已有内容的简单修改.

There are algorithms for it and has been discussed here (Finding a minimum spanning tree on a directed graph) and I can't tell if it's been implemented for BGL or not or it's just a simple modification of something that's already in 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;
}

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

Here is the example that fails. If I have the following directed graph

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

深度优先搜索dfs-visitor，1->0被归类为前向边.

In depth first search dfs-visitor, 1->0 is classified as a forward edge.

如果图被改变使得边为 0->1，那么它是树边.

If the graph was changed so that the edge is 0->1, then it is a tree edge.

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

From the strict definition of the forward edge and the source code of DFS, since vertex 0 is visited before vertex 1, it is a forward edge.

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

However, the edge 1->0 is still a tree edge in a technical sense and from the definition given in their page as http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html.

前向边是将顶点 u 连接到顶点的非树边 (u,v)搜索树中的后代 v.

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

那么，在 BGL 中是否有一个简单的解决方案，还是我必须在 BGL 中为它实现其中一种算法?

So, is there a simple solution in BGL or do I have to implement one of the algorithms in BGL for it?

推荐答案

我最终使用了来自 here 的 Edmonds 算法.谢谢 HueHang，但我最终找到了算法并在得到你的回复之前使用了它.这个问题在大约 3 周内仍未得到解答.

I ended up using Edmonds's Algorithm from here. Thanks HueHang but I ended up finding the algorithm before and using it before I got your reply. The question remained unanswered for about 3 weeks.

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

Here is my simple test program using the 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).

I get the correct answer as (2, 1) and (0, 2) when the run the sample code.

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

The algorithm returns the edges for the optimum branching. It also has weighted edges and can find the minimum or maximum weight tree. I just use weight 1 as in the example above since I don't need weighted graphs. It can also pick the root for the arborescence.

这篇关于Boost Graph Library - 有向图的最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！