Skip to content

containers.md

Latest commit

 

History

History
961 lines (742 loc) · 37.8 KB

containers.md

File metadata and controls

961 lines (742 loc) · 37.8 KB
graph-v3 logo

Graph Containers

graph-v3 ships three purpose-built graph containers. Each satisfies the adjacency list concepts so all CPOs, views, and algorithms work interchangeably.

← Back to Documentation Index

Container Storage Mutability Best for
dynamic_graph Traits-configured vertex + edge containers Mutable General purpose, flexible container choice
compressed_graph CSR (Compressed Sparse Row) Immutable after construction Read-only, high performance, memory-compact
undirected_adjacency_list Dual doubly-linked lists per edge Mutable, O(1) edge removal Undirected graphs, frequent edge insertion/removal
adjacency_matrix Dense n x n cell array Fixed order, mutable cells Small/dense graphs, O(1) edge existence queries

All four live in graph::container.

You can also use graphs without any library container:

1. dynamic_graph

#include <graph/container/dynamic_graph.hpp>
#include <graph/container/traits/vov_graph_traits.hpp>  // pick your trait

namespace graph::container {
template <class EV     = void,       // edge value type
          class VV     = void,       // vertex value type
          class GV     = void,       // graph value type
          class VId    = uint32_t,   // vertex id type
          bool Bidirectional = false, // maintain incoming-edge lists?
          class Traits = vofl_graph_traits<EV, VV, GV, VId, Bidirectional>>
class dynamic_graph;
}

dynamic_graph is the most flexible container. Its vertex and edge storage are determined entirely by the Traits parameter, which names the concrete vertices_type and edges_type (e.g., std::vector<vertex_type> and std::forward_list<edge_type>).

When Bidirectional is true, each vertex maintains an additional incoming-edge list, enabling the in_edges, in_degree, find_in_edge, and contains_in_edge CPOs in O(1) / O(in-degree). This is required by the bidirectional_adjacency_list concept and enables reverse traversal via in_edge_accessor.

Properties

Property Value
Vertex ID assignment Contiguous (0 .. N-1) for v/d traits; sparse user-defined keys for m/u traits
Vertex range Random access (v/d), bidirectional (m), forward (u)
Edge range per vertex Random access (v/d), forward (fl/us), bidirectional (l/s/m)
Partitions No
Append vertices/edges Yes

Complexity guarantees

Complexity depends on the vertex container, the edge container, or neither.

Vertex-container-dependent operations:

Operation v/d m u
find_vertex(g, uid) O(1) O(log V) O(1) avg
Add vertex O(1) amortized O(log V) O(1) avg

Edge-container-dependent operations:

Operation v/d/l fl s/em us
find_vertex_edge(g, u, vid) O(degree) O(degree) O(log degree) O(1) avg
Add edge O(1) amortized† O(1) O(log degree) O(1) avg
degree(g, u) O(1) O(degree) O(1) O(1)

† O(1) amortized for v/d (reallocation); O(1) for l (no reallocation).

Container-independent operations:

Operation Complexity
num_vertices(g) O(1)
num_edges(g) O(1)
has_edges(g) O(1)

Template parameters

Parameter Default Description
EV void Edge value type (void → no edge values)
VV void Vertex value type (void → no vertex values)
GV void Graph value type (void → no graph value)
VId uint32_t Vertex ID type (integral for indexed traits, any ordered/hashable type for map-based traits)
Bidirectional false When true, each vertex maintains an incoming-edge list, enabling in_edges(g,u), in_degree(g,u), find_in_edge(g,...), and contains_in_edge(g,...). Satisfies bidirectional_adjacency_list<G>.
Traits vofl_graph_traits<…> Trait struct that defines the vertex and edge container types

Quick usage

#include <graph/container/dynamic_graph.hpp>
#include <graph/container/traits/vov_graph_traits.hpp>

using namespace graph::container;

// vector of vertices with vector of edges
// Weighted edges (double), labeled vertices (string), no graph value
using Traits = vov_graph_traits<double, std::string>;
using G      = dynamic_adjacency_graph<Traits>;

G g;
// ... populate with load_edges / load_vertices ...

