Boost Graph Library (BGL) Skill

Graph Representation Selection

adjacency_list (primary BGL graph class)

#include <boost/graph/adjacency_list.hpp>
using namespace boost;

// Template parameters:
// adjacency_list<OutEdgeList, VertexList, Directed,
//                VertexProperties, EdgeProperties, GraphProperties>

// Directed graph with vertex and edge properties
typedef adjacency_list<
    vecS,          // OutEdgeList: vector (fast traversal, allows parallel edges)
    vecS,          // VertexList: vector (O(1) access by index)
    directedS,     // or undirectedS, bidirectionalS
    property<vertex_name_t, std::string>,       // vertex property
    property<edge_weight_t, double>             // edge property
> Graph;

// Container options for EdgeList/VertexList:
// vecS    → vector: fast O(1) access, allows parallel edges
// listS   → list: fast insert/remove, no parallel edge removal
// setS    → set: no parallel edges, O(log n) insert
// multisetS → multiset: allows parallel edges, O(log n)

adjacency_matrix (dense graphs)

#include <boost/graph/adjacency_matrix.hpp>

// Use when |E| ≈ |V|²
// O(1) edge existence check: edge(u, v, g).second
typedef adjacency_matrix<
    directedS,
    property<vertex_name_t, std::string>,
    property<edge_weight_t, double>
> DenseGraph;

Directed Options

Type	Out-edges	In-edges	Use when
directedS	Yes	No	One-way traversal only
undirectedS	Yes (both dirs)	N/A	Undirected graphs
bidirectionalS	Yes	Yes	Need in_edges() access

---

Building a Graph

typedef adjacency_list<vecS, vecS, directedS> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;

Graph g;

// Add vertices
Vertex a = add_vertex(g);
Vertex b = add_vertex(g);
Vertex c = add_vertex(g);

// Add edges
add_edge(a, b, g);
add_edge(b, c, g);
add_edge(a, c, g);

// Query
num_vertices(g);        // vertex count
num_edges(g);           // edge count

// Iteration
auto [vi, vi_end] = vertices(g);
for (; vi != vi_end; ++vi) { /* *vi is a Vertex */ }

auto [ei, ei_end] = edges(g);
for (; ei != ei_end; ++ei) {
    source(*ei, g);  target(*ei, g);
}

auto [oi, oi_end] = out_edges(a, g);  // out-edges of vertex a

---

Property Maps

// Internal properties (stored in graph)
typedef adjacency_list<vecS, vecS, directedS,
    property<vertex_name_t, std::string>,
    property<edge_weight_t, double>> Graph;

Graph g;
auto name_map   = get(vertex_name,   g);
auto weight_map = get(edge_weight,   g);

Vertex v = add_vertex(g);
put(name_map, v, "router-A");

auto [e, ok] = add_edge(a, b, g);
put(weight_map, e, 1.5);

// Get value
std::string n = get(name_map, v);
double w      = get(weight_map, e);

// External property maps (for algorithms that need scratch space)
std::vector<default_color_type> color(num_vertices(g));
auto color_map = make_iterator_property_map(color.begin(), get(vertex_index, g));

---

Graph Algorithms

Breadth-First Search (BFS)

#include <boost/graph/breadth_first_search.hpp>

// Simple usage
std::vector<Vertex> pred(num_vertices(g));
breadth_first_search(g, source_vertex,
    visitor(make_bfs_visitor(record_predecessors(&pred[0], on_tree_edge()))));

// Custom visitor
struct MyBFSVisitor : public default_bfs_visitor {
    template <typename V, typename G>
    void discover_vertex(V u, const G&) const {
        std::cout << u << '\n';
    }
    template <typename E, typename G>
    void examine_edge(E e, const G& g) const { /* ... */ }
};
breadth_first_search(g, start, visitor(MyBFSVisitor{}));

Depth-First Search (DFS)

#include <boost/graph/depth_first_search.hpp>

struct MyDFSVisitor : public default_dfs_visitor {
    template <typename V, typename G>
    void finish_vertex(V u, const G&) const {
        // Called when all descendants processed — use for topological sort
        result.push_back(u);
    }
};
depth_first_search(g, visitor(MyDFSVisitor{}));

Topological Sort

#include <boost/graph/topological_sort.hpp>

