ブーストグラフライブラリ - 指向グラフの最小スパニングツリー

Question

ブーストグラフライブラリで有向グラフの最小スパニングツリーを見つける必要があるという問題があります。

私の最初の試みは、深さの最初の検索とDFSの訪問者を使用することでした。私の計画は、ツリーエッジコールバックを除くすべてのエッジを無視することでした。これはうまくいかず、なぜ私は下の例を挙げます。

私の質問は、私の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; 
} 

ここでは失敗する例を示します。私は深さ優先検索DFS-訪問者に以下の有向グラフ

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

を持っている場合は、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です。

フォワードエッジは、頂点uを検索ツリーの 子孫vに接続する非ツリーエッジ（u、v）です。

したがって、BGLには簡単な解決策がありますか、それともBGLのアルゴリズムの1つを実装する必要がありますか？

Answer 1

エドモンズのアルゴリズムをhereから使い終わった。ありがとう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）という正しい答えが得られます。

アルゴリズムは最適な分岐のエッジを返します。また、重み付きエッジを持ち、最小または最大の重みツリーを見つけることができます。私は重み付けされたグラフを必要としないので、上記の例のように重み1を使用します。それはまた、樹木の根を選ぶことができます。

Answer 2

あなたが扱っている問題は、わかっているように、有向グラフを扱っているので、最低の重さの広がりを求めることです。樹木は、他のすべての頂点がrから到達可能となるように、指定された根頂点rを有するグラフであり、すなわち、rからグラフ内の他のすべての頂点までの経路が存在する。

残念ながら、Boost Graph Libraryにはこの問題を解決するアルゴリズムはありませんので、oneのようなサードパーティの実装を使用するか、自分で実装する必要があります。上記で与えられた実装は、Edmond's algorithmを使用します。これは、広がりのある樹木の問題を解決するための一般的なアルゴリズムです。

カットプロパティが有向グラフで機能しないため、KruskalのアルゴリズムやPrimのアルゴリズムなどのアルゴリズムは、有向グラフでは機能しません。