初始化自定義邊界類的內部邊緣索引

Question

我對BGL（boost圖形庫）非常陌生。當我嘗試使用平面映射遍歷時，遇到以下編譯問題，任何人都可以向我解釋我做錯了什麼？導致錯誤的代碼是：

put(e_index, *ei, edge_count++); 

planar_face_traversal(g, &embedding[0], v_vis); 

planar_face_traversal(g, &embedding[0], e_vis); 


/usr/include/boost/property_map/property_map.hpp:361: error: no match for 'operator=' in '(&((const boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, boost::detail::error_property_not_found&, long unsigned int, boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t>&)pa))->boost::adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property, Tag>::operator[] [with Directed = boost::undirected_tag, Value = boost::detail::error_property_not_found, Ref = boost::detail::error_property_not_found&, Vertex = long unsigned int, Property = boost::property<boost::edge_bundle_t, Edge, boost::no_property>, Tag = boost::edge_index_t, boost::adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property, Tag>::key_type = boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>](k) = v' 

/usr/include/boost/property_map/property_map.hpp:391: error: no match for 'operator+' in '((const boost::iterator_property_map<__gnu_cxx::__normal_iterator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >*, std::vector<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::allocator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > > > > >, boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t>, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >*, std::vector<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::allocator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > > > > >, boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t>, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >&>::iter + boost::get [with PropertyMap = boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t>, Reference = const boost::detail::error_property_not_found&, K = boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>]((*(const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t> >*)(&((const boost::iterator_property_map<__gnu_cxx::__normal_iterator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >*, std::vector<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::allocator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > > > > >, boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t>, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >*, std::vector<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::allocator<std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > > > > >, boost::adj_list_edge_property_map<boost::undirected_tag, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, long unsigned int, const boost::property<boost::edge_bundle_t, Edge, boost::no_property>, boost::edge_index_t>, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >, std::map<long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>, std::less<long unsigned int>, std::allocator<std::pair<const long unsigned int, boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int> > > >&>::index)), (*(const boost::detail::edge_desc_impl<boost::undirected_tag, long unsigned int>*)(& v)))' 

#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/properties.hpp> 
#include <boost/graph/graph_traits.hpp> 
#include <boost/property_map/property_map.hpp> 
#include <boost/ref.hpp> 
#include <vector> 

#include <boost/graph/planar_face_traversal.hpp> 
#include <boost/graph/boyer_myrvold_planar_test.hpp> using namespace boost; 



// Some planar face traversal visitors that will // print the vertices and edges on the faces 

class Vertex{ public: 
    int i;//just some variable 
    Vertex(){} 
    Vertex(int val){ 
     i = val; 
    } }; 

class Edge{ public: 
    int i;//just some variable 
    Edge(){} 
    Edge(int val){ 
     i = val; 
    } }; 

struct output_visitor : public planar_face_traversal_visitor { void begin_face() { std::cout << "New face: "; } void end_face() { std::cout << std::endl; } }; 



struct vertex_output_visitor : public output_visitor { void next_vertex(Vertex v) { 
    std::cout << v.i << " "; } }; 

struct edge_output_visitor : public output_visitor { void next_edge(Edge e) { 
    std::cout << e.i << " "; } }; 

int main(int argc, char** argv) { 

    typedef adjacency_list 
    < vecS, 
     vecS, 
     undirectedS, 
     Vertex, 
     Edge 
    > 
    graph; 

    // Create a graph - this is a biconnected, 3 x 3 grid. // It should have four small (four vertex/four edge) faces and // one large face that contains all but the interior vertex graph g; 


    typedef boost::graph_traits<graph>::vertex_descriptor VertexDescriptor; typedef boost::graph_traits<graph>::edge_descriptor EdgeDescriptor; 

    VertexDescriptor v0 = add_vertex(g); VertexDescriptor v1 = add_vertex(g); VertexDescriptor v2 = add_vertex(g); VertexDescriptor v3 = add_vertex(g); VertexDescriptor v4 = add_vertex(g); add_edge(v0,v1,g); add_edge(v1,v2,g); add_edge(v2,v3,g); add_edge(v3,v4,g); add_edge(v4,v0,g); 

    add_edge(v0,v2,g); add_edge(v0,v3,g); 

    add_edge(v1,v4,g); add_edge(v1,v3,g); 

    add_edge(v2, v4, g); 

    // Initialize the interior edge index property_map<graph, edge_index_t>::type e_index = get(edge_index, g); 


    graph_traits<graph>::edges_size_type edge_count = 0; graph_traits<graph>::edge_iterator ei, ei_end; for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { 
     put(e_index, *ei, edge_count++); 
     std::cout << *ei << std::endl; } 

    // Test for planarity - we know it is planar, we just want to // compute the planar embedding as a side-effect 


    typedef std::vector< graph_traits<graph>::edge_descriptor > vec_t; std::vector<vec_t> embedding(num_vertices(g)); std::cout << num_vertices(g) << std::endl; if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, 
            boyer_myrvold_params::embedding = 
             &embedding[0] 
            ) 
    ) 
    std::cout << "Input graph is planar" << std::endl; else 
    std::cout << "Input graph is not planar" << std::endl; 


    std::cout << std::endl << "Vertices on the faces: " << std::endl; vertex_output_visitor v_vis; planar_face_traversal(g, &embedding[0], v_vis); 

    std::cout << std::endl << "Edges on the faces: " << std::endl; output_visitor e_vis; planar_face_traversal(g, &embedding[0], e_vis); 

    return 0; } 

