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?
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:
After:
(where
v1
andv2
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 ofe1
ande2
and replace it withe
unconditionally.