c++11 - 使用捆绑属性 boost 图形库

标签 c++11 generics boost graph boost-graph

我是 BGL 的新手，正在尝试使用 BGL 设置一个简单的最短路径查找程序，其中无向图被定义为具有自定义 EdgeProperty 和 VertexProperty 的邻接列表。我收到编译时错误，我将其归因于我在模板和 Boost 方面的技能不足。 代码如下:

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

错误是从 double 到 EdgeProperty 的未知转换。看来我在调用 dijkstra_shortest_paths 函数的语法中有错误。

我还想用函数替换 EdgeProperty 的数据成员。

我的其他查询是关于通过顶点描述符维护节点的索引。目前，我正在使用 VertexProperty::id 维护 VertexProperty 类型对象的字典。 Do Boost 在内部维护我可以使用的任何字典。

我在Ubuntu 16.04上使用gcc5.4版本的编译器 谢谢

尼汀

最佳答案

@llonesmiz 说对了。这是代码的一般清理和现场演示。

我还使用 make_transform_value_property_map 来使用 getWeight() 并将所有数据成员设为私有(private)。

NOTE I suspect that the std::map instances aren't really useful anymore now that you use bundled properties (?). In any case, you could drop some code if you don't need them any more: Shorter Demo

NOTE You might not know about print_graph. Even Shorter, slightly abbreviated output

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

打印:

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

关于c++11 - 使用捆绑属性 boost 图形库，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46379211/

上一篇：r - 列出包的依赖关系，不管它是如何加载或安装的

下一篇：r - 使用 tsDyn 进行预测 - R 中的错​​误

相关文章：

c++ - 正确的(资源处理)零规则在哪里？

Java泛型——获取类的实例

c# - 具有泛型和 `InternalsVisibleTo` 的内部构造函数

c++11 中 boost::filesystem::copy_file() 缺少符号

C++ 连接许多 std::vectors 并删除重复项

c++ - boost::property 树的任何标准库实现

java - 泛型扩展

c++ - 如何获取 boost::fusion::map 中值的类型？

c++ - 是否可以使用 static_cast 从可变枚举创建 boost::mpl::list_c？

c++ - 使用 cpp-netlib 的异步客户端响应？

©2024 IT工具网  联系我们