Running Graph Algorithms

BGL provides over 80 graph algorithms covering common graph problems. This page shows you how to use them effectively.

Quick Example: Dijkstra's Shortest Path

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <vector>

using namespace boost;

int main()
{
    // Create weighted graph
    typedef adjacency_list<vecS, vecS, directedS,
        no_property,
        property<edge_weight_t, int> > Graph;
    
    typedef std::pair<int, int> Edge;
    Edge edges[] = {Edge(0,1), Edge(0,2), Edge(1,3), Edge(2,3)};
    int weights[] = {5, 3, 2, 7};
    
    Graph g(edges, edges + 4, weights, 4);
    
    // Storage for results
    std::vector<int> distances(num_vertices(g));
    std::vector<graph_traits<Graph>::vertex_descriptor> predecessors(num_vertices(g));
    
    // Run Dijkstra from vertex 0
    dijkstra_shortest_paths(g, 0,
        distance_map(&distances[0])
        .predecessor_map(&predecessors[0]));
    
    // Print results
    for (int i = 0; i < distances.size(); ++i) {
        std::cout << "Distance to " << i << ": " << distances[i] << "\n";
    }
    
    return 0;
}

Common Algorithm Categories

Category	Examples
Search	breadth_first_search, depth_first_search, A*
Shortest Paths	dijkstra_shortest_paths, bellman_ford_shortest_paths, floyd_warshall_all_pairs_shortest_paths
Minimum Spanning Tree	kruskal_minimum_spanning_tree, prim_minimum_spanning_tree
Connected Components	connected_components, strongly_connected_components, biconnected_components
Maximum Flow	push_relabel_max_flow, edmonds_karp_max_flow, boykov_kolmogorov_max_flow
Matching	maximum_weighted_matching, max_cardinality_matching
Centrality	betweenness_centrality, closeness_centrality
Topological Sort	topological_sort, dag_shortest_paths

Using Named Parameters

Most BGL algorithms use named parameters for flexibility. This allows you to specify only the parameters you need:

// Basic call - uses default parameters
dijkstra_shortest_paths(g, start_vertex);

// With distance map
dijkstra_shortest_paths(g, start_vertex,
    distance_map(&distances[0]));

// With multiple parameters  
dijkstra_shortest_paths(g, start_vertex,
    distance_map(&distances[0])
    .predecessor_map(&predecessors[0])
    .weight_map(get(edge_weight, g)));

Parameters are chained using the . operator.

Example: Breadth-First Search

#include <boost/graph/breadth_first_search.hpp>
#include <vector>

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

int main()
{
    Graph g(5);
    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(1, 3, g);
    add_edge(2, 4, g);
    
    // Storage for BFS state
    std::vector<default_color_type> colors(num_vertices(g));
    std::vector<int> distances(num_vertices(g));
    std::vector<graph_traits<Graph>::vertex_descriptor> predecessors(num_vertices(g));
    
    // Run BFS from vertex 0
    breadth_first_search(g, 0,
        visitor(make_bfs_visitor(
            std::make_pair(record_distances(&distances[0], on_tree_edge()),
            record_predecessors(&predecessors[0], on_tree_edge()))))
        .color_map(&colors[0]));
    
    return 0;
}

Example: Minimum Spanning Tree

#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <vector>

typedef adjacency_list<vecS, vecS, undirectedS,
    no_property,
    property<edge_weight_t, int> > Graph;

int main()
{
    typedef std::pair<int, int> Edge;
    Edge edges[] = {
        Edge(0,1), Edge(0,3), Edge(1,2),
        Edge(1,3), Edge(2,3), Edge(3,4)
    };
    int weights[] = {1, 4, 2, 5, 3, 7};
    
    Graph g(edges, edges + 6, weights, 5);
    
    // Storage for MST edges
    std::vector<graph_traits<Graph>::edge_descriptor> mst_edges;
    
    // Compute MST
    kruskal_minimum_spanning_tree(g, std::back_inserter(mst_edges));
    
    // Print MST
    std::cout << "MST edges:\n";
    for (auto e : mst_edges) {
        std::cout << "(" << source(e, g) << "," 
                  << target(e, g) << ")\n";
    }
    
    return 0;
}

