Увеличение минимального остовного дерева с включением/исключением некоторых ребер

Я пытаюсь реализовать список всех возможных остовных деревьев графа в порядке увеличения стоимости. Я использую алгоритм Sorensen and Janssens (2005). Граф инициализируется следующим образом:

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);

После этого необходимо найти минимальное остовное дерево графа с некоторыми ограничениями, например Edge(2)-(4) не должно быть в MST, а Edge(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));

Но как мне убедиться, что одно из ребер всегда находится в связующем дереве? Я пытался просто добавить Edge в вывод функции Kruskal, но, видимо, это не сработало. Это дает 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));

Можно ли пометить ребра таким образом, чтобы алгоритм Крускала знал, что включать, а что нет?


boost graph minimum-spanning-tree kruskals-algorithm boost-graph
person Vitalii Vorkov    schedule 22.06.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Кажется, вы могли бы принудительно включить определенное ребро, разделив это ребро и вставив две «искусственные» вершины посередине.

Алгоритм 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.

person sehe    schedule 22.06.2015