The dynamic_adjacency_graph<Traits> alias extracts EV, VV, GV, VId, and Bidirectional from the traits struct, so you only need one template argument.

Each traits header also provides a convenience graph alias that matches how tests are written (for example, dod_graph in test_dynamic_graph_dod.cpp):

#include <graph/container/traits/dod_graph_traits.hpp>

using namespace graph::container;

using G0 = dod_graph<>;                                      // EV=VV=GV=void
using G1 = dod_graph<int, std::string, void, uint32_t, true>; // bidirectional

Trait combinations

Traits follow the naming convention {vertex}o{edge}_graph_traits — vertex container abbreviation, the letter o, edge container abbreviation.

Vertex container abbreviations

Container Iterator type Vertex ID type Other Abbrev
std::vector Random access Integral index v
std::deque Random access Integral index d
std::map Bidirectional Ordered key (any operator< type) deduplicated vertex id m
std::unordered_map Forward Hashable key (any with std::hash) deduplicated vertex id u

Edge container abbreviations

Container Iterator type Properties Abbrev
std::vector Random access Cache-friendly, allows duplicates v
std::deque Random access Efficient front/back insertion d
std::forward_list Forward Minimal memory overhead. Edges added to the front. fl
std::list Bidirectional O(1) insertion/removal anywhere. Edges added to the back. l
std::set Bidirectional Sorted, deduplicated target id s
std::unordered_set Forward Hash-based, O(1) avg lookup, deduplicated target id us
std::map Bidirectional Sorted by target_id key, deduplicated target id m
std::unordered_map Forward Hash-based, O(1) avg lookup, deduplicated target id um

Full 27-combination matrix

Each trait struct is in graph::container and has its own header in include/graph/container/traits/.

Trait Vertices Edges Header
vov_graph_traits vector vector traits/vov_graph_traits.hpp
vod_graph_traits vector deque traits/vod_graph_traits.hpp
vofl_graph_traits vector forward_list traits/vofl_graph_traits.hpp
vol_graph_traits vector list traits/vol_graph_traits.hpp
vos_graph_traits vector set traits/vos_graph_traits.hpp
vous_graph_traits vector unordered_set traits/vous_graph_traits.hpp
vom_graph_traits vector map traits/vom_graph_traits.hpp
voum_graph_traits vector unordered_map traits/voum_graph_traits.hpp
dov_graph_traits deque vector traits/dov_graph_traits.hpp
dod_graph_traits deque deque traits/dod_graph_traits.hpp
dofl_graph_traits deque forward_list traits/dofl_graph_traits.hpp
dol_graph_traits deque list traits/dol_graph_traits.hpp
dos_graph_traits deque set traits/dos_graph_traits.hpp
dous_graph_traits deque unordered_set traits/dous_graph_traits.hpp
mov_graph_traits map vector traits/mov_graph_traits.hpp
mod_graph_traits map deque traits/mod_graph_traits.hpp
mofl_graph_traits map forward_list traits/mofl_graph_traits.hpp
mol_graph_traits map list traits/mol_graph_traits.hpp
mos_graph_traits map set traits/mos_graph_traits.hpp
mous_graph_traits map unordered_set traits/mous_graph_traits.hpp
mom_graph_traits map map traits/mom_graph_traits.hpp
uov_graph_traits unordered_map vector traits/uov_graph_traits.hpp
uod_graph_traits unordered_map deque traits/uod_graph_traits.hpp
uofl_graph_traits unordered_map forward_list traits/uofl_graph_traits.hpp
uol_graph_traits unordered_map list traits/uol_graph_traits.hpp
uos_graph_traits unordered_map set traits/uos_graph_traits.hpp
uous_graph_traits unordered_map unordered_set traits/uous_graph_traits.hpp

Common trait parameters

All trait structs share the same template parameters:

template <class EV = void, class VV = void, class GV = void,
          class VId = uint32_t, bool Bidirectional = false>
struct vov_graph_traits { ... };

Each defines:

  • edge_value_type, vertex_value_type, graph_value_type, vertex_id_type
  • static constexpr bool bidirectional
  • edge_type, vertex_type, graph_type
  • vertices_type (e.g., std::vector<vertex_type>)
  • edges_type (e.g., std::vector<edge_type>)

