Boost Graph Library - 有向圖的最小生成樹

我有一個問題，需要我在Boost圖庫中找到有向圖的最小生成樹。Boost Graph Library - 有向圖的最小生成樹

我第一次嘗試使用深度優先搜索和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; 
}

這是失敗的例子。如果我有以下有向圖

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

深度優先搜索dfs-visitor，1-> 0被分類爲前沿。

如果圖形發生了變化，使邊緣爲0-> 1，那麼它就是樹形邊緣。

從DFS的前沿和源代碼的嚴格定義來看，由於在頂點1之前訪問頂點0，所以它是前沿。

但是，從技術意義上來說，邊1-> 0仍然是樹邊緣，並且從其頁面中給出的定義爲http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html。

前部邊緣是非樹邊（U，V）連接一個頂點u到後裔v在搜索樹。

那麼，在BGL中是否存在一個簡單的解決方案，還是我必須在BGL中實現其中的一種算法？

來源

2016-06-15 Mochan

我結束了從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，因爲我不需要加權圖。它也可以選擇樹根的根。

來源

2016-07-07 20:51:28 Mochan

你正在處理的問題是，正如你可能已經知道的那樣，我們正在處理有向圖的時候搜索最小權重的跨越樹狀圖。樹狀結構是具有指定的根頂點r的圖形，使得可以從r到達所有其他頂點，即存在從r到圖中所有其他頂點的路徑。

不幸的是，Boost Graph Library沒有解決這個問題的算法，因此您需要使用像這樣的第三方實現，或者自己實現一個。上面給出的實現（在github.com上atofigh）使用Edmond's algorithm，這是一種用於解決跨越樹狀結構問題的流行算法。

請記住，算法，如Kruskal算法或Prim算法不工作就由於切割財產有向圖不工作的有向圖。

來源

2016-07-07 13:46:52 dtt

Boost Graph Library - 有向圖的最小生成樹

回答

相關問題