Answer 1

您的代碼有幾個問題。導致編譯器錯誤的一個原因是您的圖表沒有內部edge_index屬性，而您正在嘗試使用該屬性。將EdgeProperty更改爲property<edge_index_t,std::size_t,Edge>即可輕鬆解決。您的xxx_output_visitors也有問題。 next_vertex和next_edge分別指望vertex_descriptor和edge_descriptor。我已經在下面改變它們來做一些「有用」的事情。最後一個問題是boyer_myrvold_planarity_test對於您的圖返回false。因爲我真的不知道關於問題域的事情，所以我只是改變了你的圖，發現了here。

更新：如果你想避免使用property<edge_index_t,std::size_t,Edge>，你可以簡單地創建一個外部屬性映射，然後將它傳遞給planar_face_traversal。除非您也使用參數kuratowski_subgraph，否則boyer_myrvold_planarity_test不需要通過邊緣索引圖。

#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/properties.hpp> 
#include <boost/graph/graph_traits.hpp> 
#include <boost/property_map/property_map.hpp> 
#include <boost/graph/iteration_macros.hpp> 
#include <boost/ref.hpp> 
#include <vector> 

#include <boost/graph/planar_face_traversal.hpp> 
#include <boost/graph/boyer_myrvold_planar_test.hpp> 

using namespace boost; 



// Some planar face traversal visitors that will 
// print the vertices and edges on the faces 

class Vertex 
{ 
    public: 
    int i;//just some variable 
    Vertex(){} 
    Vertex(int val){ 
     i = val; 
    } 
}; 

class Edge 
{ 
    public: 
    int i;//just some variable 
    Edge(){} 
    Edge(int val){ 
     i = val; 
    } 
}; 


typedef adjacency_list 
    < vecS, 
     vecS, 
     undirectedS, 
     Vertex, 
     Edge 
    > 
    graph_type; 

struct output_visitor : public planar_face_traversal_visitor 
{ 
    void begin_face() { std::cout << "New face: "; } 
    void end_face() { std::cout << std::endl; } 
}; 



struct vertex_output_visitor : public output_visitor 
{ 
    vertex_output_visitor(const graph_type& g_):g(g_){} 
    template <typename VertexDesc> 
    void next_vertex(VertexDesc v) 
    { 
     //std::cout << g[v].i << " "; //This would do what you wanted if you initialize "i" 
     std::cout << get(vertex_index,g,v) << " "; 
    } 

    const graph_type& g; 
}; 

struct edge_output_visitor : public output_visitor 
{ 
    edge_output_visitor(const graph_type& g_):g(g_){} 
    template <typename EdgeDesc> 
    void next_edge(EdgeDesc e) 
    { 
     //std::cout << g[e].i << " "; //This would do what you wanted 
     std::cout << source(e,g) << "-" << target(e,g) << " "; 
    } 

    const graph_type& g; 
}; 

int main() { 



    // Create a graph - this is a biconnected, 3 x 3 grid. 
    // It should have four small (four vertex/four edge) faces and 
    // one large face that contains all but the interior vertex 
    graph_type g; 


    typedef boost::graph_traits<graph_type>::vertex_descriptor VertexDescriptor; 
    typedef boost::graph_traits<graph_type>::edge_descriptor EdgeDescriptor; 

    VertexDescriptor A = add_vertex(g); 
    VertexDescriptor B = add_vertex(g); 
    VertexDescriptor C = add_vertex(g); 
    VertexDescriptor D = add_vertex(g); 
    VertexDescriptor E = add_vertex(g); 
    add_edge(A,B,g); 
    add_edge(A,C,g); 
    add_edge(A,D,g); 
    add_edge(A,E,g); 
    add_edge(B,D,g); 
    add_edge(B,E,g); 
    add_edge(C,D,g); 
    add_edge(C,E,g); 
    add_edge(D,E,g); 


    typedef std::map<EdgeDescriptor, size_t> EdgeIndexMap; 
    EdgeIndexMap mapIndex; 
    boost::associative_property_map<EdgeIndexMap> my_edge_index_map(mapIndex); 
    graph_traits<graph_type>::edges_size_type current_index=0; 
    BGL_FORALL_EDGES(e,g,graph_type) 
    { 
     put(my_edge_index_map,e,current_index++); 
     std::cout << e << std::endl; 
    } 

    // Test for planarity - we know it is planar, we just want to 
    // compute the planar embedding as a side-effect 


    typedef std::vector< graph_traits<graph_type>::edge_descriptor > vec_t; 
    std::vector<vec_t> embedding(num_vertices(g)); 
    std::cout << num_vertices(g) << std::endl; 

    //if you use the parameter "kuratowski_subgraph" you'll need to pass also my_edge_index_map 
    if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g, 
            boyer_myrvold_params::embedding = 
             &embedding[0] 
            ) 
    ) 
    std::cout << "Input graph is planar" << std::endl; 
    else 
    std::cout << "Input graph is not planar" << std::endl; 


    std::cout << std::endl << "Vertices on the faces: " << std::endl; 
    vertex_output_visitor v_vis(g); 
    planar_face_traversal(g, &embedding[0], v_vis, my_edge_index_map); 

    std::cout << std::endl << "Edges on the faces: " << std::endl; 
    edge_output_visitor e_vis(g); 
    planar_face_traversal(g, &embedding[0], e_vis, my_edge_index_map); 

    return 0; 
}