Using non-default traits

#include <graph/container/dynamic_graph.hpp>
#include <graph/container/traits/mofl_graph_traits.hpp>

using namespace graph::container;

// Sparse graph with string vertex IDs, double edge weights
using Traits = mofl_graph_traits<double, std::string, void, std::string>;
using G      = dynamic_adjacency_graph<Traits>;
// Vertices: std::map<std::string, vertex_type>
// Edges:    std::forward_list<edge_type>

Note: Map-based vertex containers (m*, u* traits) require vertices to be explicitly created — they do not auto-extend when edges reference undefined vertex IDs, unlike vector/deque-based traits.

Defining custom traits

You can define your own traits struct to use containers not in the standard library (e.g., Boost, Abseil, or your own). A traits struct must provide exactly the type aliases and constant shown below:

#include <graph/container/dynamic_graph.hpp>
#include <boost/container/flat_map.hpp>
#include <boost/container/small_vector.hpp>

namespace myapp {

// Forward declarations required by dynamic_out_edge / dynamic_vertex / dynamic_graph
using namespace graph::container;

template <class EV = void, class VV = void, class GV = void,
          class VId = uint32_t, bool Bidirectional = false>
struct flat_map_small_vec_traits {
  // --- Required type aliases ---
  using edge_value_type         = EV;
  using vertex_value_type       = VV;
  using graph_value_type        = GV;
  using vertex_id_type          = VId;
  static constexpr bool bidirectional = Bidirectional;

  // --- Edge, vertex, and graph types (always use dynamic_*) ---
  using edge_type   = dynamic_out_edge<EV, VV, GV, VId, Bidirectional,
                                       flat_map_small_vec_traits>;
  using vertex_type = dynamic_vertex<EV, VV, GV, VId, Bidirectional,
                                     flat_map_small_vec_traits>;
  using graph_type  = dynamic_graph<EV, VV, GV, VId, Bidirectional,
                                    flat_map_small_vec_traits>;

  // --- Storage types (your custom containers) ---
  using vertices_type = boost::container::flat_map<VId, vertex_type>;
  using edges_type    = boost::container::small_vector<edge_type, 8>;
};

} // namespace myapp

Container requirements:

Member Container must satisfy
vertices_type std::ranges::forward_range with value_type = vertex_type. For indexed vertex IDs, must also be a std::ranges::sized_range supporting operator[]. For keyed vertex IDs, must support find(key) and end().
edges_type std::ranges::forward_range with value_type = edge_type. Must support insertion (push_back, push_front, insert, or emplace).

Usage:

using Traits = myapp::flat_map_small_vec_traits<double, std::string>;
using G      = graph::container::dynamic_adjacency_graph<Traits>;

G g;
// All CPOs, views, and algorithms work as normal

Tip: Model your traits struct on one of the 27 built-in traits headers in include/graph/container/traits/. The simplest starting point is vov_graph_traits.hpp.

Mutation API

dynamic_graph supports incremental, BGL-style mutation after construction. The add_vertex overloads differ between sequential (v/d) and associative (m/u) vertex containers:

using namespace graph::container;
using G = vov_graph<double, std::string>;   // sequential vertices, EV=double, VV=string
G g;

// Sequential containers: ids are positional; add_vertex appends and returns the new id
auto a = g.add_vertex("Alice");   // returns vertex_id_type 0
auto b = g.add_vertex("Bob");     // returns 1
auto c = g.add_vertex();          // default-constructed value, returns 2

g.add_edge(a, b, 1.5);            // both endpoints must already exist
g.add_edge(a, c);                 // EV default-constructed when value omitted

auto removed = g.remove_edge(a, b);   // returns number of edges removed
g.remove_vertex(c);                   // renumbers higher vertex/edge ids

For associative vertex containers (m* / u* traits) the caller supplies the id (key), and add_vertex returns a bool indicating whether a new vertex was inserted:

using G = mov_graph<double, std::string, void, std::string>;  // map<string, vertex>
G g;

bool inserted = g.add_vertex("alice", "Alice");   // true (new), false if key existed
g.add_vertex("bob", "Bob");
g.add_edge("alice", "bob", 2.0);

