0

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?

1 Answer 1

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.