Some tools for manipulating nearestneighbors graphs defined on regular grids
Project description
Gridgraph (fork)
About this fork
The original code in available in this repository: https://gitlab.com/1a7r0ch3/gridgraph.
This a fork for python packaging purposes.
Please post issues in this repos only if you are sure your problem is related to the packaging... and please post issue on the upstream repository only if you are sure your problem is not related to the packaging.
Below, the original README.
Original README
Some tools for manipulating nearestneighbors 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 lengthD
, 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 forD
= 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 forwardstar, where edges are numbered (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 edgesadj_vertices
 array of length E, indicating for each edge, its ending vertex
Vertices of the grid are indexed in columnmajor 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 rowmajor 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 documentation 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
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for pygrid_graph0.0.3cp312cp312win_amd64.whl
Algorithm  Hash digest  

SHA256  1aa77d7a094d43c6bcf8410ebb11dfb4f4e3dc13e37c2651dbb1fceab7ef95a2 

MD5  737fbd76393ecfecaa82661e78d3f55e 

BLAKE2b256  fa4e5c30cfe81310c149d146826b9722eb1b8be82a5535daf8f2123d31fc1926 
Hashes for pygrid_graph0.0.3cp312cp312musllinux_1_1_x86_64.whl
Algorithm  Hash digest  

SHA256  99fb1ecd2ae949323c711a47e0513bf84cd0dff5f816b0d3644418a9a4bd66c0 

MD5  024f5700fbd5fe70c2f910fa7d547201 

BLAKE2b256  6b70c584407018df0b748989a6dd41f2803853c432bd9002f85b3afd78eed27b 
Hashes for pygrid_graph0.0.3cp312cp312manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm  Hash digest  

SHA256  eb315465bf41d8a8cb0d04a0ae1e99afc81d93d6f235fca07bd1840b51be608f 

MD5  15602d711c2213fa33b2374b2c3169a2 

BLAKE2b256  491a6bf7b2433a3ba2129063bdc26deccaa4ed1dbde755068ef584a0cecbd8d9 
Hashes for pygrid_graph0.0.3cp312cp312macosx_11_0_arm64.whl
Algorithm  Hash digest  

SHA256  9d2712a6761fd7d1073feb380cd1348513d27e7f50bfbbd14580ef87efe6223e 

MD5  8d3c1f3b12309f47acf79c1f80d08cd7 

BLAKE2b256  051344925593f040c2916a5c8f872e202c65edc4688019173cb014ac9f7c5bcf 
Hashes for pygrid_graph0.0.3cp311cp311win_amd64.whl
Algorithm  Hash digest  

SHA256  f4e608f7b29a35c37e2bbc4f5103c4673307fcd363439119aa5b0282d5beb1c1 

MD5  37b4acde92b1d61181002dd25be68097 

BLAKE2b256  8e9974b55c45766d1b044e9a38cbbb7370f6bc468a5efb2da11ec814c0d55c45 
Hashes for pygrid_graph0.0.3cp311cp311musllinux_1_1_x86_64.whl
Algorithm  Hash digest  

SHA256  834ef2583d60be6e22d5ae5649f7fcd31fa5bd424e2f9f7672a870d62e41b719 

MD5  42c9f18567f7b2f2d3d65c17f7543c76 

BLAKE2b256  a10150238550160d3691003edba5922daae1e601b4b6af610b252fc72aa7162c 
Hashes for pygrid_graph0.0.3cp311cp311manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm  Hash digest  

SHA256  68a041b188d28d900060258f113a2b38e770d808fb9889da6dce8e4e319fc72a 

MD5  eec4c2d6a64d7a947aa5991de783f046 

BLAKE2b256  689dd050d8bc5ef3b1246a43234bbc13b82d20dceff277bd06eb37271c8716ea 
Hashes for pygrid_graph0.0.3cp311cp311macosx_11_0_arm64.whl
Algorithm  Hash digest  

SHA256  8d4a8a89f392a02db2c361805c4a46e73abe2caf9e7e0e307f7086a190fb0eb6 

MD5  23fb2b0e60b4d630cd6eeca4555b8963 

BLAKE2b256  41da7dff4384899692cae5e38546dbbd059ab5291d8edafdc3aed2e19f5a2355 
Hashes for pygrid_graph0.0.3cp310cp310win_amd64.whl
Algorithm  Hash digest  

SHA256  8c09478840f8598aaee7d108256ebd4b190dae52113901961c63fcd816949c21 

MD5  a3623db6a8f131fd538e69a92117fe1f 

BLAKE2b256  f4db82c7dbff8ff3e7851dbb19a04ffc02d59af1699ad45fd954b6510ac21470 
Hashes for pygrid_graph0.0.3cp310cp310musllinux_1_1_x86_64.whl
Algorithm  Hash digest  

SHA256  2b31e5ef7c7f99d0c162778487d60c717f033dc8d7466d50bf692111bb90be4b 

MD5  eaf6765808a8c4b050e26383fe91ef99 

BLAKE2b256  06e8cbb6b9dcd36e90798198b78089efa56847da509fbea2426f01228dc0b1bd 
Hashes for pygrid_graph0.0.3cp310cp310manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm  Hash digest  

SHA256  e2e946dee277c858c1b8b08aed413baa33289131c79d7baffc70f4ce6c22f9c9 

MD5  63acbe37ae6cdeec224976a44d2d2465 

BLAKE2b256  beef3b230eb052465df3760c52d29cb335d92ad48b926e8f68023feccbf21192 
Hashes for pygrid_graph0.0.3cp310cp310macosx_11_0_arm64.whl
Algorithm  Hash digest  

SHA256  3e63e81a9a6e7919b3ce57296d2b6905a03a2653b1a12fbf2bcf0579fbf0f00c 

MD5  2edb8424af8f750aac7bcf1596ce8c63 

BLAKE2b256  b8b5777ef7cf42d548db51e368c42c63af835bb823bde0d6171bb388ee1c0d2a 
Hashes for pygrid_graph0.0.3cp39cp39win_amd64.whl
Algorithm  Hash digest  

SHA256  2027c38f96d1554a5ca083ab93740557a4b13852db2c0c84f16ef8410f87c38a 

MD5  afcd04797c486487ab80bb0e73136d40 

BLAKE2b256  22e7022094c82634157907d77dc2a553130be012700b76bdb27f2ee5f7cd2c63 
Hashes for pygrid_graph0.0.3cp39cp39musllinux_1_1_x86_64.whl
Algorithm  Hash digest  

SHA256  56973e4eb1f022b446a0ab648875828fd3ca909b145851d9bae4c8d88cece545 

MD5  214fb2b9df65576b902654dc7c3954bd 

BLAKE2b256  62f7ace9f82f8e4af5c596b9b00c154badf8b8db2e759b937d4d8c533662fc65 
Hashes for pygrid_graph0.0.3cp39cp39manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm  Hash digest  

SHA256  aa637f46f1cdbc01dfbda7d29547f831762c1a71329f3750ec1594285f6ffe9a 

MD5  478c47dadd626414f724bf90decbcdcd 

BLAKE2b256  7f32fceb77bb60c72e8013610d9496c058eb8eab3684a110be9ec10bf456226a 
Hashes for pygrid_graph0.0.3cp39cp39macosx_11_0_arm64.whl
Algorithm  Hash digest  

SHA256  e3742dcdc4a3e3fd4a25d4ab0a64e6df321c20f263340f3b2e72f8a6cc415380 

MD5  c56e6f49ccbf5176e1b91b41cabef1ce 

BLAKE2b256  1cc640d7fb5b78f058b26de2fc89d3b47aa4d7bed88da9e17cb1c48dc227284b 