std::deque<Vertex> order;
topological_sort(g, std::front_inserter(order));
// order is now in topological order (u before v if edge u→v)
// Throws boost::not_a_dag if graph has cycles

Shortest Paths (Dijkstra)

#include <boost/graph/dijkstra_shortest_paths.hpp>

std::vector<double> dist(num_vertices(g));
std::vector<Vertex> pred(num_vertices(g));

dijkstra_shortest_paths(g, source_v,
    predecessor_map(make_iterator_property_map(pred.begin(), get(vertex_index, g)))
    .distance_map(make_iterator_property_map(dist.begin(), get(vertex_index, g)))
    .weight_map(get(edge_weight, g)));

// Reconstruct path from source to target:
Vertex cur = target_v;
while (cur != source_v) {
    path.push_back(cur);
    cur = pred[cur];
}
path.push_back(source_v);
std::reverse(path.begin(), path.end());

Bellman-Ford (negative weights)

#include <boost/graph/bellman_ford_shortest_paths.hpp>

bool no_neg_cycle = bellman_ford_shortest_paths(
    g, num_vertices(g),
    weight_map(get(edge_weight, g))
    .predecessor_map(&pred[0])
    .distance_map(&dist[0]));

Minimum Spanning Tree (Kruskal)

#include <boost/graph/kruskal_min_spanning_tree.hpp>

std::vector<Edge> mst_edges;
kruskal_minimum_spanning_tree(g, std::back_inserter(mst_edges),
    weight_map(get(edge_weight, g)));

---

Visitor Event Points

BFS Event	DFS Event	When triggered
initialize_vertex	initialize_vertex	Before search
discover_vertex	start_vertex	First visit to vertex
examine_vertex	discover_vertex	Popped from queue
examine_edge	examine_edge	Edge about to be explored
tree_edge	tree_edge	Edge in search tree
non_tree_edge	back_edge	Back edge (DFS cycle detection)
—	finish_vertex	All descendants done

---

Generic Programming Concepts (BGL Design Philosophy)

Concept vs Inheritance

OOP polymorphism (virtual functions):
+ Run-time dispatch
- Extra pointer dereference → cannot inline → slower for fine-grained ops
- Binary method problem (operator== between derived types requires downcast)

Generic programming (templates / concepts):
+ Compile-time dispatch → inlinable → zero overhead
+ No binary method problem — types need not inherit from base
+ Any type satisfying the requirements works (structural, not nominal)
- Larger binary (template instantiation per type)
- Errors harder to read (before C++20 concepts)

Concept → Model pattern

// A concept is a set of requirements documented/enforced:
// VertexListGraph concept requires: vertices(g), num_vertices(g), etc.

// Any type that satisfies these requirements is a "model" of the concept:
// adjacency_list models VertexListGraph
// std::vector<std::list<int>> models VertexListGraph (via adaptor)
// LEDA Graph models VertexListGraph (via adaptor functions)

Traits Classes

// Access associated types for any graph type G:
graph_traits<G>::vertex_descriptor    // type of vertex handle
graph_traits<G>::edge_descriptor      // type of edge handle
graph_traits<G>::vertex_iterator      // type of vertex iterator
graph_traits<G>::edge_iterator        // type of edge iterator
graph_traits<G>::out_edge_iterator    // type of out-edge iterator
graph_traits<G>::directed_category    // directed_tag or undirected_tag
graph_traits<G>::edges_size_type      // integer type for edge count

---

Algorithm Selection Guide

Problem	Algorithm	Header
Shortest paths (non-negative weights)	dijkstra_shortest_paths	dijkstra_shortest_paths.hpp
Shortest paths (negative weights)	bellman_ford_shortest_paths	bellman_ford_shortest_paths.hpp
All-pairs shortest paths	johnson_all_pairs_shortest_paths	johnson_all_pairs_shortest_paths.hpp
Minimum spanning tree	kruskal_minimum_spanning_tree or prim_minimum_spanning_tree	kruskal.hpp / prim.hpp
Topological ordering	topological_sort	topological_sort.hpp
Connected components	connected_components	connected_components.hpp
Strongly connected components	strong_components	strong_components.hpp
Cycle detection	DFS visitor detecting back_edge	depth_first_search.hpp
Reachability	BFS from source, check color	breadth_first_search.hpp