Property Maps
Algorithms need data on vertices and edges: weights, distances, colors, predecessors, communities. A property map is a lightweight accessor that reads and writes this data. You own the storage; the property map just knows how to index into it.
This separation lets you choose the allocation strategy (stack array, heap
vector, std::map, even a lambda) while algorithms access the data through a
uniform get(map, key) / put(map, key, value) interface.
The trade-off is that the complexity shifts to the point where you wrap your storage into this uniform interface: creating the property map.
How to attach data to a graph
There are three approaches. Start with bundled properties unless you have a specific reason not to.
1. Bundled properties (recommended)
Define a struct for your vertex/edge data. Access members with
get(&Struct::member, g).
struct City { std::string name; int population; };
struct Road { double distance; int lanes; };
using Graph = adjacency_list<vecS, vecS, directedS, City, Road>;
Graph g(3);
g[0].name = "Paris";
auto dist_map = get(&Road::distance, g); // property map for all edge distances| Use when: you own the graph type and know the properties at compile time. This is the simplest and most readable approach. |
2. External properties
Store data in your own container, then wrap it as a property map. The graph object knows nothing about this data.
std::vector<int> dist(num_vertices(g));
auto dist_map = make_iterator_property_map(dist.begin(), get(vertex_index, g));| Use when: the data is temporary (algorithm output), you cannot modify the graph type, or you need to control allocation (custom allocator, memory-mapped storage, reuse across calls). |
3. Internal property tags (legacy)
Attach properties via property<> tags at graph definition time. Access with
get(tag, g).
using Graph = adjacency_list<vecS, vecS, directedS,
no_property,
property<edge_weight_t, int>>;
auto weight = get(edge_weight, g);| Use only with existing code that already uses this style. Prefer bundled properties for new code. Tags are harder to read and do not compose well when you need multiple properties. |
| Most algorithms accept all three approaches interchangeably. The algorithm does not know or care where the data lives. |
When an algorithm parameter like color_map is not explicitly provided,
most algorithms allocate a temporary std::vector internally and wrap it with
the graph’s vertex_index map. This is why many algorithms work out of the box
with no property map arguments — but it requires VertexList=vecS (which
provides the built-in vertex index).
|
Property maps are not iterable. There is no begin()/end(). To
read all values, iterate over the graph’s vertices or edges and look up each
one: for (auto v : make_iterator_range(vertices(g))) std::cout << get(pm, v);
|
Creation reference
| Storage | Create with | Example |
|---|---|---|
Bundled struct member |
|
|
Internal property tag |
|
|
|
|
|
Raw C array |
Use directly |
|
|
|
|
Auto-growing vector |
|
|
Computed from a callable |
|
|
Transformed view of another map |
|
|
Vertex degree (read-only) |
|
|
Constant value for all keys |
|
|
Discard output (placeholder) |
|
|
Memory-efficient 2-color map |
|
|
Memory-efficient 4-color map |
|
|
The interface
Every property map supports at most three operations:
value = get(pm, key); // read (Readable)
put(pm, key, value); // write (Writable)
reference = pm[key]; // reference access (Lvalue only)get() returns a copy of the value. For Lvalue property maps, pm[key]
returns a reference (const or mutable depending on the map).
To deduce types from a property map at compile time, use property_traits:
using Value = typename property_traits<Map>::value_type;
using Key = typename property_traits<Map>::key_type;
using Cat = typename property_traits<Map>::category;This is the property map equivalent of std::iterator_traits.
Property map categories
When reading algorithm documentation, each parameter is tagged with a direction: IN, OUT, or UTIL/OUT. These correspond to property map categories that determine what operations the algorithm will perform on the map.
| Category | Algorithm tag | What it means |
|---|---|---|
Readable |
IN |
The algorithm only reads: |
Writable |
OUT |
The algorithm only writes: |
ReadWrite |
UTIL/OUT |
The algorithm reads and writes: both |
Lvalue |
(rare) |
|
For example, in dijkstra_shortest_paths, the weight_map parameter is
tagged IN (the algorithm reads edge weights but never modifies them), while
distance_map is tagged UTIL/OUT (the algorithm both reads and writes
distances during relaxation).
Passing a read-only map (like make_function_property_map) where
the algorithm expects ReadWrite will fail to compile. The error message will
mention put() not being found, which can be confusing if you do not know
about these categories.
|
Headers
| Header | Contents |
|---|---|
|
Internal property tags ( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Most algorithm headers pull in <boost/graph/properties.hpp>
automatically, but external property map adaptors (iterator_property_map,
vector_property_map, etc.) require explicit includes from
<boost/property_map/>. Forgetting this is a common source of confusing
template errors.
|
Complete example
All property map types in one file:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/property_map/vector_property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <map>
#include <string>
#include <vector>
struct City { std::string name; };
struct Road { double km; };
using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS, City, Road>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
int main() {
Graph g(3);
g[0].name = "Paris";
g[1].name = "Lyon";
g[2].name = "Marseille";
add_edge(0, 1, Road{460}, g);
add_edge(1, 2, Road{310}, g);
add_edge(0, 2, Road{775}, g);
auto index_map = get(vertex_index, g);
// Bundled property map
auto km_map = get(&Road::km, g);
// std::vector + make_iterator_property_map
std::vector<int> vec(num_vertices(g), -1);
auto vec_map = make_iterator_property_map(vec.begin(), index_map);
put(vec_map, vertex(0, g), 42);
// Raw C array (usable directly as a property map)
int arr[3] = {100, 200, 300};
// std::map + make_assoc_property_map
std::map<Vertex, std::string> labels;
auto label_map = make_assoc_property_map(labels);
put(label_map, vertex(0, g), "capital");
// vector_property_map (auto-growing, heap-allocated)
vector_property_map<double, decltype(index_map)> vpm(num_vertices(g), index_map);
put(vpm, vertex(2, g), 3.14);
// Computed from a lambda (read-only)
auto degree_map = make_function_property_map<Vertex>([&](Vertex v) { return out_degree(v, g); });
// Transformed view of another map
auto miles_map = make_transform_value_property_map([](double d) { return d * 0.621371; }, km_map);
// Constant for all keys
static_property_map<double> unit(1.0);
// Discard writes (placeholder)
dummy_property_map sink;
put(sink, vertex(0, g), 999); // silently ignored
// All accessed the same way: get(map, key)
std::cout << get(km_map, edge(0, 1, g).first) << " km\n";
std::cout << get(vec_map, vertex(0, g)) << "\n";
std::cout << get(arr, 1) << "\n";
std::cout << get(label_map, vertex(0, g)) << "\n";
std::cout << get(vpm, vertex(2, g)) << "\n";
std::cout << get(degree_map, vertex(0, g)) << "\n";
std::cout << get(miles_map, edge(0, 1, g).first) << " miles\n";
std::cout << get(unit, vertex(0, g)) << "\n";
}460 km
42
200
capital
3.14
2
285.831 miles
1