Graph Property Maps

Abstracts over storage location for values associated with graphs.

Graph algorithms often need to store data during the course of execution, such as vertex color (during search), or the costs of traversing an edge (e.g. Dijkstra’s algorithm). While some graph types can store data within the graph structure itself. (e.g. AdjacencyList allows associating data with every vertex and edge.) Some graph data structures are not materialized whatsoever (e.g. the possible moves on a knight’s tour on a chess board). Additionally, data is often needed only during the course of an algorithm, and is discarded afterwards. As a result, it would be inefficient to pay the cost of requiring every graph implementation to persist this transient state. Fortunately, property maps allow us to leverage “in-graph” storage when it is available, while also allowing data to be stored outside the graph when convenient as well, all behind a single abstraction. In short, thanks to the PropertyMap protocol, we can write an algorithm once using one or more PropertyMap’s, and the algorithm can be re-used independent of whether the data is stored within the graph data structure or in a separate data structure.

External property maps store data outside the graph.

A ParallelCapablePropertyMap is one that can be used with ParallelGraphs in vertex-parallel algorithms.

A table-based external property map.

An external property map backed by a dictionary.

A read-only property map whose values are computed by a closure.

Transforms an existing property map (Underlying) to project out a single underlying field from its Value.

Beware: this results in extra copies when mutating the underlying values.

A PropertyMap over the vertices of Graph.

A PropertyMap over the edges of Graph.