Boost graph Library utilisant les propriétés Bundled

Question

Je suis nouveau à BGL et j'essaie de configurer un programme de recherche de chemin le plus court en utilisant BGL où le graphique non orienté est défini comme une liste d'adjacence avec EdgeProperty et VertexProperty définis. Je reçois une erreur de compilation que j'attribue à mes compétences insuffisantes dans les templates et Boost. Le code est le suivant:

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/directed_graph.hpp> 
#include <boost/graph/graph_traits.hpp> 
#include <boost/graph/dijkstra_shortest_paths.hpp> 
#include<iostream> 
#include <map> 

using namespace std; 
using namespace boost; 
enum Node_type 
{ 
    STAIR, 
    LEVEL, 
    LIFT, 
    OTHER, 
    UNKNOWN 
}; 

class VertexProperty 
{ 
public: 
    VertexProperty(){ id=-1; type=Node_type::UNKNOWN, level_id=254, stair_id=254;} 
    std::string toString() 
    { 
    std::string str; 
    str = "id "+to_string(id)+" type "+to_string(type)+" level "+to_string(level_id)+" stair_id "+to_string(stair_id); 
    return str; 
    } 

    int getVertexID() {return id;} 
    int id; 
    Node_type type; 
    int level_id; 
    int stair_id; 
}; 

class EdgeProperty 
{ 
public: 
    EdgeProperty(){id=-1, weight=0;} 
    EdgeProperty(int i, double wt){ id=i; weight=wt; } 
    double getWeigth(){ return weight;} 
    int getID() {return id;} 
    std::string toString() 
    { 
    std::string str; 
    str = "id "+to_string(id)+" weight="+to_string(weight); 
    return str; 
    } 

    int id; 
    double weight; 
}; 

typedef boost::property<boost::edge_weight_t, double> EdgeWeigthProperty; 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,VertexProperty, EdgeProperty> UndirectedGraph; 
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator; 
typedef boost::graph_traits<UndirectedGraph>::vertex_iterator vertex_iterator; 
typedef boost::directed_graph <boost::no_property, EdgeWeigthProperty> DirectedGraph; 
typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor; 
typedef boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor; 

class A 
{ 
public: 
    A(); 
    void undirected_graph_creation(); 
    void directed_graph_creation(); 
    void showEdges(); 
    void showVertices(); 
    void run_dijkastra(); 
    UndirectedGraph g; 
    DirectedGraph dg; 
    map<int, vertex_descriptor> map_id_vertex_desc; 
    map<int, edge_descriptor> map_id_edge_desc; 
    map<int, Node_type> map_node_id_type; 
}; 

A::A() 

    { 

    } 

    void A::undirected_graph_creation() 
    { 

    UndirectedGraph::vertex_descriptor v0= boost::add_vertex(g); 
    map_id_vertex_desc.emplace(0,v0); 
    g[v0].id=0; 
    g[v0].type=Node_type::LEVEL; 
    UndirectedGraph::vertex_descriptor v1= boost::add_vertex(g); 
    g[v1].id=1; 
    g[v1].type=Node_type::STAIR; 
    map_id_vertex_desc.emplace(1,v1); 
    UndirectedGraph::vertex_descriptor v2= boost::add_vertex(g); 
    map_id_vertex_desc.emplace(2,v2); 
    g[v2].id=2; 
    g[v2].type=Node_type::STAIR; 
    UndirectedGraph::vertex_descriptor v3= boost::add_vertex(g); 
    map_id_vertex_desc.emplace(3,v3); 
    g[v3].id=3; 
    g[v3].type=Node_type::STAIR; 
    /*EdgeWeigthProperty w8(8); 
    EdgeWeigthProperty w18(18); 
    EdgeWeigthProperty w20(20); 
    EdgeWeigthProperty w2(2); 
    EdgeWeigthProperty w7(7);*/ 
    EdgeProperty w8(1,8); 
    EdgeProperty w18(2,18); 
    EdgeProperty w20(3,20); 
    EdgeProperty w2(4,2); 
    EdgeProperty w7(5,7); 

    boost::add_edge(v0,v1,w8,g); 
    boost::add_edge(v0,v3,w18,g); 
    boost::add_edge(v1,v2,w20,g); 
    boost::add_edge(v2,v3,w2,g); 
    boost::add_edge(v1,v3,w7,g); 
} 

void A::showEdges() 
{ 
    std::pair<edge_iterator,edge_iterator> ei=edges(g); 
    std::cout<<" number of edges "<<num_edges(g)<<endl; 
    std::cout<<" Edge list "; 
    for(edge_iterator it= ei.first; it!=ei.second; ++it) 
    cout<<*it<<" "<<g[*it].toString()<<endl; 
} 

