Creating a Graph

There are several ways to construct a graph in BGL. This page shows the most common approaches.

Method 1: Create Empty Graph, Then Add Edges

The simplest approach is to create a graph with a specified number of vertices, then add edges one at a time:

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

typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

int main()
{
    // Create graph with 5 vertices (numbered 0-4)
    Graph g(5);
    
    // Add edges using add_edge(source, target, graph)
    add_edge(0, 1, g);
    add_edge(0, 3, g);
    add_edge(2, 0, g);
    add_edge(3, 2, g);
    add_edge(2, 4, g);
    add_edge(1, 3, g);
    add_edge(3, 4, g);
    
    return 0;
}

You can also use enums to make vertex labels more readable:

// Make convenient labels for the vertices
enum { A, B, C, D, E, N };
const int num_vertices = N;

// Create graph
Graph g(num_vertices);

// Add edges using named vertices
add_edge(A, B, g);
add_edge(A, D, g);
add_edge(C, A, g);
add_edge(D, C, g);
add_edge(C, E, g);
add_edge(B, D, g);
add_edge(D, E, g);

Method 2: Using an Edge Array

For clarity, you can define all edges upfront in an array, then add them in a loop:

#include <utility>  // for std::pair

typedef std::pair<int, int> Edge;

Edge edge_array[] = {
    Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
    Edge(C,E), Edge(B,D), Edge(D,E)
};
const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

// Create graph
Graph g(num_vertices);

// Add all edges
for (int i = 0; i < num_edges; ++i)
    add_edge(edge_array[i].first, edge_array[i].second, g);

Method 3: Edge Iterator Constructor (Most Efficient)

The most efficient way to construct a graph is using the edge iterator constructor. This builds the graph directly from an edge list without repeated calls to add_edge():

Edge edge_array[] = {
    Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
    Edge(C,E), Edge(B,D), Edge(D,E)
};

// Pointers can be used as iterators
Graph g(edge_array, 
        edge_array + sizeof(edge_array) / sizeof(Edge), 
        num_vertices);

Why is this faster? The constructor can allocate all memory upfront and build the data structure in one pass, rather than potentially reallocating storage as edges are added one-by-one.

Method 4: Reading from a File

BGL provides functions to read graphs from various file formats:

#include <boost/graph/graphml.hpp>
#include <fstream>

// Read from GraphML file
std::ifstream infile("graph.graphml");
Graph g;
dynamic_properties dp;
read_graphml(infile, g, dp);

See the Graph I/O section for more details on file formats.

Method 5: Dynamic Vertex Addition

Instead of creating a graph with a fixed number of vertices, you can add vertices dynamically:

Graph g;  // Empty graph

// add_vertex() returns a vertex descriptor
Graph::vertex_descriptor v0 = add_vertex(g);
Graph::vertex_descriptor v1 = add_vertex(g);
Graph::vertex_descriptor v2 = add_vertex(g);
Graph::vertex_descriptor v3 = add_vertex(g);
Graph::vertex_descriptor v4 = add_vertex(g);

// Add edges using vertex descriptors
add_edge(v0, v1, g);
add_edge(v0, v3, g);
add_edge(v2, v0, g);
// ... etc

Note: When using vecS for VertexList, vertex descriptors are just integers (0, 1, 2, ...). With other selectors like listS, descriptors are opaque handles that remain valid even when vertices are removed.

Creating Graphs with Properties

You can attach data to vertices and edges during construction. For example:

// Define graph with edge weights
typedef adjacency_list<vecS, vecS, directedS,
                       no_property,
                       property<edge_weight_t, int> > WeightedGraph;

// Edge with weight
typedef std::pair<int, int> E;
struct weighted_edge {
    E edge;
    int weight;
};

weighted_edge edges[] = {
    {{0,1}, 5},
    {{0,2}, 3},
    {{1,3}, 2},
    {{2,3}, 7}
};

// Extract edges and weights
const int n_edges = sizeof(edges) / sizeof(weighted_edge);
E edge_array[n_edges];
int weights[n_edges];

for (int i = 0; i < n_edges; ++i) {
    edge_array[i] = edges[i].edge;
    weights[i] = edges[i].weight;
}

// Create graph with weighted edges
WeightedGraph g(edge_array, edge_array + n_edges, weights, 4);

For more on properties, see Attaching Data to Graphs.

Summary

Method	Best For	Performance
add_edge() in loop	Simple cases, small graphs	Good
Edge iterator constructor	Known edge list, larger graphs	Best
add_vertex() dynamically	Unknown number of vertices	Good (with listS)
Read from file	External data sources	Varies