Choosing Your Graph Structure

BGL provides three main concrete graph data structures, each representing different assumptions about data representation and access patterns:

• adjacency_list - A flexible, general-purpose structure suitable for most applications
• adjacency_matrix - Optimized for dense graphs with fast edge queries
• compressed_sparse_row_graph - A memory-efficient, static structure for large graphs

Choosing the right structure is a top-level decision that should be made before refining configuration details through selector types. The following flowchart provides a quick decision path for selecting the appropriate graph data structure based on key characteristics such as mutability, memory constraints, density, and query requirements:

Configuration of the Graph Structure

---

Adjacency List

Once it has been decided to use adjacency_list as the top-level data structure, its three key template arguments must also be configured:

• Directed: graph directionality - directedS (one-way edges), undirectedS (symmetric edges), or bidirectionalS (access both in-edges and out-edges)
• OutEdgeList: container for storing out-edges - vecS (allows parallel edges, fast iteration) or setS (prevents parallel edges)
• VertexList: container for storing vertices - vecS (fast access, unstable descriptors) or listS (stable descriptors)

For example, with no data attached to vertices, edges nor graph:

using Graph = boost::adjacency_list< boost::vecS,         // OutEdgeList
                                     boost::vecS,          // VertexList  
                                     boost::directedS,     // Directed
                                     boost::no_property,   // Vertex data access
                                     boost::no_property,   // Edge data access
                                     boost::no_property >; // Graph data access

The following flowchart provides a guide for selecting these configuration parameters, the bold lines representing the choice path defaulted by the BGL:

Key Trade-offs

• Sequence-based (vecS, listS, slistS): Allow parallel edges, fast add_edge(), slower remove_edge() and edge() lookup
• Set-based (setS, hash_setS): Prevent parallel edges, slower add_edge() due to duplicate checking, faster remove_edge() and edge() lookup

Common Configurations

// General purpose: fast iteration, allows parallel edges (DEFAULT)
typedef adjacency_list<vecS, vecS, directedS> Graph;

// No parallel edges: automatically prevents duplicates
typedef adjacency_list<setS, vecS, directedS> Graph;

// Dynamic graph: stable descriptors when adding/removing vertices
typedef adjacency_list<vecS, listS, directedS> Graph;

// Undirected graph
typedef adjacency_list<vecS, vecS, undirectedS> Graph;

// Bidirectional: access both in-edges and out-edges
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

Recommendations

1. Start with adjacency_list<vecS, vecS, directedS> - it's the fastest for most operations
2. Switch to setS for OutEdgeList if you need to prevent parallel edges
3. Use listS for VertexList if you need stable vertex descriptors
4. Choose bidirectionalS if your algorithms need to traverse edges in both directions
5. Profile your code if performance is critical - the best choice depends on your specific usage pattern

For detailed performance characteristics and complexity analysis, see the Performance Reference page.

---

Adjacency Matrix

Once it has been decided to use adjacency_matrix as the top-level data structure, its main template argument must be configured:

• Directed: graph directionality - directedS (full V×V matrix) or undirectedS (symmetric, lower triangle only)

For example, with no data attached to vertices, edges nor graph:

using Graph = boost::adjacency_matrix< boost::directedS,     // or undirectedS
                                       boost::no_property,   // Vertex data access
                                       boost::no_property,   // Edge data access
                                       boost::no_property >; // Graph data access

The following flowchart provides a guide for selecting the directionality, the bold line representing the choice path defaulted by the BGL:

Key Characteristics

• Fixed vertex count: Number of vertices must be specified at construction and cannot change
• O(1) edge operations: Adding, removing, and checking edge existence are constant-time
• O(V²) space: Always uses V×V space regardless of actual edge count (V²/2 for undirected)
• Best for dense graphs: Efficient when E ≈ V² (more than ~25% of possible edges)

Common Configurations

// Directed graph (DEFAULT)
typedef adjacency_matrix<directedS> Graph;

// Undirected graph (symmetric, saves space)
typedef adjacency_matrix<undirectedS> Graph;

Recommendations

1. Use adjacency_matrix only for dense graphs where E > V²/4
2. Ensure vertex count is reasonable (< 10K vertices to avoid memory issues)
3. Use undirectedS for undirected graphs to save 50% space
4. Consider adjacency_list<setS, vecS, ...> for sparse graphs needing O(1) edge lookup

---

Compressed Sparse Row Graph

Once it has been decided to use a compressed_sparse_row_graph as the top-level data structure, its three key template arguments must also be configured:

• Directed: whether the graph stores only out-edges (directedS) or both out-edges and in-edges (bidirectionalS)
• Vertex: the unsigned integer type used for vertex indices (uint16_t, uint32_t, or size_t)
• EdgeIndex: the unsigned integer type used for edge indices, which can be larger than the Vertex type for dense graphs

For example, with no data attached to vertices, edges nor graph:

using Graph = boost::compressed_sparse_row_graph< boost::directedS,    // or bidirectionalS
                                                  boost::no_property,  // Vertex data access
                                                  boost::no_property,  // Edge data access
                                                  boost::no_property,  // Graph data access
                                                  uint32_t,            // Vertex type
                                                  uint32_t >;          // EdgeIndex type

The following flowchart provides a guide for selecting these configuration parameters, the bold lines representing the choice path defaulted by the BGL:

Key Characteristics

• Immutable structure: Cannot add or remove vertices/edges after construction
• Minimal memory: Most compact representation, O(V + E) space
• Fastest iteration: Cache-friendly contiguous storage for optimal traversal
• Static graphs only: Best for graphs loaded once and queried many times

Common Configurations

// Default: directedS, size_t for Vertex and EdgeIndex
typedef compressed_sparse_row_graph<directedS> Graph;

// Small graph: uint16_t for memory optimization (< 65K vertices)
typedef compressed_sparse_row_graph<directedS, no_property, no_property, 
                                    no_property, uint16_t, uint16_t> Graph;

// Bidirectional: access both in-edges and out-edges
typedef compressed_sparse_row_graph<bidirectionalS> Graph;

// Dense graph: different Vertex and EdgeIndex types
typedef compressed_sparse_row_graph<directedS, no_property, no_property,
                                    no_property, uint16_t, uint32_t> Graph;

Recommendations

1. Use default directedS and size_t types unless memory is critical
2. Choose bidirectionalS only if you need to traverse edges backward
3. Optimize with uint16_t or uint32_t for very large graphs to reduce memory
4. Use different EdgeIndex type only for near-complete graphs where edge count exceeds vertex type maximum
5. Prefer sorted edge construction (edges_are_sorted) for best performance

---

Further Reading