I am trying to implement my own A star algorithm. However, I've only come up with a way to get my edge weight values through iterators. Since Iterators access the property map in order, I cannot prioritize edges and need to do a full loop for each vertex to find the neighbors, this would make the algorithm really slow.
Is there any way to use get(), put()... without iterators, selecting the vertices of which I want to check the edges?
This is my program at the moment:
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;
}
}
}
Also, would like to be able to modify the values of f, h and parent within a Point struct.
Any help or guidance will be greatly appreciated.
You can use vertex descriptors instead of the iterators.
In your case, because you are using bundled properties, you can use the operator[descriptor] shorthand on the graph.
You can use this to alter the bundled properties as long as your graph is not const.
It's not actually clear to me what the code in your question was supposed to illustrate. I'll simply reply with a similarly dissociated piece of code that built from there and shows you a few things that might be enlightening :)
#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
}
Printing, for example:
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]