algorithm - 如何使用 get() boost 图

Question

我正在尝试实现我自己的 A 星算法。但是，我只是想出了一种通过迭代器获取边权重值的方法。由于迭代器按顺序访问属性映射，我无法确定边的优先级并且需要为每个顶点执行完整循环以找到邻居，这会使算法非常慢。

有没有什么方法可以在没有迭代器的情况下使用 get()、put()...，选择我要检查边的顶点？

这是我目前的程序:

struct Point {//struct point with vertex properties
    int x, y;
    int parentx, parenty;
    double g;
    double h;
     friend std::ostream& operator<<(std::ostream& os, Point p) {
      return os << "[" << p.x << "," << p.y << "]";
    }
};

int main() {
//declarations
typedef property < edge_weight_t, double >Weight;
using std::vector;//?
using Graph = adjacency_list<setS, vecS, undirectedS, Point, Weight>;//graph includes our created point struct property<edge_weight_t
using vertex_descriptor = Graph::vertex_descriptor;
Graph lattuce;


    //lattuce graph is created with weighted edges value 1 or 1,41 if diagonal. The functions used on a loop are:
//add_edge(nodes[p.x][p.y],nodes[neighbour.x][neighbour.y], Weight(1.0), lattuce);
//add_edge(nodes[p.x][p.y],nodes[neighbour.x][neighbour.y], Weight(1.4), lattuce);

        typedef Graph::edge_iterator EdgeIterator;
        std::pair<EdgeIterator, EdgeIterator> edges = boost::edges(lattuce);

        typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap;

        WeightMap weights = boost::get(boost::edge_weight_t(), lattuce);
        //cout<<get(weights,(1,2));

        EdgeIterator edge;
        for (edge = edges.first; edge != edges.second; ++edge) {
          std::cout << boost::get(weights, *edge) <<" "<< *edge<< "   ";

          if (source(*edge, lattuce) == origin || target(*edge, lattuce)==origin ){
            get(weights, *edge);
              cout<<"Edge related to the origin   ";
          }
          if (source(*edge, lattuce) == end_vertex || target(*edge, lattuce)==end_vertex ){
              cout<<"Edge related to the end_vertex   ";
          }
          if (get(weights, *edge)==1.41){
              cout<<" Diagonal"<<endl;
          }
          else if (get(weights, *edge)==1){
              cout<<"    Unitary"<<endl;
          }
          else if (get(weights, *edge)==99999999.0){
              cout<<"Infinite"<<endl;

          }

        }
}

此外，还希望能够修改 Point 结构中的 f、h 和 parent 的值。

任何帮助或指导将不胜感激。

Answer 1

回答您的问题

您可以使用顶点描述符代替迭代器。

在您的情况下，因为您使用的是捆绑属性，所以您可以在图表上使用 operator[descriptor] 速记。

只要您的图形不是常量，您就可以使用它来更改捆绑属性。

代码

我实际上并不清楚您问题中的代码应该说明什么。我将简单地用从那里构建的类似分离的代码来回复，并向您展示一些可能有启发性的东西:)

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/random.hpp>
#include <iostream>

#include <random>

static std::mt19937 s_rng { std::random_device{}() };
static std::uniform_int_distribution<> s_coord(-10,10);
static std::uniform_real_distribution<double> s_double(-1.,1.);

static int gen_coord() { return s_coord(s_rng); }
static int gen_gh   () { return s_double(s_rng); }

struct Point { // struct point with vertex properties
    int x = gen_coord(), y = gen_coord();
    int parentx = gen_coord(), parenty = gen_coord();
    double g = gen_gh();
    double h = gen_gh();

    friend std::ostream &operator<<(std::ostream &os, Point p) { return os << "[" << p.x << "," << p.y << "]"; }
};

// declarations
typedef boost::property<boost::edge_weight_t, double> Weight;
using Graph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, Point, Weight>;
using vertex_descriptor = Graph::vertex_descriptor;

int main() {
    Graph lattuce;

    using namespace boost;
    generate_random_graph(lattuce, 10, 20, s_rng);

    vertex_descriptor origin     = vertex(0, lattuce);
    vertex_descriptor end_vertex = vertex(9, lattuce);

    typedef boost::property_map<Graph, boost::edge_weight_t>::type WeightMap;

    WeightMap weights = boost::get(boost::edge_weight_t(), lattuce);

    for (Graph::edge_descriptor edge : make_iterator_range(edges(lattuce))) {
        std::cout << boost::get(weights, edge) << " " << edge << "   ";

        vertex_descriptor src = source(edge, lattuce);
        vertex_descriptor trg = target(edge, lattuce);

        Point& src_bundle = lattuce[src];
        Point& trg_bundle = lattuce[trg];

        std::cout << "Edge: " << src_bundle << " -- " << trg_bundle << "\n";

        src_bundle.g *=  1.1;
        src_bundle.h *= -1.1;

        //double weight = get(weights, edge);
    }

    (void) origin; // unused
    (void) end_vertex; // unused
}

打印，例如:

0 (7,5)   Edge: [-5,-5] -- [-9,-6]
0 (9,2)   Edge: [3,2] -- [-3,3]
0 (3,4)   Edge: [-4,-10] -- [-10,-5]
0 (1,6)   Edge: [3,4] -- [-7,7]
0 (9,4)   Edge: [3,2] -- [-10,-5]
0 (3,8)   Edge: [-4,-10] -- [-6,0]
0 (1,9)   Edge: [3,4] -- [3,2]
0 (5,9)   Edge: [-9,-6] -- [3,2]
0 (6,9)   Edge: [-7,7] -- [3,2]
0 (0,1)   Edge: [-9,8] -- [3,4]
0 (1,4)   Edge: [3,4] -- [-10,-5]
0 (0,2)   Edge: [-9,8] -- [-3,3]
0 (9,3)   Edge: [3,2] -- [-4,-10]
0 (2,4)   Edge: [-3,3] -- [-10,-5]
0 (7,6)   Edge: [-5,-5] -- [-7,7]
0 (1,2)   Edge: [3,4] -- [-3,3]
0 (0,9)   Edge: [-9,8] -- [3,2]
0 (4,7)   Edge: [-10,-5] -- [-5,-5]
0 (1,5)   Edge: [3,4] -- [-9,-6]
0 (0,7)   Edge: [-9,8] -- [-5,-5]