Some tools for manipulating nearest-neighbors graphs defined on regular grids

C++ routines.
Parallelization with OpenMP.
Mex interfaces for GNU Octave or Matlab.
Extension module for Python.

A grid graph in dimension D is defined by the following parameters:

D - the number of dimensions
shape - array of length D, giving the grid size in each dimension
connectivity - defines the neighboring relationship;
corresponds to the square of the maximum Euclidean distance between two neighbors; if less than 4, it defines the number of coordinates allowed to simultaneously vary (+1 or -1) to define a neighbor; (in that case, each level ℓ of connectivity in dimension D adds C_ℓ^D ⨯ 2^ℓ neighbors).
Corresponding number of neighbors for D = 2 and 3:

connectivity 1 2 3

2D 4 8 (8)

3D 6 18 26

Note that a connectivity of 4 or more includes neighbors whose coordinates might differ by 2 or more from the coordinates of the considered vertex. In that sense, in dimension 4 or more, including all immediately surrounding vertices (that is, all vertices for which each coordinate differ by 1 or less) would then also include vertices from a more distant surround: the neighbor v + (2, 0, 0, 0) is at the same distance as the neighbor v + (1, 1, 1, 1).

connectivity	1	2	3
2D	4	8	(8)
3D	6	18	26

A graph with V vertices and E edges is represented either as edge list (array of E edges given as ordered pair of vertices), or as forward-star, where edges are numeroted (from 0 to E − 1) so that all edges originating from a same vertex are consecutive, and represented by the following parameters:

first_edge - array of length V + 1, indicating for each vertex, the first edge starting from the vertex (or, if there are none, starting from the next vertex); the last value is always the total number of edges
adj_vertices - array of length E, indicating for each edge, its ending vertex

Vertices of the grid are indexed in column-major order, that is indices increase first along the first dimension specified in the 'shape' array (in the usual convention in 2D, this corresponds to columns), and then along the second dimension, and so on up to the last dimension. Indexing in row-major order (indices increase first along the last dimension and so on up to the first) can be obtained by simply reverting the order of the grid dimensions in the shape array (in 2D, this amounts to transposition).

Work possibly in parallel with OpenMP API

Directory tree

.   
├── include/      C++ headers, with some doc  
├── octave/       GNU Octave or Matlab code  
│   ├── doc/      some documentation  
│   └── mex/      MEX C++ interfaces
├── python/       Python code  
│   └── cpython/  C Python interface  
└── src/          C++ sources

C++ documentation

Requires C++11.
Be sure to have OpenMP enabled with your compiler to enjoy parallelization. Note that, as of 2020, MSVC still does not support OpenMP 3.0 (published in 2008); consider switching to a decent compiler.

The C++ classes are documented within the corresponding headers in include/.

Python extension module

Requires numpy package.
See the script setup.py for compiling the module with distutils; on UNIX systems, it can be directly interpreted as python setup.py build_ext.
Compatible with Python 2 and Python 3.

Once compiled, see the documentation with the help() python utility.

GNU Octave or Matlab

See the script compile_grid_graph_mex.m for typical compilation commands; it can be run directly from the GNU Octave interpreter, but Matlab users must set compilation flags directly on the command line CXXFLAGS = ... and LDFLAGS = ....

Extensive documention of the MEX interfaces can be found within dedicated .m files in octave/doc/.

References and license

This software is under the GPLv3 license.

Hugo Raguet 2019, 2020