g.remove_edge("alice", "bob");
g.remove_vertex("bob");           // remaining keys stay stable (no renumbering)
Operation Sequential (v/d) Associative (m/u)
add_vertex() / add_vertex(val) Appends, returns new id n/a (id required)
add_vertex(id) / add_vertex(id, val) n/a Keyed insert, returns bool
add_edge(u, v) / add_edge(u, v, val) Both endpoints must exist (std::out_of_range otherwise) same
remove_edge(u, v) Returns count removed same
remove_vertex(u) Renumbers higher ids; invalidates descriptors Stable keys; only removed id invalidated

Note: add_edge requires that both vertices already exist — it does not auto-create them. When Bidirectional is true, edge mutations also maintain the matching in-edge lists. After remove_vertex on a sequential container, all existing vertex and edge descriptors are invalidated because ids are renumbered.

2. compressed_graph

#include <graph/container/compressed_graph.hpp>

namespace graph::container {
template <class EV        = void,            // edge value type
          class VV        = void,            // vertex value type
          class GV        = void,            // graph value type
          integral VId    = uint32_t,        // vertex id type
          integral EIndex = uint32_t,        // edge index type
          class Alloc     = std::allocator<VId>>
class compressed_graph;
}

compressed_graph uses CSR (Compressed Sparse Row) format for maximum memory density and cache locality. Vertices and edges cannot be added or removed after construction, but values on them can be modified.

Properties

Property Value
Vertex ID assignment Contiguous (0 .. N-1)
Vertex range Contiguous
Edge range Contiguous per vertex
Partitions Optional (multi-partite support)
Append vertices/edges No

Complexity guarantees

Operation Complexity
Vertex access by ID O(1)
find_vertex(g, uid) O(1)
find_vertex_edge(g, u, vid) O(degree)
num_vertices(g) O(1)
num_edges(g) O(1)
degree(g, u) O(1)
Iterate edges from vertex O(degree)

Memory layout

$$|V| \times (\text{sizeof}(\texttt{EIndex}) + \text{sizeof}(\texttt{VV})) + |E| \times (\text{sizeof}(\texttt{VId}) + \text{sizeof}(\texttt{EV})) + \text{sizeof}(\texttt{GV})$$

When VV, EV, or GV is void, that term contributes zero.

Quick usage

#include <graph/container/compressed_graph.hpp>

using namespace graph::container;

// Construct from an edge list (tuple<source, target, weight>)
std::vector<std::tuple<int,int,double>> edges = {
  {0, 1, 1.5}, {1, 2, 2.0}, {2, 0, 0.5}
};
compressed_graph<double> g(edges, 3);  // 3 vertices, EV=double

// Values on edges are mutable even though structure is not
for (auto&& u : graph::vertices(g)) {
  for (auto&& uv : graph::edges(g, u)) {
    graph::edge_value(g, uv) *= 2.0;
  }
}

Template parameters

Parameter Default Description
EV void Edge value type
VV void Vertex value type
GV void Graph value type
VId uint32_t Vertex ID type (must be integral; size must hold |V|+1)
EIndex uint32_t Edge index type (must be integral; size must hold |E|+1)
Alloc std::allocator<VId> Allocator (rebound for internal containers)

3. undirected_adjacency_list

#include <graph/container/undirected_adjacency_list.hpp>

namespace graph::container {
template <typename EV                                        = void,
          typename VV                                        = void,
          typename GV                                        = void,
          integral VId                                       = uint32_t,
          template <typename V, typename A> class VContainer = std::vector,
          typename Alloc                                     = std::allocator<char>>
class undirected_adjacency_list;
}

Each undirected edge appears in two doubly-linked lists — one at each endpoint. This gives O(1) edge removal from both vertices and efficient iteration of incident edges. Edges are not duplicated, so this is ideal when edge properties need to be changed or when there are many edge properties.

Complexity guarantees

Operation Complexity
Vertex access by ID O(1)
find_vertex(g, uid) O(1)
find_vertex_edge(g, u, vid) O(degree)
Add vertex O(1) amortized
Add edge O(1)
Remove edge O(degree) find + O(1) unlink
Degree query O(1) (cached)
Iterate edges from vertex O(degree)
Iterate all edges O(V + E)

