This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

Grid Graph

A multi-dimensional, rectangular grid of vertices with user-defined dimension lengths and optional wrapping per dimension.

Defined in: <boost/graph/grid_graph.hpp>
Models: IncidenceGraph, AdjacencyGraph, VertexListGraph, EdgeListGraph, BidirectionalGraph, AdjacencyMatrix

grid_graph does not support bundled properties. To associate data with grid cells (e.g. terrain costs), maintain an external container indexed by the grid’s vertex index: std::vector<double> cost(num_vertices(g));

Flat grid

The simplest case: a rectangular grid with no wrapping. Corner vertices have fewer neighbors than interior vertices.

3x3 unwrapped grid 
#include <boost/graph/grid_graph.hpp>
#include <boost/array.hpp>
#include <iostream>

int main() {
    using namespace boost;
    using Graph = grid_graph<2>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

    // 3x3 flat grid (no wrapping)
    boost::array<std::size_t, 2> lengths = {{ 3, 3 }};
    Graph g(lengths);

    std::cout << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";

    // Corner vertex has 2 neighbors, edge vertex has 3, center has 4
    for (auto vi = vertices(g).first; vi != vertices(g).second; ++vi) {
        Vertex v = *vi;
        std::cout << "(" << v[0] << "," << v[1] << ") degree="
                  << out_degree(v, g) << "\n";
    }
}
9 vertices, 24 edges
(0,0) degree=2
(1,0) degree=3
(2,0) degree=2
(0,1) degree=3
(1,1) degree=4
(2,1) degree=3
(0,2) degree=2
(1,2) degree=3
(2,2) degree=2

Torus (all dimensions wrap)

Pass true as the second constructor argument to wrap all dimensions. Every vertex now has the same degree.

3x3 wrapped grid (torus) 
#include <boost/graph/grid_graph.hpp>
#include <boost/array.hpp>
#include <iostream>

int main() {
    using namespace boost;
    using Graph = grid_graph<2>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

    // 3x3 torus (all dimensions wrap)
    boost::array<std::size_t, 2> lengths = {{ 3, 3 }};
    Graph g(lengths, true);

    std::cout << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";

    // Every vertex has exactly 4 neighbors on a torus
    for (auto vi = vertices(g).first; vi != vertices(g).second; ++vi) {
        Vertex v = *vi;
        std::cout << "(" << v[0] << "," << v[1] << ") degree="
                  << out_degree(v, g) << "\n";
    }
}
9 vertices, 36 edges
(0,0) degree=4
(1,0) degree=4
(2,0) degree=4
(0,1) degree=4
(1,1) degree=4
(2,1) degree=4
(0,2) degree=4
(1,2) degree=4
(2,2) degree=4

Cylinder (mixed wrapping)

Pass a boost::array<bool, Dimensions> to control wrapping per dimension. Here dimension 0 wraps (cylinder) but dimension 1 does not.

#include <boost/graph/grid_graph.hpp>
#include <boost/array.hpp>
#include <iostream>

int main() {
    using namespace boost;
    using Graph = grid_graph<2>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

    // 4x3 cylinder: dimension 0 wraps, dimension 1 does not
    boost::array<std::size_t, 2> lengths = {{ 4, 3 }};
    boost::array<bool, 2> wrap = {{ true, false }};
    Graph g(lengths, wrap);

    std::cout << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";

    // Navigate: wrapping in dimension 0
    Vertex corner = vertex(0, g);
    Vertex wrapped = g.previous(corner, 0);  // wraps to (3,0)
    std::cout << "\nFrom (" << corner[0] << "," << corner[1] << "):\n";
    std::cout << "  previous in dim 0 (wraps) = ("
              << wrapped[0] << "," << wrapped[1] << ")\n";

    // Navigate: no wrapping in dimension 1
    Vertex same = g.previous(corner, 1);  // stays at (0,0)
    std::cout << "  previous in dim 1 (stops) = ("
              << same[0] << "," << same[1] << ")\n";
}
12 vertices, 40 edges

From (0,0):
  previous in dim 0 (wraps) = (3,0)
  previous in dim 1 (stops) = (0,0)

Higher dimensions

The Dimensions template parameter is a compile-time constant. A 3D grid works the same way.

#include <boost/graph/grid_graph.hpp>
#include <boost/array.hpp>
#include <iostream>

int main() {
    using namespace boost;
    using Graph = grid_graph<3>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

    // 3x3x3 cube (no wrapping)
    boost::array<std::size_t, 3> lengths = {{ 3, 3, 3 }};
    Graph g(lengths);

    std::cout << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";

    // Corner vertex: 3 neighbors. Center vertex: 6 neighbors.
    Vertex corner = vertex(0, g);
    Vertex center = {{ 1, 1, 1 }};
    std::cout << "corner (" << corner[0] << "," << corner[1] << ","
              << corner[2] << ") degree=" << out_degree(corner, g) << "\n";
    std::cout << "center (" << center[0] << "," << center[1] << ","
              << center[2] << ") degree=" << out_degree(center, g) << "\n";
}
27 vertices, 108 edges
corner (0,0,0) degree=3
center (1,1,1) degree=6

Synopsis

template <std::size_t Dimensions,
          typename VertexIndex = std::size_t,
          typename EdgeIndex = VertexIndex>
class grid_graph;

Template Parameters

Parameter Description Default

Dimensions

Number of dimensions (compile-time constant).

VertexIndex

Integer type for vertex indices.

std::size_t

EdgeIndex

Integer type for edge indices.

same as VertexIndex

Constructors

grid_graph(boost::array<VertexIndex, Dimensions> lengths);

Create an unwrapped grid with the given dimension lengths.

grid_graph(boost::array<VertexIndex, Dimensions> lengths,
           bool wrap_all);

Create a grid where all dimensions wrap (true) or none wrap (false).

grid_graph(boost::array<VertexIndex, Dimensions> lengths,
           boost::array<bool, Dimensions> wrap_per_dim);

Create a grid with per-dimension wrapping control.

Member Functions

std::size_t dimensions();

Returns the number of dimensions.

VertexIndex length(std::size_t dim);

Returns the length of dimension dim.

bool wrapped(std::size_t dim);

Returns whether dimension dim wraps.

vertex_descriptor next(vertex_descriptor v, std::size_t dim,
                       vertices_size_type distance = 1);
vertex_descriptor previous(vertex_descriptor v, std::size_t dim,
                           vertices_size_type distance = 1);

Move along a dimension. In an unwrapped dimension, next stops at the last vertex and previous stops at the first. In a wrapped dimension, movement wraps around.

Indexing

Vertices and edges can be addressed by integer index:

vertex_descriptor vertex(vertices_size_type idx, const grid_graph& g);
edges_size_type   get(edge_index_t, const grid_graph& g, edge_descriptor e);
edge_descriptor   edge_at(edges_size_type idx, const grid_graph& g);

The vertex descriptor is a boost::array<VertexIndex, Dimensions> that can be indexed by dimension: v[0] is the position in dimension 0, v[1] in dimension 1, etc.

Edit this Page