Example: Connected Components

#include <boost/graph/connected_components.hpp>
#include <vector>

typedef adjacency_list<vecS, vecS, undirectedS> Graph;

int main()
{
    Graph g(7);
    // Create three components
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(3, 4, g);
    add_edge(5, 6, g);
    
    std::vector<int> component(num_vertices(g));
    int num_components = connected_components(g, &component[0]);
    
    std::cout << "Number of components: " << num_components << "\n";
    for (int i = 0; i < component.size(); ++i) {
        std::cout << "Vertex " << i << " in component " 
                  << component[i] << "\n";
    }
    
    return 0;
}

Example: Topological Sort

#include <boost/graph/topological_sort.hpp>
#include <list>

typedef adjacency_list<vecS, vecS, directedS> Graph;

int main()
{
    Graph g(6);
    // Dependencies: 0<-1, 0<-2, 1<-3, 2<-3, 3<-4, 4<-5
    add_edge(1, 0, g);
    add_edge(2, 0, g);
    add_edge(3, 1, g);
    add_edge(3, 2, g);
    add_edge(4, 3, g);
    add_edge(5, 4, g);
    
    std::list<int> sorted_vertices;
    topological_sort(g, std::front_inserter(sorted_vertices));
    
    std::cout << "Topological order: ";
    for (auto v : sorted_vertices) {
        std::cout << v << " ";
    }
    std::cout << "\n";
    
    return 0;
}

Using Visitors for Custom Behavior

Visitors let you customize algorithm behavior by providing callbacks at specific points:

#include <boost/graph/depth_first_search.hpp>

// Custom visitor to count back edges
struct cycle_detector : public dfs_visitor<>
{
    cycle_detector(bool& has_cycle) : m_has_cycle(has_cycle) {}
    
    template <class Edge, class Graph>
    void back_edge(Edge, Graph&) {
        m_has_cycle = true;
    }
    
    bool& m_has_cycle;
};

int main()
{
    Graph g(4);
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 3, g);
    add_edge(3, 1, g);  // Creates a cycle
    
    bool has_cycle = false;
    depth_first_search(g, visitor(cycle_detector(has_cycle)));
    
    std::cout << (has_cycle ? "Graph has cycles" : "Graph is acyclic") << "\n";
    
    return 0;
}

Property Maps in Algorithms

Most algorithms work with property maps to access graph data:

// Internal property map (built into graph)
auto weight_map = get(edge_weight, g);
dijkstra_shortest_paths(g, start, weight_map(weight_map));

// External property map (separate storage)
std::vector<int> weights(num_edges(g));
auto weight_map = make_iterator_property_map(weights.begin(), get(edge_index, g));
dijkstra_shortest_paths(g, start, weight_map(weight_map));

Common Patterns

Pattern: Recording Algorithm Results

std::vector<int> distances(num_vertices(g));
std::vector<Vertex> predecessors(num_vertices(g));

dijkstra_shortest_paths(g, start,
    distance_map(&distances[0])
    .predecessor_map(&predecessors[0]));

// Reconstruct path from start to target
std::vector<Vertex> path;
Vertex current = target;
while (current != start) {
    path.push_back(current);
    current = predecessors[current];
}
path.push_back(start);
std::reverse(path.begin(), path.end());

Pattern: Checking Preconditions

// Check if graph is DAG before topological sort
bool has_cycle = false;
depth_first_search(g, visitor(cycle_detector(has_cycle)));

if (!has_cycle) {
    topological_sort(g, std::front_inserter(result));
} else {
    std::cerr << "Cannot sort: graph has cycles\n";
}

Algorithm Reference by Problem

Problem	Algorithm
Find shortest path	dijkstra_shortest_paths
Shortest paths with negative weights	bellman_ford_shortest_paths
All pairs shortest paths	floyd_warshall_all_pairs_shortest_paths
Find minimum spanning tree	kruskal_minimum_spanning_tree
Maximum network flow	push_relabel_max_flow
Detect cycles	depth_first_search + visitor
Find connected components	connected_components
Task scheduling order	topological_sort
Find bridges/articulation points	biconnected_components

For a complete list of algorithms, see the Table of Contents under the Algorithms section.