Memory overhead

  • Per vertex: ~24-32 bytes (list head pointers + value)
  • Per edge: ~48-64 bytes (4 list pointers, 2 vertex IDs, value, allocation overhead)

Iteration note

Edge iteration at graph level visits each edge twice (once from each endpoint). Use edges_size() / 2 for the unique edge count.

Template parameters

Parameter Default Description
EV void Edge value type
VV void Vertex value type
GV void Graph value type
VId uint32_t Vertex ID type (integral)
VContainer std::vector Vertex storage container template
Alloc std::allocator<char> Allocator

Mutation API

undirected_adjacency_list is built incrementally with the same BGL-style names as dynamic_graph. Vertex ids are positional indices into the vertex container.

#include <graph/container/undirected_adjacency_list.hpp>
using namespace graph::container;

undirected_adjacency_list<int, std::string> g;   // EV=int (weight), VV=string (name)

auto u = g.add_vertex("Alice");   // returns vertex_iterator
auto v = g.add_vertex("Bob");
auto w = g.add_vertex();          // default-constructed value

g.add_edge(u, v, 42);             // by iterator, with edge value
g.add_edge(0, 2);                 // by id, edge value default-constructed

auto n = g.remove_edge(0u, 1u);   // by id: returns number of edges removed
g.remove_vertex(2u);              // O(V+E): renumbers higher vertex ids
Operation Complexity Notes
add_vertex() / add_vertex(val) O(1) amortized Appends, returns vertex_iterator
add_edge(u, v) / add_edge(u, v, val) O(1) By iterator or by id; with or without edge value
remove_edge(pos) O(1) By edge_iterator; unlinks from both endpoints
remove_edge(uid, vid) O(degree(uid)) Returns count removed; std::out_of_range on invalid id
remove_vertex(uid) O(V + E) Renumbers higher vertex ids; std::out_of_range on invalid id

Iterator invalidation: add_vertex may invalidate vertex iterators if the vertex container reallocates; remove_vertex invalidates them because higher ids are renumbered. add_edge and remove_edge do not invalidate vertex iterators.

4. adjacency_matrix

#include <graph/container/adjacency_matrix.hpp>

namespace graph::container {
template <class EV       = void,       // edge value (weight) type
          class VId      = uint32_t,   // vertex id / index type (integral)
          bool  Directed = true>       // false adds the reciprocal edge too
class adjacency_matrix;
}

adjacency_matrix is a dense container: it owns an n x n block of cells, one per ordered vertex pair. This makes edge-existence and weight lookups O(1) at the cost of O(n²) space, so it suits small or dense graphs and algorithms that probe arbitrary (u, v) pairs (e.g. Floyd–Warshall, transitive closure).

The number of vertices (the matrix order) is fixed at construction. Edges are added by setting cells; storage never reallocates afterwards, so iterators and views stay valid for the matrix's lifetime.

Like the other containers, it satisfies index_adjacency_list, so all CPOs, views, and algorithms work. vertices(g) yields the integral row indices, and out_edges(g, u) lazily scans row u, skipping absent cells.

Properties

Property Value
Vertex ID assignment Contiguous (0 .. order-1)
Vertex range Random access
Edge range per vertex Forward (filtered row view)
Order Fixed at construction
Append vertices No
Append edges Yes (set cells)

Complexity guarantees

Operation Complexity
exists(u, v) / has_edge(u, v) O(1)
operator()(u, v) (weighted, const) O(1)
add_edge(u, v[, val]) O(1)
Iterate out_edges(g, u) O(order) (whole row scanned)
num_edges() / num_vertices() O(1)
Space O(order²)

Quick usage

#include <graph/container/adjacency_matrix.hpp>
using namespace graph::container;

// Unweighted, directed, 4 vertices
adjacency_matrix<> g(4);
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(2, 3);

bool e = g.has_edge(0, 1);          // O(1)
bool e2 = g.exists(0, 1);           // O(1)

// Weighted (double) — value recovered via edge_value CPO or const operator()(u, v)
adjacency_matrix<double> w(3);
w.add_edge(0, 1, 1.5);
const auto& cw = w;
double wt = cw(0, 1);               // 1.5

