Spatial KWD for Large Spatial Maps
Project description
Spatial-KWD: Kantorovich-Wasserstein Distances for Large Spatial Maps
The Spatial-KWD package contains efficient implementations of Discrete Optimal Transport algorithms for the computation of Kantorovich-Wasserstein distances [1], which are customized for large spatial maps. All the algorithms are based on an ad-hoc implementation of the Network Simplex algorithm [1,2]. Each implemented algorithm builds a different network, exploiting the special structure of spatial maps.
Details
This library contains three helper functions and two main classes.
The three helper functions are compareOneToOne
, compareOneToMany
, and compareAll
. All the functions take in input the data and an options list. Using the options is possible to configure the Kantorivich-Wasserstein solver, so that it uses different algorithms with different parameters.
The helper functions are built on top of two main classes: Histogram2D
and Solver
.
Note that in case of non-convex maps, the algorithm builds the convex-hull of the input bins and pads the weights with zeros.
Prerequisities
You only need the following two standard python libraries:
- cython
- numpy
In the case you want to compile the source files, you need the python-dev
, which on linux can be installed by>
apt install python3-dev # Ubuntu
Installation
To install Spatial-KWD you can run the following command:
pip3 install Spatial-KWD
This will compile the C++ code and build the python wrapper.
Testing
For testing the library you can run the following command:
python3 test_matrix.py
The test program is the following
import numpy as np
from KWD import compareOneToOne, compareOneToMany, compareAll
np.random.seed(13)
N = 32*32
M = 3
# Random data
Coordinates = np.random.randint(0, 32, size=(N, 2), dtype=np.int32)
Weights = np.random.uniform(0, 100, size=(N, 2))
# Testing the first helper function
print('-----------------------------\nTest one2one approx:')
Options = {'Verbosity': 'debug'}
sol = compareOneToOne(Coordinates, Weights, Options)
for k in sol:
print(k, sol[k])
References
[1] Bassetti, F., Gualandi, S. and Veneroni, M., 2020. On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows. SIAM Journal on Optimization, 30(3), pp.2441-2469.
[2] Cunningham, W.H., 1976. A Network Simplex method. Mathematical Programming, 11(1), pp.105-116.
[3] https://github.com/eurostat/Spatial-KWD
Authors and maintainers
Stefano Gualandi, stefano.gualandi@gmail.com.
Maintainer: Stefano Gualandi stefano.gualandi@gmail.com
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 Spatial_KWD-0.2.6-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9d0fac951904e2757cdcdc56490e7fe96090ef1c890a9a3f31f36a7486bc26b2 |
|
MD5 | 684028e6eb8003aac2c8aca24ff5bc3c |
|
BLAKE2b-256 | d5843bcb55fdef6e453664b056f18b604f72200dd85825f508060856319531e5 |
Hashes for Spatial_KWD-0.2.6-cp39-cp39-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a7ca5261fd7464f18df5205fc465c154d070c783d6044cb9094d6dd6270b5b52 |
|
MD5 | 854b7370d4cb0b6eb6460f2c0bdd551f |
|
BLAKE2b-256 | 08daad237c5b53ed34dddfdd38e43ddb423577f6c14b9126e07c8d7fefb1cfb7 |
Hashes for Spatial_KWD-0.2.6-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 10cea7c108fc445c43ee30dc5d025fd237b8840519651498942ac80dd2009fbc |
|
MD5 | c770ac4a01ff1a42d60c058bcd722569 |
|
BLAKE2b-256 | 950caafbb10f86062c223a0c0900f43774b8c6a8ea4137eeba2b10d84e9fc585 |
Hashes for Spatial_KWD-0.2.6-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7adc662880d7e0385b376463fde55dc8772222204b9a6fd1d6c28fe43e382b18 |
|
MD5 | 0026be71bddb2c9f7a8a445e7cac3d9c |
|
BLAKE2b-256 | 9244a5894530e370c38ae26f71fc0ff4e682009160321d20d92a7489be2c9ea5 |
Hashes for Spatial_KWD-0.2.6-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b6611e90964c71360887574cfe3f45b7e50ffde160db58d965aa2bea27ce4a04 |
|
MD5 | 3a8f5cacee1155934c2a8cec4bfd18b1 |
|
BLAKE2b-256 | f5fde527ee3860de333c06a555a450def2342d25c227e9ac05ded7275ecac562 |
Hashes for Spatial_KWD-0.2.6-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 48139845ade1d243e2aeb8e8fd9694e4a7a2d4f858beb551bebea23f998ba157 |
|
MD5 | c7e8e088604bfdb9abff9a969221f89d |
|
BLAKE2b-256 | 347a1182163f95c03fc0246a9666d477d2d208a40e7bed5a820ae38ae874f6af |
Hashes for Spatial_KWD-0.2.6-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 682d1b86365a7250146cd71a61a9c1071970d50b11b488d44978e8f5ac7c00a0 |
|
MD5 | e6c6398ac2140466381da5efcbbd1155 |
|
BLAKE2b-256 | 1a430a59d94b9aa4b29785cc1d83dfb917010d6d51d5cd72bc489749765c6b4d |
Hashes for Spatial_KWD-0.2.6-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1d368fb639c672ba606a2aec10207dca9ddf6ef1e5d0998885cb6576f707dd1a |
|
MD5 | 0a259669241ad78f19704e8deb0adb62 |
|
BLAKE2b-256 | 7948de80df7df368a137b307d1a57f87eef66e01f93376548657bc68f53f0c9e |