BGL 自定义图表 connected_components

Question

我正在尝试使用 boost 图形库的 connected_components 算法。我有一个以不同格式定义此类图形的数据结构，我想避免将图形复制到 BGL 的图形类型，例如 adjacency_list。因此我使用 graph_traits 让 BGL 知道如何直接在我的图结构上操作。下面是一个简化的示例，展示了我在实际数据中遇到的相同问题：

#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();
}

我得到的错误是：

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;
        ~~~~~~~~~~~~~^~~~

完整的错误消息和实时代码 here。

我错过了什么？

Answer 1

您缺少 color_map 或 vertex_index_map。由于默认参数，Boost.Graph 库中的算法根据它们的调用方式对图提出了进一步的要求（您可以在算法 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 中看到那些，然后忽略它。

完整示例

#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;
}

BGL 自定义图表 connected_components

BGL custom graph connected_components

c++

boost

boost-graph