// Undirected — adds the reciprocal edge automatically
adjacency_matrix<void, std::uint32_t, /*Directed=*/false> u(3);
u.add_edge(0, 1);                   // both (0,1) and (1,0) now present

Construction from an edge range

As with dynamic_graph and compressed_graph, an adjacency_matrix can be built directly from a range of edges plus a projection to copyable_edge_t<VId, EV> ({source_id, target_id [, value]}). The matrix is sized to the supplied order; endpoints are not scanned to grow it, so every projected id must be < order.

#include <graph/container/adjacency_matrix.hpp>
using namespace graph::container;

// Already copyable_edge_t — use std::identity (the default)
std::vector<graph::copyable_edge_t<std::uint32_t>> ee = {{0,1},{0,2},{1,2},{2,3}};
adjacency_matrix<> g(4, ee);

// Project from your own edge type
struct raw_edge { int from, to; double w; };
std::vector<raw_edge> raw = {{0,1,1.5},{0,2,2.5},{1,2,3.5}};
adjacency_matrix<double> wg(3, raw, [](const raw_edge& e) {
  return graph::copyable_edge_t<std::uint32_t, double>{
      static_cast<std::uint32_t>(e.from), static_cast<std::uint32_t>(e.to), e.w};
});

Template parameters

Parameter Default Meaning
EV void Edge value (weight) type; void for an unweighted graph
VId uint32_t Vertex id / index type (must be integral)
Directed true When false, add_edge(u, v) also adds v -> u (symmetric matrix)

C++23 mdspan variant

When compiled as C++23 with <mdspan> available, the header also defines md_adjacency_matrix<EV, VId, Directed>. It has identical concept wiring and owning storage, but additionally exposes the dense presence plane as a 2-D std::mdspan (presence()) and offers natural m(u, v) element access. The mdspan is a view over the owned storage — it never owns the data.

#if defined(__cpp_lib_mdspan)
md_adjacency_matrix<double> g(3);
g.add_edge(0, 1, 2.5);
bool present = g.exists(0, 1);      // true
auto plane   = g.presence();       // std::mdspan<const std::uint8_t, dextents<size_t,2>>
#endif

5. Range-of-Ranges Graphs (No Library Graph Container Required)

You do not need dynamic_graph, compressed_graph, or any library container to use graph-v3. Any range-of-ranges whose elements follow a recognised pattern works directly with all CPOs, views, and algorithms:

#include <graph/graph.hpp>

// A plain vector-of-vectors IS a graph — no wrapper needed
std::vector<std::vector<std::pair<int,double>>> g = {
  {{1, 1.5}, {2, 0.5}},   // vertex 0 → edges to 1 (weight 1.5) and 2 (0.5)
  {{2, 2.0}},              // vertex 1 → edge to 2 (weight 2.0)
  {}                       // vertex 2 → no outgoing edges
};

for (auto&& u : graph::vertices(g)) {
  for (auto&& uv : graph::edges(g, u)) {
    auto vid = graph::target_id(g, uv);
    auto w   = graph::edge_value(g, uv);   // returns pair.second (the double)
  }
}

The library detects the graph structure from the range categories and element types — not from specific container names. Any container satisfying the requirements below will work, including third-party containers (Boost, Abseil, etc.).

Outer range (vertex container) requirements

The outer range holds vertices. Each element represents one vertex; its position or key becomes the vertex ID.

Outer range category Vertex ID type Examples
Random-access + sized Integral index (0 .. N-1) std::vector<…>, std::deque<…>, std::array<…, N>
Associative (pair-valued) Key type std::map<K, …>, std::unordered_map<K, …>

The outer range must be a forward_range. For num_vertices(g) to work, it must also be a sized_range.

When the outer range is an associative container, vertex IDs are keys rather than indices:

std::map<std::string, std::vector<std::pair<std::string, double>>> g = {
  {"A", {{"B", 1.0}, {"C", 2.0}}},
  {"B", {{"C", 0.5}}},
  {"C", {}}
};

