包含/排除某些邊的提升最小生成樹

我試圖按照成本增加的順序實現圖的所有可能生成樹的列表。我正在使用Sorensen and Janssens (2005)的算法。 - （4）不應該在MST和邊緣（包含/排除某些邊的提升最小生成樹

typedef property<edge_weight_t, int> EdgeWeightProperty; 
typedef adjacency_list<vecS, vecS, undirectedS, no_property, EdgeWeightProperty> Graph; 
typedef Graph::edge_descriptor Edge; 
typedef Graph::vertex_descriptor Vertex; 
typedef boost::graph_traits<Graph>::edge_iterator EdgeIterator; 
typedef std::pair<EdgeIterator, EdgeIterator> EdgePair; 
Graph g; 

add_edge(1, 2, 3, g); 
add_edge(1, 3, 1, g); 
add_edge(1, 4, 2, g); 
add_edge(2, 3, 3, g); 
add_edge(2, 4, 1, g);

此有必要找到一些限制圖的最小生成樹後，例如邊緣（2）：圖形如下初始化1） - （2）應該在那裏。

對於邊緣排除，可以使用remove_edge_if（..）從圖中刪除邊緣。

template<typename WMap> 
class Remover 
{ 
public: 
    Remover(const WMap& weights, int threshold) 
     : m_weights(weights), m_threshold(threshold) {} 

    template<typename ED> 
    bool operator()(ED w) const { return m_weights[w] <= m_threshold; } 

private: 
    const WMap& m_weights; 
    int   m_threshold; 
}; 

.... 
// remove edges of weight < 1 
Remover< property_map<Graph, edge_weight_t>::type> r(get(edge_weight, g), 1); 
remove_edge_if(r, g); 
.... 
std::list <Edge> spanning_treeT; 
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_treeT));

但我應該如何確保其中一條邊總是在生成樹中？我只是想在Kruskal函數的輸出中添加一些Edge，但它顯然不起作用。它產生的圖形的MST +額外的優勢：

std::list <Edge> spanning_tree_g2; 
Vertex u, v; 
EdgePair ep = edges(g2); 
u = source(*ep.first, g2); 
v = target(*ep.first, g2); 
Edge ed = edge(u, v, g2).first; 
spanning_tree_g2.push_front(ed); 
kruskal_minimum_spanning_tree(g2, std::back_inserter(spanning_tree_g2));

是否有可能在該秩算法知道什麼包括什麼不可以的方式邊沿標記？

來源

2015-06-22 Vitalii Vorkov

我似乎可以通過分割這條邊並在中間插入兩個「人造」頂點來強制包含某個邊。

MST算法已經需要產生邊緣樹，涵蓋所有頂點。

由於人爲添加了人造頂點，因此很容易確保使用任何其他邊緣都無法訪問它。

前：

------------------[e:w1+w2]------------------

後：

----[e1:w1]---(v1)---[em:0]---(v2)---[e2:w2]----

（其中v1和v2插入頂點）。

事實上，您將(e1,em,e2)或(e2,em,e1)的任何序列「合攏」爲(e)。

您可能會得到一棵樹，達到v1和v2，但從不遍歷em。在這種情況下，您可以簡單地刪除e1和e2之一，並無條件地將其替換爲e。

來源

2015-06-22 14:41:05 sehe

包含/排除某些邊的提升最小生成樹

回答

相關問題