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]