for (auto&& u : graph::vertices(g)) {
  auto vid = graph::vertex_id(g, u);        // std::string ("A", "B", "C")
  for (auto&& uv : graph::edges(g, u)) {
    auto tid = graph::target_id(g, uv);     // std::string
    auto w   = graph::edge_value(g, uv);    // double
  }
}
Outer container vertex_id_t<G> find_vertex complexity
std::map<K, …> K O(log V)
std::unordered_map<K, …> K O(1) avg

In a plain range-of-ranges, the "vertex value" returned by vertex_value(g, u) is the inner range itself (the edge list). There is no separate vertex data slot. If you need per-vertex data alongside edges, use dynamic_graph with a vertex value type, or store vertex data in a separate parallel container.

Inner range (edge container) requirements

Each vertex's value must be a forward_range whose elements are the edges leaving that vertex. The element type determines how target_id and edge_value are extracted.

Edge element patterns

The library recognises four edge element patterns, checked in priority order:

1. Simple integral — target ID only

std::vector<std::vector<int>> g = {
  {1, 2},    // vertex 0 → edges to vertices 1 and 2
  {0},       // vertex 1 → edge to vertex 0
  {}
};
auto vid = graph::target_id(g, uv);   // the int value itself
auto ev  = graph::edge_value(g, uv);  // also the int value (same as target_id)
target_id edge_value
The value itself The value itself

Any std::integral type (int, uint32_t, size_t, …).

2. Pair — target ID + one property

std::vector<std::vector<std::pair<int, double>>> g = {
  {{1, 1.5}, {2, 0.5}},
  {{2, 2.0}},
  {}
};
auto vid = graph::target_id(g, uv);   // pair.first
auto w   = graph::edge_value(g, uv);  // pair.second (mutable reference)
target_id edge_value
.first .second

Works with std::pair and any type with .first and .second members. edge_value returns a reference, so the property is mutable in-place.

3. Tuple — target ID + one or more properties

// Two-element tuple (same semantics as pair)
std::vector<std::vector<std::tuple<int, double>>> g = { ... };
auto vid = graph::target_id(g, uv);   // get<0>
auto w   = graph::edge_value(g, uv);  // get<1> (single value reference)

// Three-or-more-element tuple
std::vector<std::vector<std::tuple<int, double, std::string>>> g = { ... };
auto vid = graph::target_id(g, uv);   // get<0>
auto ev  = graph::edge_value(g, uv);  // tuple of references: {get<1>, get<2>, ...}
Elements target_id edge_value
2 get<0> get<1> (single reference)
3+ get<0> forward_as_tuple(get<1>, get<2>, …)

Any type satisfying std::tuple_size (e.g., std::tuple, std::array).

4. Custom struct — user-defined extraction

struct MyEdge {
  int    target;
  double weight;
  // Option A: provide a target_id() member
  int target_id() const { return target; }
};

std::vector<std::vector<MyEdge>> g = { ... };
auto vid = graph::target_id(g, uv);   // calls MyEdge::target_id()
auto ev  = graph::edge_value(g, uv);  // returns MyEdge& (whole struct)
Has target_id() member? target_id edge_value
Yes .target_id() Whole struct reference
No Must provide ADL target_id(g, uv) Whole struct reference

If your struct does not have a target_id() member, provide a free function found by ADL.

source_id(g, uv) — always available

Every edge descriptor stores its source vertex, so source_id(g, uv) works for all range-of-ranges graphs without any extra annotation.

Quick reference

Graph type vertex_id type target_id source edge_value type
vector<vector<int>> size_t value int
vector<vector<pair<int,double>>> size_t .first double&
vector<vector<tuple<int,double>>> size_t get<0> double&
vector<vector<tuple<int,double,string>>> size_t get<0> tuple<double&,string&>
vector<vector<MyEdge>> size_t .target_id() MyEdge&
deque<vector<int>> size_t value int
map<K, vector<pair<K,double>>> K .first double&
vector<set<int>> size_t value (key) int

6. Custom Graphs

If you have an existing graph data structure that does not model a range-of-ranges, you can still use it with all library views and algorithms by overriding the graph CPOs for your type. This gives maximum flexibility — your storage layout, indexing scheme, and memory management remain unchanged while the library operates on them through the CPO interface.

