Author: Chris Dellin <cdellin@gmail.com>
Dependencies: boost
The pr_bgl
package contains implemtations of various algorithms and utilities that build atop the Boost Graph Library (BGL). As is customary with BGL, almost everything is implemented generically in headers.
BGL uses Boost property maps heavily to provide access to properties of graphs, vertices, and edges to algorithms in a generic way.
compose_property_map.hpp
compose_property_map
was written by Guillaume Pinot, owned by Eurodecision (2013), and released in Boost 1.54 under the Boost Software License v1.0. It's copied here for users of older versions of Boost.
Test coverage: No.
flag_set_map.h
The flag_set_map
class wraps an existing map by putting true
to an ancillary map (with the same key) whenever the primary wrap is accessed (read or written).
Test coverage: No.
pair_index_map.h
The pair_index_map
class is a readable boost property map which maps from a pair of indexable entities to a master index like C row major order 2d matrix indices.
Test coverage: No.
string_map.h
The string_map
class implements a read-write map which wraps an existing property by allowing converting its values to and from the std::string
instances. It requires that the free functions stringify_from_x()
and stringify_to_x()
for any custom values.
TODO: this may duplicate functionality from boost::lexical_cast
.
Test coverage: No.
throw_map.h
The throw_map
implements a read-write map which throws immediately on get()
or set()
. Useful as an assertion that an instantiation of an algorithm never uses a particular input map.
Test coverage: No.
edge_indexed_graph.h
The edge_indexed_graph
class wraps an existing graph object, while additionally maintaining incrementing edge indices in supplied property maps. The behavior is undefined if edges are not removed in the inverse order that they are added.
Test coverage: No.
graph_io.h
The [read|write]_graphio_[graph|properties]()
functions implement serializing and deserializing a graph and its properties to a custom textual graph format, which stores vertices, edges and properties one per line.
Test coverage: No.
overlay_manager.h
The overlay_manager
class maintains a graph overlay. In other words, given a core graph and an overlay graph, the manager can temporarily "apply" the overlay onto the core graph, copying the appropriate vertices and edges from the overlay to the core graph. It then remembers the applied vertices and edges, so that they can be "unapplied" later (removed from the core graph in reverse order). It is conjectured that this operation is safe on a core implemented as an adjacency list without invalidating vertex descriptors on the core graph (see mailing list).
Test coverage: No.
rev_edge_map.h
The rev_edge_map
class is a readable boost property map which maps from reversed edges to original edges in a reversed graph.
Test coverage: No.
incbi.h
The incbi
class implements incremental bidirectional Dijkstra's search over a graph for the single-source single-sink shortest path problem.
Test coverage: No.
lazysp.h
The lazysp
function implements the Lazy Shortest Path algorithm for the single-pair shortest path problem. It takes as an argument an EvalStrategy
object which determins for the candidate path found at each iteration which edge(s) to select for evaluation.
Related code:
lazysp_incsp_astar.h
- adaptor to use A* for inner searchlazysp_incsp_dijkstra.h
- adaptor to use Dijkstra's for inner searchlazysp_incsp_incbi.h
- adaptor to use incremental bidirectional algorithm for inner searchlazysp_incsp_lpastar.h
- adaptor to use LPA* for inner searchlazysp_selector_partition_all.h
- selector using partition functionslazysp_selector_sp_indicator_probability.h
- selector using sp indicator probabilityTest coverage: Yes.
lpastar.h
Implements the Lifelong Planning A* incremental search algorithm.
Sven Koenig, Maxim Likhachev, and David Furcy. 2004. Lifelong planning A*. Artif. Intell. 155, 1-2 (May 2004), 93-146. DOI=http://dx.doi.org/10.1016/j.artint.2003.12.001
Test coverage: Yes.
path_generator.h
The path_generator
class implements a generator of all simple paths solving the single-source single-sink problem in non-decreasing order of length.
Test coverage: No.
partition_all.h
The partition_all
function calculates the edge-weight partition function over all paths between every pair of vertices on a graph, via a recursive formulation which is linear in the number of edges in the graph.
Test coverage: Yes.
partition_simple.h
The partition_simple
function calculates an approximation to the edge-weight partition function over all simple paths between two given vertices. The implementation returns the value over all simple paths with total length below a given parameter.
Test coverage: Yes.
heap_indexed.h
The heap_indexed
class implements a binary min-heap with index lookups. Elements are identified with an index value (e.g. [0,num_vertices)
). The heap also maintains a vector backing, wich each element at a particular location.
TODO: this may duplicate functionality implemented in BGL.
Test coverage: Yes.
LEMUR is written by Chris Dellin at the Personal Robotics Lab at the Robotics Intitute, Carnegie Mellon University. It was released on April 9, 2015 under a BSD license.
Source code for this package is on GitHub.