pr_bgl: Algorithms for Boost Graph

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 search`lazysp_incsp_dijkstra.h`

- adaptor to use Dijkstra's for inner search`lazysp_incsp_incbi.h`

- adaptor to use incremental bidirectional algorithm for inner search`lazysp_incsp_lpastar.h`

- adaptor to use LPA* for inner search`lazysp_selector_partition_all.h`

- selector using partition functions`lazysp_selector_sp_indicator_probability.h`

- selector using sp indicator probability

Test 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.

Generated on Sat Sep 3 2016 01:25:38 for pr_bgl by 1.8.6 using