Augment custom weights to edge descriptors in boost::grid_graph

Question

I am using BGL for a custom AStar search. Basically, the nodes of the graph correspond to the cells of a map, and each cell has an elevation.

I've created an cell traversal score function stepTime which takes in the elevation of two cells, and outputs a cost function. I wanna add this cost function to the edge weights in my boost graph.

How do I go about this? I've seen functions using

auto weightmap = make_transform_value_property_map

to create a weight map, but how do I update the weights according to the output of:

double stepTime(const vertex_descriptor& source, const vertex_descriptor& target, const std::vector<uint8_t>& elevation)

Tagging https://stackoverflow.com/users/85371/sehe since they appear to answer most boost-graph related questions I've seen here — Jim, Aug 30 '17 at 18:05
Lol. No need. I'm here anyways. Tagging [tag:boost-graph] tends to work. — sehe, Aug 30 '17 at 21:03

score 2 · Accepted Answer · answered Aug 30 '17 at 21:14

but how do I update the weights according to the output of:
 double stepTime(const vertex_descriptor& source, const vertex_descriptor& target, const std::vector<uint8_t>& elevation)

I have no clue where you get the elevation vector from, but I guess that's your problem.

The source and target vertices are easily gotten from the graph itself, so here goes:

auto custom = boost::make_function_property_map<Graph::edge_descriptor>(
        [&g,&elevation](Graph::edge_descriptor e) {
            return stepTime(boost::source(e, g), boost::target(e, g), elevation);
        });

Demo

Live On Coliru

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

using Graph = boost::adjacency_list<>;

double stepTime(const Graph::vertex_descriptor& source, const Graph::vertex_descriptor& target, const std::vector<uint8_t>& elevation) {
    std::cout << __FUNCTION__ << "(" << source << ", " << target << ", {" << elevation.size() << " elements})\n";
    return 42;
}

int main() {
    Graph g(10);
    add_edge(4, 5, g);
    add_edge(2, 8, g);
    add_edge(5, 1, g);
    add_edge(1, 3, g);

    std::vector<uint8_t> const elevation { 1,2,3,4,5,6 }; // or whatevs

    // custom weight map
    auto custom = boost::make_function_property_map<Graph::edge_descriptor>(
            [&g,&elevation](Graph::edge_descriptor e) {
                return stepTime(boost::source(e, g), boost::target(e, g), elevation);
            });

    // pass it to an algorithm directly, or wrap it in a named-parameter object:
    auto param = boost::weight_map(custom);
    param.weight_map2(custom); // or as the alternative weight map
}

Thank you so much! The fact that it can update weights with an external function with one line of code makes it pretty powerful. — Jim, Aug 30 '17 at 22:06
Beware of potential issues. Astar should be fine, as it's driven heuristically, but some algorithms might not ever complete with wrong kind of dynamic feedback in the weight function. (E.g. randomly inverting weights on a shortest path search). Algorithms can make assumptions about the repeatability. And depending on how they're implemented not choose to keep track of previously evaluated cost functions. BGL documentation seems to do a decent job documenting these kind of assumptions (requirements). — sehe, Aug 30 '17 at 22:09
And yes, property maps are a very powerful concept, see e.g. https://stackoverflow.com/questions/27863061/map-set-get-requests-into-c-class-structure-changes/27863767#27863767 (or just search my answers for the many usage examples) — sehe, Aug 30 '17 at 22:12

Augment custom weights to edge descriptors in boost::grid_graph

1 Answers1

Demo