void A::showVertices() 
{ 
    std::pair<vertex_iterator, vertex_iterator> vi= boost::vertices(g); 
    std::cout<<" Number of vertices are "<<endl; 
    for(vertex_iterator i = vi.first; i!=vi.second; ++i) 
    { 
    cout<<*i<<" id="<<g[*i].toString()<<" type="<<g[*i].type<<endl; 
    } 

} 
void A::run_dijkastra() 
{ 
    std::vector<vertex_descriptor> predecessors(boost::num_vertices(g)); 
    std::vector<EdgeProperty> distances(boost::num_vertices(g)); 
    std::pair<vertex_iterator,vertex_iterator> vi=boost::vertices(g); 
    vertex_descriptor first_vertex_descriptor = *(vi.first); 
    vertex_descriptor start_vertex = boost::vertex(0,g); 

// boost::dijkstra_shortest_paths(g, first_vertex_descriptor, 
    //        boost::weight_map(get(&EdgeProperty::weight,g)) 
    //        .distance_map(boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, g)))        ); 

dijkstra_shortest_paths(g, first_vertex_descriptor, 
         predecessor_map(make_iterator_property_map(predecessors.begin(), get(vertex_index,g))).distance_map(make_iterator_property_map(distances.begin(), get(boost::vertex_index,g))).weight_map(get(&EdgeProperty::weight,g)); 
/* 
std::cout << "distances and parents:" << std::endl; 
graph_traits <UndirectedGraph>::vertex_iterator vi1, vend1; 
for (boost::tie(vi1, vend1) = vertices(g); vi1 != vend1; ++vi1) { 
    std::cout << "distance(" << g[*vi1].id << ") = " << distances[*vi1].toString() << ", "; 
    std::cout << "parent(" << g[*vi1].id << ") = " << g[predecessors[*vi1]].id << std:: 
    endl; 
}*/ 
} 

void A::directed_graph_creation() 
{ 
//todo 

} 
int main() 
{ 
    A a_graph; 
    a_graph.undirected_graph_creation(); 
    a_graph.showEdges(); 
    a_graph.showVertices();; 
    a_graph.run_dijkastra(); 
    return 0; 
} 

erreur est inconnue conversion de double en EdgeProperty. Il semble que j'ai une erreur dans la syntaxe de l'appel à dijkstra_shortest_paths fonctions.

Je voudrais également remplacer le membre de données de EdgeProperty par une fonction.

D'autres requêtes que j'ai portent sur le maintien d'un index aux nœuds via le descripteur de vertex. Actuellement, j'utilise VertexProperty :: id pour maintenir un dictionnaire à l'objet du type VertexProperty. Do Boost maintient en interne tout dictionnaire que je peux utiliser.

J'utilise compilateur version gcc5.4 sur Ubuntu 16.04 Merci

Nitin

Answer 1

@llonesmiz avait raison sur la marque. Voici un nettoyage général du code et une démo en direct.

J'ai également utilisé make_transform_value_property_map pour utiliser getWeight() et ai rendu tous les membres de données privés.

NOTE Je suspect que les std::map cas ne sont pas vraiment plus utile maintenant que vous utilisez les propriétés (empaquetés?). Dans tous les cas, vous pouvez laisser tomber un peu de code si vous ne avez plus besoin: Shorter Demo

NOTE Vous savez peut-être pas print_graph. Even Shorter, légèrement abrégée sortie

Live On Coliru

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/dijkstra_shortest_paths.hpp> 
#include <boost/property_map/transform_value_property_map.hpp> 
#include <iostream> 
#include <map> 

enum class Node_type { STAIR, LEVEL, LIFT, OTHER, UNKNOWN }; 

static std::ostream& operator<<(std::ostream& os, Node_type type) { 
    switch(type) { 
     case Node_type::STAIR: return os << "STAIR"; 
     case Node_type::LEVEL: return os << "LEVEL"; 
     case Node_type::LIFT: return os << "LIFT"; 
     case Node_type::OTHER: return os << "OTHER"; 
     default: 
     case Node_type::UNKNOWN: return os << "UNKNOWN"; 
    } 
} 

class VertexProperty { 
    public: 
    VertexProperty(int id = -1, Node_type type = Node_type::UNKNOWN, int level_id=254, int stair_id=254) 
     : id(id), type(type), level_id(level_id), stair_id(stair_id) { } 

    std::string toString() const { 
     std::ostringstream oss; 
     oss << *this; 
     return oss.str(); 
    } 

    int getVertexID() { return id; } 

    private: 
    friend std::ostream& operator<<(std::ostream& os, VertexProperty const& v) { 
     return os << "id " << v.id << " type " << v.type << " level " << v.level_id << " stair_id " << v.stair_id; 
    } 

    int id; 
    Node_type type; 
    int level_id; 
    int stair_id; 
}; 

class EdgeProperty { 
    public: 
    EdgeProperty(int i = -1, double wt = 0) : id(i), weight(wt) { 
     id = i; 
     weight = wt; 
    } 
    double getWeight() { return weight; } 
    int getID() { return id; } 

    std::string toString() const { 
     std::ostringstream oss; 
     oss << *this; 
     return oss.str(); 
    } 

    private: 
    friend std::ostream& operator<<(std::ostream& os, EdgeProperty const& e) { 
     return os << "id " << e.id << " weight=" << std::fixed << e.weight; 
    } 

    int id; 
    double weight; 
}; 

class A { 
    public: 
    void undirected_graph_creation(); 
    void showEdges(); 
    void showVertices(); 
    void runDijstra(); 

    private: 
    typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> UndirectedGraph; 
    UndirectedGraph g; 

    using edge_iterator  = UndirectedGraph::edge_iterator; 
    using vertex_iterator = UndirectedGraph::vertex_iterator; 
    using vertex_descriptor = UndirectedGraph::vertex_descriptor; 
    using edge_descriptor = UndirectedGraph::edge_descriptor; 

    std::map<int, vertex_descriptor> map_id_vertex_desc; 
    std::map<int, edge_descriptor> map_id_edge_desc; 
    std::map<int, Node_type>   map_node_id_type; 
}; 

void A::undirected_graph_creation() { 

    auto add_vertex = [this](int id, Node_type type) { 
     // TODO: these maps are probably not required anymore 
     map_node_id_type[id] = type; 
     vertex_descriptor vd = boost::add_vertex(VertexProperty{id, type}, g); 
     return map_id_vertex_desc[id] = vd; 
    }; 

    auto v0 = add_vertex(0, Node_type::LEVEL); 
    auto v1 = add_vertex(1, Node_type::STAIR); 
    auto v2 = add_vertex(2, Node_type::STAIR); 
    auto v3 = add_vertex(3, Node_type::STAIR); 

    auto add_edge = [this](vertex_descriptor u, vertex_descriptor v, EdgeProperty prop) { 
     auto ins = boost::add_edge(u, v, prop, g); 

     if (ins.second) 
      map_id_edge_desc[prop.getID()] = ins.first; 

     return ins.first; 
    }; 

    add_edge(v0, v1, {1, 8}); 
    add_edge(v0, v3, {2, 18}); 
    add_edge(v1, v2, {3, 20}); 
    add_edge(v2, v3, {4, 2}); 
    add_edge(v1, v3, {5, 7}); 
} 

void A::showEdges() { 
    for (auto e : boost::make_iterator_range(boost::edges(g))) 
     std::cout << "Edge " << e << " " << g[e] << "\n"; 
} 

void A::showVertices() { 
    for (auto v : boost::make_iterator_range(boost::vertices(g))) 
     std::cout << "Vertex " << v << " " << g[v] << "\n"; 
} 

void A::runDijstra() { 
    std::vector<vertex_descriptor> predecessors(num_vertices(g)); 
    std::vector<double>   distances(num_vertices(g)); 
    vertex_descriptor start = *(vertices(g).first); 

    auto v_index = get(boost::vertex_index, g); 
    auto weight = boost::make_transform_value_property_map(std::mem_fn(&EdgeProperty::getWeight), get(boost::edge_bundle, g)); 

    dijkstra_shortest_paths(
     g, start, 
     predecessor_map(make_iterator_property_map(predecessors.begin(), v_index)) 
      .distance_map(make_iterator_property_map(distances.begin(), v_index)) 
      .weight_map(weight)); 

    std::cout << "distances and parents:\n"; 
    for (auto v : boost::make_iterator_range(boost::vertices(g))) { 
     auto id = g[v].getVertexID(); 
     std::cout << "distance(" << id << ") = " << distances[v] << ", "; 
     std::cout << "parent(" << id << ") = " << g[predecessors[v]] << "\n"; 
    } 
} 

int main() { 
    A a; 
    a.undirected_graph_creation(); 
    a.showEdges(); 
    a.showVertices(); 

    a.runDijstra(); 
} 

Prints:

Edge (0,1) id 1 weight=8.000000 
Edge (0,3) id 2 weight=18.000000 
Edge (1,2) id 3 weight=20.000000 
Edge (2,3) id 4 weight=2.000000 
Edge (1,3) id 5 weight=7.000000 
Vertex 0 id 0 type LEVEL level 254 stair_id 254 
Vertex 1 id 1 type STAIR level 254 stair_id 254 
Vertex 2 id 2 type STAIR level 254 stair_id 254 
Vertex 3 id 3 type STAIR level 254 stair_id 254 
distances and parents: 
distance(0) = 0.000000, parent(0) = id 0 type LEVEL level 254 stair_id 254 
distance(1) = 8.000000, parent(1) = id 0 type LEVEL level 254 stair_id 254 
distance(2) = 17.000000, parent(2) = id 3 type STAIR level 254 stair_id 254 
distance(3) = 15.000000, parent(3) = id 1 type STAIR level 254 stair_id 254