Attaching Data to Graphs

Real-world graphs usually need to store data on vertices and edges—for example, vertex names, edge weights, colors, coordinates, etc. BGL provides flexible mechanisms for attaching properties to graphs.

Two Approaches: Internal vs External Properties

BGL supports two ways to store properties:

Internal properties: Stored inside the graph object itself. Best when properties exist for the graph's entire lifetime (e.g., edge weights, vertex names).
External properties: Stored separately from the graph. Best for temporary algorithm state (e.g., vertex colors during search, distances during shortest path calculation).

Both approaches use the same property map interface, so algorithms work with either type transparently.

Internal Properties: The Basics

To add internal properties, use the property template in the graph type definition:

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

using namespace boost;

// Graph with edge weights
typedef adjacency_list<
    vecS,                              // OutEdgeList
    vecS,                              // VertexList
    directedS,                         // Directed
    no_property,                       // VertexProperties
    property<edge_weight_t, int>       // EdgeProperties (weight)
> WeightedGraph;

The template parameters for property are:

Property tag: Identifies the property type (e.g., edge_weight_t, vertex_name_t)
Value type: The data type of the property (e.g., int, std::string, double)

Predefined Property Tags

BGL provides many standard property tags:

Tag	Typical Use	Common Type
`edge_weight_t`	Edge weights/costs	`int`, `double`
`edge_capacity_t`	Flow capacity	`int`, `double`
`vertex_name_t`	Vertex labels	`std::string`
`vertex_color_t`	Search state	`default_color_type`
`vertex_distance_t`	Shortest path distance	`int`, `double`
`vertex_index_t`	Vertex numbering	`int`
`edge_index_t`	Edge numbering	`int`

See Internal Properties for the complete list.

Setting Property Values During Construction

You can set edge properties when creating a graph:

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

// Define edges
Edge edges[] = {
    Edge(0, 2), Edge(1, 1), Edge(1, 3),
    Edge(2, 1), Edge(2, 3), Edge(3, 4)
};

// Define corresponding weights
int weights[] = {1, 2, 1, 7, 3, 1};

const int num_vertices = 5;
const int num_edges = sizeof(edges) / sizeof(Edge);

// Create graph with edge weights
WeightedGraph g(edges, edges + num_edges, weights, num_vertices);

The weights array is passed to the constructor and automatically assigned to edges in order.

Accessing Internal Properties

Use property maps to access internal properties:

// Get the edge weight property map
typedef property_map<WeightedGraph, edge_weight_t>::type WeightMap;
WeightMap weight_map = get(edge_weight, g);

// Access edge weights
graph_traits<WeightedGraph>::edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
    std::cout << "Edge (" << source(*ei, g) << "," 
              << target(*ei, g) << ") weight: "
              << weight_map[*ei] << std::endl;
}

Or use the shorthand get() and put() functions:

// Read a property
int w = get(weight_map, edge);

// Write a property  
put(weight_map, edge, 42);

// Or use operator[]
weight_map[edge] = 42;

Multiple Properties

Chain multiple property templates to add multiple properties:

// Graph with edge weight AND edge capacity
typedef adjacency_list<
    vecS, vecS, directedS,
    no_property,
    property<edge_weight_t, int,
        property<edge_capacity_t, int> >
> FlowGraph;

// Access each property separately
typedef property_map<FlowGraph, edge_weight_t>::type WeightMap;
typedef property_map<FlowGraph, edge_capacity_t>::type CapacityMap;

WeightMap weights = get(edge_weight, g);
CapacityMap capacities = get(edge_capacity, g);

Vertex Properties

Vertex properties work the same way:

// Graph with vertex names and edge weights
typedef adjacency_list<
    vecS, vecS, directedS,
    property<vertex_name_t, std::string>,      // Vertex property
    property<edge_weight_t, double>            // Edge property
> NamedGraph;

NamedGraph g(5);

// Get vertex name property map
typedef property_map<NamedGraph, vertex_name_t>::type NameMap;
NameMap name_map = get(vertex_name, g);

// Set vertex names
name_map[0] = "Alice";
name_map[1] = "Bob";
name_map[2] = "Charlie";

// Print vertex names
graph_traits<NamedGraph>::vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    std::cout << "Vertex " << *vi << ": " 
              << name_map[*vi] << std::endl;
}

External Properties: Using std::vector

For temporary algorithm state, external properties are often simpler:

typedef adjacency_list<vecS, vecS, directedS> Graph;
Graph g(5);
// ... add edges ...

// External property: vertex distances (for Dijkstra's algorithm)
std::vector<int> distances(num_vertices(g));

// std::vector iterators can be used as property maps
dijkstra_shortest_paths(g, source_vertex,
    distance_map(&distances[0]));  // Pass vector as property map

// Access results
for (int i = 0; i < distances.size(); ++i) {
    std::cout << "Distance to vertex " << i 
              << ": " << distances[i] << std::endl;
}

External Properties: Using std::map

When using listS for vertices (where descriptors aren't integers), use std::map:

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

Graph g;
// ... build graph ...

// Map from vertex descriptor to color
std::map<Vertex, default_color_type> color_map;

// Use associative_property_map wrapper
auto color = make_assoc_property_map(color_map);

// Use in algorithm
breadth_first_search(g, start_vertex,
    visitor(make_bfs_visitor(/* ... */))
    .color_map(color));

Custom Property Types

You can attach custom structs or classes as properties:

struct VertexData {
    std::string name;
    double x, y;  // Coordinates
    int importance;
};

struct EdgeData {
    double weight;
    std::string label;
};

typedef adjacency_list<
    vecS, vecS, directedS,
    VertexData,    // Custom vertex property
    EdgeData       // Custom edge property
> CustomGraph;

CustomGraph g(3);

// Access using [] operator on graph
g[0].name = "Node A";
g[0].x = 10.5;
g[0].y = 20.3;

// For edges, use edge descriptor
auto e = add_edge(0, 1, g).first;
g[e].weight = 3.14;
g[e].label = "important edge";

When to Use Internal vs External Properties

Use Internal Properties When...	Use External Properties When...
Property is intrinsic to the graph (weights, names)	Property is temporary algorithm state (colors, distances)
Property lifetime matches graph lifetime	Multiple algorithms need different property sets
You want to save/load properties with the graph	You want to avoid modifying graph type
Property is used by most algorithms	Property is used by one specific algorithm

Complete Example

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

using namespace boost;

int main()
{
    // Graph with internal edge weights
    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);
    
    // External property for distances
    std::vector<int> distances(num_vertices(g));
    
    // Run Dijkstra (uses internal weights, external distances)
    dijkstra_shortest_paths(g, 0,
        distance_map(&distances[0]));
    
    // Print results
    for (int i = 0; i < distances.size(); ++i)
        std::cout << "Distance to " << i 
                  << ": " << distances[i] << "\n";
    
    return 0;
}

For more details, see: