BGL custom graph connected_components

Question

I'm trying to use the connected_components algorithm of boost graph library. I have a data structure defining such a graph in a different format and I want to avoid copying the graph to the BGL's graph types, such as adjacency_list. Therefore I use the graph_traits to let BGL know how to operate directly on my graph structure. Below is a simplified example exhibiting the same problem I face with the actual data:

#include <vector>
#include <map>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/connected_components.hpp>

namespace myns {
    struct MyGraph {
        using VertsContainer = std::vector<std::string>;
        using Edge = std::pair<std::string, std::string>;
        using EdgesContainer = std::vector<Edge>;

        VertsContainer verts;
        EdgesContainer edges;

        void get_connected_components();
    };
}


namespace boost
{
    template<>
    struct graph_traits<myns::MyGraph> {
        /////////////////////////////////
        // Graph concept
        /////////////////////////////////
        using vertex_descriptor = myns::MyGraph::VertsContainer::value_type;
        using edge_descriptor = myns::MyGraph::EdgesContainer::value_type;

        using directed_category = boost::undirected_tag;
        using edge_parallel_category = boost::disallow_parallel_edge_tag;

        struct traversal_category : boost::vertex_list_graph_tag, boost::incidence_graph_tag {};

        /////////////////////////////////
        // Incidence graph concept
        /////////////////////////////////
        using out_edge_iterator = myns::MyGraph::EdgesContainer::const_iterator;
        using degree_size_type = std::size_t;

        // out_edges(v, g)
        // source(e, g)
        // target(e, g)
        // out_degree(v, g)

        /////////////////////////////////
        // Adjacency graph concept
        /////////////////////////////////
        using adjacency_iterator = myns::MyGraph::VertsContainer::const_iterator;

        // adjacent_vertices(v, g)

        /////////////////////////////////
        // Vertex list graph concept
        /////////////////////////////////
        using vertex_iterator = myns::MyGraph::VertsContainer::const_iterator;
        using vertices_size_type = std::size_t;

        // vertices(g)
        // num_vertices(g)
    };

} // namespace boost 

namespace myns
{
    boost::graph_traits<myns::MyGraph>::vertex_descriptor
        source(const boost::graph_traits<myns::MyGraph>::edge_descriptor& e, const myns::MyGraph& g)
    {
        return e.first;
    }

    boost::graph_traits<myns::MyGraph>::vertex_descriptor
        target(const boost::graph_traits<myns::MyGraph>::edge_descriptor& e, const myns::MyGraph& g)
    {
        return e.second;
    }

    std::pair<boost::graph_traits<myns::MyGraph>::out_edge_iterator, boost::graph_traits<myns::MyGraph>::out_edge_iterator>
        out_edges(const boost::graph_traits<myns::MyGraph>::vertex_descriptor& v, const myns::MyGraph& g)
    {
        return{g.edges.begin(), g.edges.end()};
    }

    boost::graph_traits<myns::MyGraph>::degree_size_type
        out_degree(const boost::graph_traits<myns::MyGraph>::vertex_descriptor& v, const myns::MyGraph& g)
    {
        return g.edges.size();
    }

    std::pair<boost::graph_traits<myns::MyGraph>::adjacency_iterator, boost::graph_traits<myns::MyGraph>::adjacency_iterator>
        adjacent_vertices(const boost::graph_traits<myns::MyGraph>::vertex_descriptor& v, const myns::MyGraph& g)
    {
        return{g.verts.begin(), g.verts.end()};
    }

    std::pair<boost::graph_traits<myns::MyGraph>::vertex_iterator, boost::graph_traits<myns::MyGraph>::vertex_iterator>
        vertices(const myns::MyGraph& g)
    {
        return{g.verts.begin(), g.verts.end()};
    }

    boost::graph_traits<myns::MyGraph>::vertices_size_type
        num_vertices(const myns::MyGraph& g)
    {
        return g.verts.size();
    }

} // namespace myns

static void _test_concepts()
{
    BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<myns::MyGraph>));
    BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<myns::MyGraph>));
}

void myns::MyGraph::get_connected_components()
{
    _test_concepts();

    auto connectedComponentsMap = std::map<std::string, int>{};
    boost::associative_property_map< std::map<std::string, int> > comp_prop_map(connectedComponentsMap);

    boost::connected_components(*this, comp_prop_map);
}

int main()
{
    myns::MyGraph().get_connected_components();
}

The error I get is:

In file included from /usr/local/include/boost/graph/graph_traits.hpp:18:
/usr/local/include/boost/mpl/eval_if.hpp:38:26: error: no type named 'type' in 'boost::no_property'
    typedef typename f_::type type;
        ~~~~~~~~~~~~~^~~~

Full error message and live code here.

What am I missing?

Answer 1

You are missing either a color_map or a vertex_index_map. The algorithms in the Boost.Graph library impose further requirements on the graphs depending on how they are called, due to the defaulted parameters(you can see those in the algorithm documentation). In your invocation you left the color map out and so the algorithm uses its default color map. It tries to get your graph's index map by using boost::get(boost::vertex_index_t, const GraphType&). Since your graph does not have a vertex index property the error occurs. You could either define the required get function like it's done here(although with your current vertex_descriptor it is a little difficult) or simply create your own color map and ignore it afterwards.

Full example

#include <iostream>
#include <vector>
#include <map>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/connected_components.hpp>

namespace myns {
    struct MyGraph {
        using VertsContainer = std::vector<std::string>;
        using Edge = std::pair<std::string, std::string>;
        using EdgesContainer = std::vector<Edge>;

        VertsContainer verts;
        EdgesContainer edges;

        void get_connected_components();
    };
}


namespace boost
{
    template<>
    struct graph_traits<myns::MyGraph> {
        /////////////////////////////////
        // Graph concept
        /////////////////////////////////
        using vertex_descriptor = myns::MyGraph::VertsContainer::value_type;
        using edge_descriptor = myns::MyGraph::EdgesContainer::value_type;

        using directed_category = boost::undirected_tag;
        using edge_parallel_category = boost::disallow_parallel_edge_tag;

        struct traversal_category : boost::vertex_list_graph_tag, boost::incidence_graph_tag {};

        static vertex_descriptor null_vertex(){ return {}; } //ADDED

        /////////////////////////////////
        // Incidence graph concept
        /////////////////////////////////
        using out_edge_iterator = myns::MyGraph::EdgesContainer::const_iterator;
        using degree_size_type = std::size_t;

        // out_edges(v, g)
        // source(e, g)
        // target(e, g)
        // out_degree(v, g)

        /////////////////////////////////
        // Adjacency graph concept
        /////////////////////////////////
        using adjacency_iterator = myns::MyGraph::VertsContainer::const_iterator;

        // adjacent_vertices(v, g)

        /////////////////////////////////
        // Vertex list graph concept
        /////////////////////////////////
        using vertex_iterator = myns::MyGraph::VertsContainer::const_iterator;
        using vertices_size_type = std::size_t;

        // vertices(g)
        // num_vertices(g)
    };

} // namespace boost 

namespace myns
{
    boost::graph_traits<myns::MyGraph>::vertex_descriptor
        source(const boost::graph_traits<myns::MyGraph>::edge_descriptor& e, const myns::MyGraph& g)
    {
        return e.first;
    }

    boost::graph_traits<myns::MyGraph>::vertex_descriptor
        target(const boost::graph_traits<myns::MyGraph>::edge_descriptor& e, const myns::MyGraph& g)
    {
        return e.second;
    }

    std::pair<boost::graph_traits<myns::MyGraph>::out_edge_iterator, boost::graph_traits<myns::MyGraph>::out_edge_iterator>
        out_edges(const boost::graph_traits<myns::MyGraph>::vertex_descriptor& v, const myns::MyGraph& g)
    {
        return{g.edges.begin(), g.edges.end()};
    }

    boost::graph_traits<myns::MyGraph>::degree_size_type
        out_degree(const boost::graph_traits<myns::MyGraph>::vertex_descriptor& v, const myns::MyGraph& g)
    {
        return g.edges.size();
    }

    std::pair<boost::graph_traits<myns::MyGraph>::adjacency_iterator, boost::graph_traits<myns::MyGraph>::adjacency_iterator>
        adjacent_vertices(const boost::graph_traits<myns::MyGraph>::vertex_descriptor& v, const myns::MyGraph& g)
    {
        return{g.verts.begin(), g.verts.end()};
    }

    std::pair<boost::graph_traits<myns::MyGraph>::vertex_iterator, boost::graph_traits<myns::MyGraph>::vertex_iterator>
        vertices(const myns::MyGraph& g)
    {
        return{g.verts.begin(), g.verts.end()};
    }

    boost::graph_traits<myns::MyGraph>::vertices_size_type
        num_vertices(const myns::MyGraph& g)
    {
        return g.verts.size();
    }

} // namespace myns

static void _test_concepts()
{
    BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<myns::MyGraph>));
    BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<myns::MyGraph>));
}

void myns::MyGraph::get_connected_components()
{
    _test_concepts();

    auto connectedComponentsMap = std::map<std::string, int>{};
    boost::associative_property_map< std::map<std::string, int> > comp_prop_map(connectedComponentsMap);

    auto colorMap = std::map<std::string, boost::default_color_type>{};     //ADDED
    boost::associative_property_map< std::map<std::string, boost::default_color_type> > color_prop_map(colorMap);   //ADDED

    boost::connected_components(*this, comp_prop_map, boost::color_map(color_prop_map));    //ADDED
}

int main()
{
    myns::MyGraph().get_connected_components();
    std::cout << "Yay" << std::endl;
}