This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

Graph Interface Primitives

What is a graph?

Formally, a graph is a pair G = (V, E) where V is a set of vertices and E is a set of edges. Each edge is a pair (u, v) with u, v in V.

  • In a directed graph, edges are ordered pairs: the edge (u, v) goes from its source vertex u to its target vertex v.

  • In an undirected graph, edges are unordered pairs and connect both vertices in either direction.

The terms vertex, edge, source, target, and the directed vs. undirected distinction map directly onto the operations listed below.

For a fuller introduction (degrees, paths, cycles, planarity), see Graph Theory Review.

All BGL graph types share a common set of free functions for accessing and modifying the graph structure. These functions are how algorithms interact with graphs, regardless of the underlying data structure.

#include <boost/graph/adjacency_list.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS>;

int main() {
    Graph g(4);
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 3, g);

    for (auto v : make_iterator_range(vertices(g))) {
        for (auto e : make_iterator_range(out_edges(v, g))) {
            std::cout << source(e, g) << " -> " << target(e, g) << "\n";
        }
    }
}
0 -> 1
1 -> 2
2 -> 3

Traversal

Function Returns Concept

vertices(g)

Pair of vertex iterators (all vertices)

VertexListGraph

edges(g)

Pair of edge iterators (all edges)

EdgeListGraph

out_edges(v, g)

Pair of out-edge iterators

IncidenceGraph

in_edges(v, g)

Pair of in-edge iterators

BidirectionalGraph

adjacent_vertices(v, g)

Pair of adjacency iterators

AdjacencyGraph
All pairs can be used with make_iterator_range for range-based for loops (see example above).

Edge access

Function Returns Concept

source(e, g)

Source vertex of edge e

IncidenceGraph

target(e, g)

Target vertex of edge e

IncidenceGraph

edge(u, v, g)

Pair of (edge_descriptor, bool). Bool is true if the edge exists.

AdjacencyMatrix

 
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS>;

int main() {
    Graph g(3);
    add_edge(0, 1, g);

    auto result = edge(0, 1, g);       // pair of (edge_descriptor, bool)
    if (result.second) {
        std::cout << source(result.first, g) << " -> " << target(result.first, g) << "\n";
    }
}
0 -> 1

Counts

Function Returns Concept

num_vertices(g)

Number of vertices

VertexListGraph

num_edges(g)

Number of edges

EdgeListGraph

out_degree(v, g)

Number of out-edges of vertex v

IncidenceGraph

in_degree(v, g)

Number of in-edges of vertex v

BidirectionalGraph

degree(v, g)

out_degree + in_degree

BidirectionalGraph

 
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

using namespace boost;
using Graph = adjacency_list<vecS, vecS, bidirectionalS>;

int main() {
    Graph g(3);
    add_edge(0, 1, g);
    add_edge(2, 1, g);

    std::cout << "num_vertices: " << num_vertices(g) << "\n";
    std::cout << "num_edges:    " << num_edges(g) << "\n";
    std::cout << "out_degree(0): " << out_degree(0, g) << "\n";
    std::cout << "in_degree(1):  " << in_degree(1, g) << "\n";
    std::cout << "degree(1):     " << degree(1, g) << "\n";
}
num_vertices: 3
num_edges:    2
out_degree(0): 1
in_degree(1):  2
degree(1):     2

Mutation

Function Effect Concept

add_vertex(g)

Add a vertex, return its descriptor

MutableGraph

remove_vertex(v, g)

Remove vertex v and all incident edges

MutableGraph

add_edge(u, v, g)

Add edge from u to v, return pair (descriptor, bool)

MutableGraph

remove_edge(u, v, g)

Remove edge(s) between u and v

MutableGraph

remove_edge(e, g)

Remove specific edge e

MutableGraph

clear_vertex(v, g)

Remove all edges incident to v (vertex remains)

MutableGraph
With adjacency_list<vecS, vecS, …​>, remove_vertex() invalidates all vertex descriptors after the removed vertex. See Graph Data Structures for details. 
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS>;

int main() {
    Graph g(2);
    add_edge(0, 1, g);

    auto v = add_vertex(g);
    add_edge(v, vertex(0, g), g);
    clear_vertex(v, g);    // remove all edges of v
    remove_vertex(v, g);   // remove v itself

    std::cout << "vertices: " << num_vertices(g) << "\n";
}
vertices: 2

Property access

Function Returns

get(&Struct::member, g)

Property map for bundled property member

get(map, key)

Value of key in property map map

put(map, key, value)

Set value of key in property map map

g[v] or g[e]

Direct reference to bundled property struct of vertex v or edge e

get(tag, g)

Property map for internal property tag (legacy, prefer bundled properties)

 
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
#include <string>

using namespace boost;

struct City { std::string name; };
struct Road { double km; };
using Graph = adjacency_list<vecS, vecS, directedS, City, Road>;

int main() {
    Graph g(2);
    add_edge(0, 1, Road{460.0}, g);

    g[0].name = "Paris";                        // direct struct access
    auto km = get(&Road::km, g);                // property map from bundled member
    std::cout << get(km, edge(0, 1, g).first);  // read through property map
}
460

Types

Obtained via graph_traits<Graph>:

Type Description

vertex_descriptor

Handle to a vertex. Opaque type, do not assume it is an integer.

edge_descriptor

Handle to an edge. Contains source and target information.

vertex_iterator

Iterator over all vertices.

edge_iterator

Iterator over all edges.

out_edge_iterator

Iterator over the out-edges of a vertex.

in_edge_iterator

Iterator over the in-edges of a vertex (requires bidirectionalS).

adjacency_iterator

Iterator over the adjacent vertices of a vertex.

vertices_size_type

Unsigned integer type for vertex counts.

edges_size_type

Unsigned integer type for edge counts.

degree_size_type

Unsigned integer type for vertex degree.

See also

Edit this Page