astar_search: visitor edge_relaxed method called inconsistently before or after cost map is set

[risicle]

astar_bfs_visitor calls m_vis.edge_relaxed before setting the new cost map value in tree_edge and black_target (and in astar_search_no_init_tree's main loop from the looks of it), but afterwards in gray_target. This is very confusing if you want to look up the new cost value in your visitor method.

[qbit86]

Let me attach the code for clarity.

tree_edge

m_vis.edge_relaxed(e, g);
put(m_cost, target(e, g),
    m_combine(
        get(m_distance, target(e, g)), m_h(target(e, g))));

gray_target

put(m_cost, target(e, g),
    m_combine(
        get(m_distance, target(e, g)), m_h(target(e, g))));
m_Q.update(target(e, g));
m_vis.edge_relaxed(e, g);

black_target

m_vis.edge_relaxed(e, g);
put(m_cost, target(e, g),
    m_combine(
        get(m_distance, target(e, g)), m_h(target(e, g))));
m_Q.push(target(e, g));
put(m_color, target(e, g), Color::gray());
m_vis.black_target(e, g);

At the moment of edge_relaxed event:

• the predecessor map and the distance map are already updated;
• the color map is not updated yet;
• the queue and the cost map are inconsistently updated.

The queue should probably be updated after edge_relaxed, to be consistent with “outer” breadth_first_visit. The cost map should almost certainly be updated before edge_relaxed.

[jeremy-murphy]

Could one of you make a PR to fix it? @qbit86 I think you already have the code ready? :)