Boost minimum spanning tree with some edges included/excluded

Question

I'm trying to implement the list of all possible spanning trees of a graph in order of increasing cost. I'm using the algorithm by Sorensen and Janssens (2005). The graph is initialized as follows:

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

After this it's necessary to find the minimum spanning tree of a graph with some limitations, for instance Edge(2)-(4) shouldn't be in MST and Edge(1)-(2) should be there.

For the edge exclusion it's possible to use remove_edge_if(..) to delete the edge from the graph.

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

But how should I ensure that one of the edges is always in the spanning tree? I was trying just to add some Edge into output of the Kruskal function, but it didn't work apparently. It yields MST of the graph + added edge:

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

Is it possible to mark the edges in a way that Kruskal algorithm knows what to include and what not to?

sehe sehe · Accepted Answer · 2015-06-22T14:41:05

I seems you could force the inclusion of a certain edge by splitting this edge and inserting two "artificial" vertices in the middle.

The MST algorithm is already required to produce a tree of edges that covers all vertices.

Because the artifical vertices have been purposely added by you, it's easy to make sure it's never reachable using any other edges.

Before:

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

After:

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

(where v1 and v2 are the vertices inserted).

After the fact you "collapse" any sequence of (e1,em,e2) or (e2,em,e1) into (e).

You might end up with a tree that reaches v1 and v2 but never traverses em. In that case you can simply drop one of e1 and e2 and replace it with e unconditionally.

Boost minimum spanning tree with some edges included/excluded

1 Answers