Graph Structure Performance Reference
This page provides detailed performance characteristics and complexity analysis for different adjacency_list selector choices. For guidance on choosing a graph structure, see Choosing Your Graph Structure.
Template Parameters
The adjacency_list has the following declaration:
template <class OutEdgeList, class VertexList, class Directed,
class VertexProperties, class EdgeProperties,
class GraphProperties, class EdgeList>
class adjacency_list;
The most important choices are the first three template parameters:
- OutEdgeList: determines the data structure used to store out-edges for each vertex
- VertexList: determines the data structure used to store the set of vertices
- Directed: determines graph directionality (directedS, undirectedS, bidirectionalS)
Selector Types
BGL provides selector types that specify which underlying container to use:
- vecS - std::vector
- listS - std::list
- slistS - std::slist (single-linked list)
- setS - std::set
- multisetS - std::multiset
- hash_setS - std::hash_set
VertexList Performance
This table summarizes the space and time complexities for different VertexList choices:
| VertexList | Space | add_vertex() | remove_vertex() | Vertex Descriptor Stability |
|---|---|---|---|---|
| vecS | O(V) | O(1) amortized | O(V + E) | Invalidated on removal |
| listS | O(V) | O(1) | O(E) | Stable |
| setS | O(V) | O(log(V)) | O(log(V) + E) | Stable |
Analysis:
- vecS: Fastest vertex access, but removing vertices invalidates all vertex descriptors and is expensive
- listS: Stable descriptors survive vertex removal, moderate remove_vertex() cost
- setS: Stable descriptors, but slower operations due to tree structure
OutEdgeList Performance
This table summarizes complexities for different OutEdgeList choices:
| OutEdgeList | Space | add_edge() | remove_edge() | edge() | Parallel Edges |
|---|---|---|---|---|---|
| vecS | O(E) | O(1) amortized | O(E/V) | O(E/V) | Allowed |
| listS | O(E) | O(1) | O(E/V) | O(E/V) | Allowed |
| slistS | O(E) | O(1) | O(E/V) | O(E/V) | Allowed |
| setS | O(E) | O(log(E/V)) | O(log(E/V)) | O(log(E/V)) | Prevented |
| hash_setS | O(E) | O(1) average | O(1) average | O(1) average | Prevented |
Analysis:
- Sequence-based (vecS, listS, slistS): Allow parallel edges, fast add_edge(), but slower remove_edge() and edge() lookup (must scan)
- Set-based (setS, hash_setS): Prevent parallel edges automatically, logarithmic or constant-time edge operations
Iterator Performance
The choice of OutEdgeList affects iterator performance, which is critical since iterating over edges is the workhorse of most graph algorithms:
out_edge_iterator::operator++()
Speed ordering (fastest to slowest): vecS, slistS, listS, setS, hash_setS
Explanation:
- vecS: Contiguous memory, best cache locality, fastest iteration
- slistS: Single-linked list, no previous pointer overhead
- listS: Doubly-linked list, extra pointer per node
- setS: Tree structure, pointer chasing through nodes
- hash_setS: Hash table, worst cache behavior due to bucket traversal
Back to Choosing Your Graph Structure
Copyright © 2000-2001 Jeremy Siek, Indiana University