This class implements incremental bidirectional Dijkstra's search for the single-pair shortest path problem. More...

#include <incbi.h>

Classes
struct	conn_key

Public Types
typedef boost::graph_traits < Graph >::vertex_descriptor	Vertex

typedef boost::graph_traits < Graph >::vertex_iterator	VertexIter

typedef boost::graph_traits < Graph >::edge_descriptor	Edge

typedef boost::graph_traits < Graph >::out_edge_iterator	OutEdgeIter

typedef boost::graph_traits < Graph >::in_edge_iterator	InEdgeIter

typedef boost::property_traits < WeightMap >::value_type	weight_type

Public Member Functions
	incbi (const Graph &g, Vertex v_start, Vertex v_goal, StartPredecessorMap start_predecessor, StartDistanceMap start_distance, StartDistanceLookaheadMap start_distance_lookahead, GoalSuccessorMap goal_successor, GoalDistanceMap goal_distance, GoalDistanceLookaheadMap goal_distance_lookahead, WeightMap weight, VertexIndexMap vertex_index_map, EdgeIndexMap edge_index_map, CompareFunction compare, CombineFunction combine, CostInf inf, CostZero zero, weight_type goal_margin, IncBiVisitor vis, IncBiBalancer balancer)

void	reset ()

weight_type	start_calculate_key (Vertex u)

weight_type	goal_calculate_key (Vertex u)

void	update_edge (Edge e)

bool	start_update_predecessor (Vertex u, Vertex v, double uv_weight)

void	start_update_vertex (Vertex u)

bool	goal_update_successor (Vertex u, Vertex v, double uv_weight)

void	goal_update_vertex (Vertex v)

std::pair< size_t, bool >	compute_shortest_path ()

Public Attributes
const Graph &	g

Vertex	v_start

Vertex	v_goal

StartPredecessorMap	start_predecessor

StartDistanceMap	start_distance

StartDistanceLookaheadMap	start_distance_lookahead

GoalSuccessorMap	goal_successor

GoalDistanceMap	goal_distance

GoalDistanceLookaheadMap	goal_distance_lookahead

WeightMap	weight

VertexIndexMap	vertex_index_map

EdgeIndexMap	edge_index_map

CompareFunction	compare

CombineFunction	combine

CostInf	inf

CostZero	zero

weight_type	goal_margin

IncBiVisitor	vis

IncBiBalancer	balancer

heap_indexed< weight_type >	start_queue

heap_indexed< weight_type >	goal_queue

heap_indexed< conn_key >	conn_queue

Detailed Description

template<class Graph, class StartPredecessorMap, class StartDistanceMap, class StartDistanceLookaheadMap, class GoalSuccessorMap, class GoalDistanceMap, class GoalDistanceLookaheadMap, class WeightMap, class VertexIndexMap, class EdgeIndexMap, typename CompareFunction, typename CombineFunction, typename CostInf, typename CostZero, class IncBiVisitor, class IncBiBalancer>
class pr_bgl::incbi< Graph, StartPredecessorMap, StartDistanceMap, StartDistanceLookaheadMap, GoalSuccessorMap, GoalDistanceMap, GoalDistanceLookaheadMap, WeightMap, VertexIndexMap, EdgeIndexMap, CompareFunction, CombineFunction, CostInf, CostZero, IncBiVisitor, IncBiBalancer >

This class implements incremental bidirectional Dijkstra's search for the single-pair shortest path problem.

for now, we assume an undirected graph (that is, update_edge will attempt an upate in both directions) we assume that everything is constant (graph structure) rhs = one-step-lookahead (based on d/g) d (DynamicSWSF-FP) = g (LPA*) value = distance map rhs (DynamicSWSF-FP) = rhs (LPA*) = distance_lookahead_map

see "Efficient Point-to-Point Shortest Path Algorithms" by Andrew V. Goldberg et. al for correct bidirection Dijkstra's termination condition

original implemetation from 2015-04

be careful: this class uses the CostInf template argument for decisions about infinities and non-existant paths; if the underlying edge weights use a different value, performace can suffer!

Invariant 1: start_distlook[v] = min_pred(v) { start_dist[u] + w(u,v) }

Invariant 2: iff start_distlook[v] != start_dist[u], then inconsistent (also conn queue stuff)

The documentation for this class was generated from the following file:

pr_bgl/include/pr_bgl/incbi.h

Classes

Public Types

Public Member Functions

Public Attributes

Detailed Description