Tip: If you want to filter vertices or edges of an existing graph, or interoperate with Boost.Graph types, see Adaptors for ready-made non-owning wrappers that require no CPO overrides.

Which CPOs to override

At minimum, provide ADL overloads for these core CPOs in your type's namespace:

CPO Signature Purpose
vertices(g) Returns a range of vertices Vertex iteration
edges(g, u) Returns a range of edges for vertex u Edge iteration
target_id(g, uv) Returns the target vertex id of edge uv Edge traversal
vertex_id(g, u) Returns the id of vertex u Vertex identification

Optional CPOs to override for richer functionality:

CPO Purpose
source_id(g, uv) Required by algorithms that need edge source
vertex_value(g, u) Expose vertex properties
edge_value(g, uv) Expose edge properties (weights, labels, etc.)
num_vertices(g) Vertex count (defaults to size(vertices(g)))
find_vertex(g, uid) Sub-linear vertex lookup
find_vertex_edge(g, u, vid) Sub-linear edge lookup

Example

namespace mylib {

struct my_graph {
  struct vertex { int id; std::string name; std::vector<int> neighbors; };
  std::vector<vertex> verts;
};

// Core CPOs — found via ADL
auto vertices(const my_graph& g) { return std::ranges::ref_view(g.verts); }
auto edges(const my_graph& g, const my_graph::vertex& u) {
  return std::ranges::ref_view(u.neighbors);
}
auto target_id(const my_graph&, int tid) { return tid; }
auto vertex_id(const my_graph&, const my_graph::vertex& u) { return u.id; }

// Optional: expose vertex value
auto vertex_value(const my_graph&, const my_graph::vertex& u) {
  return std::string_view(u.name);
}

} // namespace mylib

With these overloads in place, my_graph works directly with library views (vertices_breadth_first_search, edges_depth_first_search, etc.) and algorithms (dijkstra_shortest_paths, bellman_ford_shortest_paths, etc.).

See CPO Implementation Guide for the full CPO resolution order and advanced customization patterns.

7. Container Selection Guide

              ┌─ Already have data in          → range-of-ranges
              │   standard containers?            (zero-copy, no conversion)
              │
              ├─ Have an existing graph         → custom graph
              │   data structure?                  (override CPOs for full control)
              │
              ├─ Need undirected edges          → undirected_adjacency_list
              │   with O(1) removal or
              │   mutable edge properties?
Start ────────┤
              │
              ├─ Small or dense graph with      → adjacency_matrix
              │   O(1) (u,v) existence queries?    (O(n²) space, fixed order)
              │
              ├─ Graph is read-only             → compressed_graph
              │   after construction?              (smallest memory, best cache)
              │
              └─ Need mutable vertices/edges?   → dynamic_graph
                                                   (pick traits for your needs)

When compressed_graph or dynamic_graph is used to represent an undirected graph, edges must be duplicated (e.g. edges A/B and B/A for vertices A and B). Properties must also be duplicated, or handled in a way that avoids duplication (e.g. a std::shared_ptr to a property struct), if they are mutable.

Criterion dynamic_graph compressed_graph undirected_adjacency_list adjacency_matrix range-of-ranges
Add/remove vertices Yes No Yes No (fixed order) Depends on outer container
Add/remove edges Yes No Yes (O(1) remove) Add only (set cells) Depends on inner container
Directed Yes Yes No (undirected) Yes Yes
Undirected Yes (duplicated edges) Yes (duplicated edges) Yes Yes (Directed=false) Yes (duplicated edges)
Mutable Properties Directed (Yes), Undirected (No) Directed (Yes), Undirected (No) Yes Yes (cells) Directed (Yes), Undirected (No); your data
Memory efficiency Medium Best (CSR) Highest overhead O(n²) (dense) Zero overhead (existing data)
Cache locality Depends on trait Excellent Poor (linked-list) Excellent (contiguous) Depends on containers used
Multi-partite No Yes No No No
Container flexibility 27 trait combos Fixed (CSR) Configurable random access vertex container Fixed (dense) Any forward_range of forward_ranges

Custom graphs. See Section 6 (Custom Graphs) for how to use your own graph data structure with all library views and algorithms by overriding graph CPOs.

See Also