c++ - 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。由于默认参数(您可以在算法 documentation 中看到这些参数)，Boost.Graph 库中的算法根据它们的调用方式对图提出了进一步的要求。在您的调用中，您遗漏了颜色图，因此算法使用其默认颜色图。它尝试使用 boost::get(boost::vertex_index_t, const GraphType&) 获取图表的索引图。由于您的图形没有顶点索引属性，因此会发生错误。您可以像完成一样定义所需的 get 函数 here (尽管使用您当前的 vertex_descriptor 有点困难)或简单地创建 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;
}