Question

I'm trying to apply Kruskal's minimum spanning tree to my graph to turn it from a undirected cyclic graph into a real tree. The edge weights are all the same, because it doesn't matter whether the MST is unique or not.

So far I've implemented it as follows:

typedef boost::adjacency_list<boost::setS, boost::listS, 
            boost::undirectedS, CoordNode, CoordSegment> BGraph;

with

class CoordSegment {
public:
    double weight;
[...]
}

and I needed to add some functionality to my graph, therefore my graph object is actually a derivate (if that matters):

class Graph : public BGraph {
protected:
    unsigned int _idCounter;

[...]
}

My problem is here:

// compiles ok
boost::property_map<BGraph, double CoordSegment::*>::type weightMap = boost::get(&CoordSegment::weight, _graph);

    std::vector<EdgeDesc> tree;
// doesn't compile 
    boost::kruskal_minimum_spanning_tree(_graph, std::back_inserter(tree), weightMap);

And it complains as follows:

\src\PGraphSkel.cpp(376) : error C2784: "void boost::kruskal_minimum_spanning_tree(const Graph &,OutputIterator,const boost::bgl_named_params<P,T,R> &)": template-argument for "const boost::bgl_named_params<P,T,R> &" could not be deduced from "boost::bundle_property_map<Graph,Descriptor,Bundle,T>".
1>        with
1>        [
1>            Graph=BGraph,
1>            Descriptor=boost::detail::edge_desc_impl<boost::undirected_tag,void *>,
1>            Bundle=CoordSegment,
1>            T=double
1>        ]
1>        C:\Libraries\boost_1_46_1\boost/graph/kruskal_min_spanning_tree.hpp(120): See declaration of 'boost::kruskal_minimum_spanning_tree'

Why does it complain about it at all?

How can I make my bundled_property_map into the proper bgl_named_params argument needed for this Kruskal MST function?

Was it helpful?

Solution

It is simply not a good idea to inherit from the defined adjacency_list template class. Removing this inheritance solved the problem. Using the boost::graph as a member variable and wrapping everything else in a class around it is much better.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top