| ## 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<sub>ℓ</sub><sup>_D_</sup> ⨯ 2<sup>ℓ</sup> | |
| 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). | |
| 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 | |