PropertyMap

public protocol PropertyMap

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.