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

## 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 CD ⨯ 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).

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.
Requires numpy package.
See the script setup.py for compiling modules with setuptools; it can be run simply by using pip e.g. python -m pip install .. pre compiled binaries for Windows and Linux will soon be available on PyPI

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/.

This software is under the GPLv3 license.

Hugo Raguet 2019, 2020

## Project details

### Source Distributions

No source distribution files available for this release.See tutorial on generating distribution archives.

### Built Distributions

pygrid_graph-0.0.2-cp312-cp312-macosx_14_0_arm64.whl (43.8 kB view hashes)

Uploaded CPython 3.12 macOS 14.0+ ARM64

pygrid_graph-0.0.2-cp311-cp311-win_amd64.whl (42.2 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

pygrid_graph-0.0.2-cp311-cp311-win32.whl (41.0 kB view hashes)

Uploaded CPython 3.11 Windows x86

pygrid_graph-0.0.2-cp311-cp311-musllinux_1_1_x86_64.whl (721.2 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

pygrid_graph-0.0.2-cp311-cp311-musllinux_1_1_i686.whl (772.5 kB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

pygrid_graph-0.0.2-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (162.0 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

pygrid_graph-0.0.2-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl (165.7 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686

pygrid_graph-0.0.2-cp311-cp311-macosx_14_0_arm64.whl (43.7 kB view hashes)

Uploaded CPython 3.11 macOS 14.0+ ARM64

pygrid_graph-0.0.2-cp310-cp310-win_amd64.whl (42.2 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

pygrid_graph-0.0.2-cp310-cp310-win32.whl (41.0 kB view hashes)

Uploaded CPython 3.10 Windows x86

pygrid_graph-0.0.2-cp310-cp310-musllinux_1_1_x86_64.whl (720.1 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

pygrid_graph-0.0.2-cp310-cp310-musllinux_1_1_i686.whl (771.5 kB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

pygrid_graph-0.0.2-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (161.9 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

pygrid_graph-0.0.2-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl (165.5 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686

pygrid_graph-0.0.2-cp39-cp39-win_amd64.whl (42.2 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

pygrid_graph-0.0.2-cp39-cp39-win32.whl (41.0 kB view hashes)

Uploaded CPython 3.9 Windows x86

pygrid_graph-0.0.2-cp39-cp39-musllinux_1_1_x86_64.whl (719.6 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

pygrid_graph-0.0.2-cp39-cp39-musllinux_1_1_i686.whl (771.2 kB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

pygrid_graph-0.0.2-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (161.7 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

pygrid_graph-0.0.2-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl (165.3 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686

pygrid_graph-0.0.2-cp38-cp38-win_amd64.whl (42.2 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

pygrid_graph-0.0.2-cp38-cp38-win32.whl (41.0 kB view hashes)

Uploaded CPython 3.8 Windows x86

pygrid_graph-0.0.2-cp38-cp38-musllinux_1_1_x86_64.whl (720.0 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

pygrid_graph-0.0.2-cp38-cp38-musllinux_1_1_i686.whl (771.4 kB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

pygrid_graph-0.0.2-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (161.7 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

pygrid_graph-0.0.2-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl (165.3 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686`