POT : Python Optimal Transport

Overview

POT: Python Optimal Transport

PyPI version Anaconda Cloud Build Status Codecov Status Downloads Anaconda downloads License

This open source Python library provide several solvers for optimization problems related to Optimal Transport for signal, image processing and machine learning.

Website and documentation: https://PythonOT.github.io/

Source Code (MIT): https://github.com/PythonOT/POT

POT provides the following generic OT solvers (links to examples):

POT provides the following Machine Learning related solvers:

Some other examples are available in the documentation.

Using and citing the toolbox

If you use this toolbox in your research and find it useful, please cite POT using the following reference from our JMLR paper:

Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, Titouan Vayer,
POT Python Optimal Transport library,
Journal of Machine Learning Research, 22(78):1−8, 2021.
Website: https://pythonot.github.io/

In Bibtex format:

@article{flamary2021pot,
  author  = {R{\'e}mi Flamary and Nicolas Courty and Alexandre Gramfort and Mokhtar Z. Alaya and Aur{\'e}lie Boisbunon and Stanislas Chambon and Laetitia Chapel and Adrien Corenflos and Kilian Fatras and Nemo Fournier and L{\'e}o Gautheron and Nathalie T.H. Gayraud and Hicham Janati and Alain Rakotomamonjy and Ievgen Redko and Antoine Rolet and Antony Schutz and Vivien Seguy and Danica J. Sutherland and Romain Tavenard and Alexander Tong and Titouan Vayer},
  title   = {POT: Python Optimal Transport},
  journal = {Journal of Machine Learning Research},
  year    = {2021},
  volume  = {22},
  number  = {78},
  pages   = {1-8},
  url     = {http://jmlr.org/papers/v22/20-451.html}
}

Installation

The library has been tested on Linux, MacOSX and Windows. It requires a C++ compiler for building/installing the EMD solver and relies on the following Python modules:

  • Numpy (>=1.16)
  • Scipy (>=1.0)
  • Cython (>=0.23)
  • Matplotlib (>=1.5)

Pip installation

Note that due to a limitation of pip, cython and numpy need to be installed prior to installing POT. This can be done easily with

pip install numpy cython

You can install the toolbox through PyPI with:

pip install POT

or get the very latest version by running:

pip install -U https://github.com/PythonOT/POT/archive/master.zip # with --user for user install (no root)

Anaconda installation with conda-forge

If you use the Anaconda python distribution, POT is available in conda-forge. To install it and the required dependencies:

conda install -c conda-forge pot

Post installation check

After a correct installation, you should be able to import the module without errors:

import ot

Note that for easier access the module is name ot instead of pot.

Dependencies

Some sub-modules require additional dependences which are discussed below

  • ot.dr (Wasserstein dimensionality reduction) depends on autograd and pymanopt that can be installed with:
pip install pymanopt autograd
  • ot.gpu (GPU accelerated OT) depends on cupy that have to be installed following instructions on this page. Obviously you will need CUDA installed and a compatible GPU.

Examples

Short examples

  • Import the toolbox
import ot
  • Compute Wasserstein distances
# a,b are 1D histograms (sum to 1 and positive)
# M is the ground cost matrix
Wd = ot.emd2(a, b, M) # exact linear program
Wd_reg = ot.sinkhorn2(a, b, M, reg) # entropic regularized OT
# if b is a matrix compute all distances to a and return a vector
  • Compute OT matrix
# a,b are 1D histograms (sum to 1 and positive)
# M is the ground cost matrix
T = ot.emd(a, b, M) # exact linear program
T_reg = ot.sinkhorn(a, b, M, reg) # entropic regularized OT
  • Compute Wasserstein barycenter
# A is a n*d matrix containing d  1D histograms
# M is the ground cost matrix
ba = ot.barycenter(A, M, reg) # reg is regularization parameter

Examples and Notebooks

The examples folder contain several examples and use case for the library. The full documentation with examples and output is available on https://PythonOT.github.io/.

Acknowledgements

This toolbox has been created and is maintained by

The contributors to this library are

This toolbox benefit a lot from open source research and we would like to thank the following persons for providing some code (in various languages):

Contributions and code of conduct

Every contribution is welcome and should respect the contribution guidelines. Each member of the project is expected to follow the code of conduct.

Support

You can ask questions and join the development discussion:

You can also post bug reports and feature requests in Github issues. Make sure to read our guidelines first.

References

[1] Bonneel, N., Van De Panne, M., Paris, S., & Heidrich, W. (2011, December). Displacement interpolation using Lagrangian mass transport. In ACM Transactions on Graphics (TOG) (Vol. 30, No. 6, p. 158). ACM.

[2] Cuturi, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems (pp. 2292-2300).

[3] Benamou, J. D., Carlier, G., Cuturi, M., Nenna, L., & Peyré, G. (2015). Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2), A1111-A1138.

[4] S. Nakhostin, N. Courty, R. Flamary, D. Tuia, T. Corpetti, Supervised planetary unmixing with optimal transport, Whorkshop on Hyperspectral Image and Signal Processing : Evolution in Remote Sensing (WHISPERS), 2016.

[5] N. Courty; R. Flamary; D. Tuia; A. Rakotomamonjy, Optimal Transport for Domain Adaptation, in IEEE Transactions on Pattern Analysis and Machine Intelligence , vol.PP, no.99, pp.1-1

[6] Ferradans, S., Papadakis, N., Peyré, G., & Aujol, J. F. (2014). Regularized discrete optimal transport. SIAM Journal on Imaging Sciences, 7(3), 1853-1882.

[7] Rakotomamonjy, A., Flamary, R., & Courty, N. (2015). Generalized conditional gradient: analysis of convergence and applications. arXiv preprint arXiv:1510.06567.

[8] M. Perrot, N. Courty, R. Flamary, A. Habrard (2016), Mapping estimation for discrete optimal transport, Neural Information Processing Systems (NIPS).

[9] Schmitzer, B. (2016). Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems. arXiv preprint arXiv:1610.06519.

[10] Chizat, L., Peyré, G., Schmitzer, B., & Vialard, F. X. (2016). Scaling algorithms for unbalanced transport problems. arXiv preprint arXiv:1607.05816.

[11] Flamary, R., Cuturi, M., Courty, N., & Rakotomamonjy, A. (2016). Wasserstein Discriminant Analysis. arXiv preprint arXiv:1608.08063.

[12] Gabriel Peyré, Marco Cuturi, and Justin Solomon (2016), Gromov-Wasserstein averaging of kernel and distance matrices International Conference on Machine Learning (ICML).

[13] Mémoli, Facundo (2011). Gromov–Wasserstein distances and the metric approach to object matching. Foundations of computational mathematics 11.4 : 417-487.

[14] Knott, M. and Smith, C. S. (1984).On the optimal mapping of distributions, Journal of Optimization Theory and Applications Vol 43.

[15] Peyré, G., & Cuturi, M. (2018). Computational Optimal Transport .

[16] Agueh, M., & Carlier, G. (2011). Barycenters in the Wasserstein space. SIAM Journal on Mathematical Analysis, 43(2), 904-924.

[17] Blondel, M., Seguy, V., & Rolet, A. (2018). Smooth and Sparse Optimal Transport. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (AISTATS).

[18] Genevay, A., Cuturi, M., Peyré, G. & Bach, F. (2016) Stochastic Optimization for Large-scale Optimal Transport. Advances in Neural Information Processing Systems (2016).

[19] Seguy, V., Bhushan Damodaran, B., Flamary, R., Courty, N., Rolet, A.& Blondel, M. Large-scale Optimal Transport and Mapping Estimation. International Conference on Learning Representation (2018)

[20] Cuturi, M. and Doucet, A. (2014) Fast Computation of Wasserstein Barycenters. International Conference in Machine Learning

[21] Solomon, J., De Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyen, A. & Guibas, L. (2015). Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics (TOG), 34(4), 66.

[22] J. Altschuler, J.Weed, P. Rigollet, (2017) Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, Advances in Neural Information Processing Systems (NIPS) 31

[23] Aude, G., Peyré, G., Cuturi, M., Learning Generative Models with Sinkhorn Divergences, Proceedings of the Twenty-First International Conference on Artficial Intelligence and Statistics, (AISTATS) 21, 2018

[24] Vayer, T., Chapel, L., Flamary, R., Tavenard, R. and Courty, N. (2019). Optimal Transport for structured data with application on graphs Proceedings of the 36th International Conference on Machine Learning (ICML).

[25] Frogner C., Zhang C., Mobahi H., Araya-Polo M., Poggio T. (2015). Learning with a Wasserstein Loss Advances in Neural Information Processing Systems (NIPS).

[26] Alaya M. Z., Bérar M., Gasso G., Rakotomamonjy A. (2019). Screening Sinkhorn Algorithm for Regularized Optimal Transport, Advances in Neural Information Processing Systems 33 (NeurIPS).

[27] Redko I., Courty N., Flamary R., Tuia D. (2019). Optimal Transport for Multi-source Domain Adaptation under Target Shift, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (AISTATS) 22, 2019.

[28] Caffarelli, L. A., McCann, R. J. (2010). Free boundaries in optimal transport and Monge-Ampere obstacle problems, Annals of mathematics, 673-730.

[29] Chapel, L., Alaya, M., Gasso, G. (2020). Partial Optimal Transport with Applications on Positive-Unlabeled Learning, Advances in Neural Information Processing Systems (NeurIPS), 2020.

[30] Flamary R., Courty N., Tuia D., Rakotomamonjy A. (2014). Optimal transport with Laplacian regularization: Applications to domain adaptation and shape matching, NIPS Workshop on Optimal Transport and Machine Learning OTML, 2014.

[31] Bonneel, Nicolas, et al. Sliced and radon wasserstein barycenters of measures, Journal of Mathematical Imaging and Vision 51.1 (2015): 22-45

Comments
  •  [WIP] small tentative for EMD 1D in torch

    [WIP] small tentative for EMD 1D in torch

    I saw the torch branch for LP stuff. Would you be interested in my implementation for the 1d EMD (and the sliced wasserstein with it)?

    I'm not a huge fan of Pytorch so I can't vouch that what I'm doing here is the best implementation, but it feels to me like it should be fairly ok for batched inputs which is what you want for slice stuff anyway.

    opened by AdrienCorenflos 47
  • GPU changes:

    GPU changes:

    • Replace cudamat by cupy for GPU implementations (cupy is still in active development, while cudamat is not)
    • Use the new DA class instead of the old deprecated one

    TODO for another PR:

    • Performances are still a bit lower than with cudamat (even if better than CPU for large matrices). Some speedups should be possible by tweaking the code
    opened by toto6 38
  • Domain adaptation Classes

    Domain adaptation Classes

    • first proposal of DA class structure
    • BaseEstimator: OTDA wrapper (does not work as a stand-alone but implements the methods common to any OTDA algorithm)
    • SinkhornTransport: implements Sinkhorn algorithm for OTDA
    • try doc strings compliant with numpy requirements
    opened by Slasnista 29
  • Domain adaptation Classes

    Domain adaptation Classes

    We should change the domain adaptation Classes to be more sklearn compliant.

    Main issues:

    • Use CamelCase for classes
    • Use init for setting parameters and instead of fit.

    @agramfort proposed to Creat new Clases with proper names and begin deprecating the old classes.

    I think it is a good move.

    enhancement 
    opened by rflamary 28
  • Not in simplex -- two sets of largely different sizes

    Not in simplex -- two sets of largely different sizes

    I am trying to calculate the EMD of two sets. When one set has a few hundred entries and the other has only 2, the EMD calculation fails and returns Problem Infeasible.

    Steps to reproduce the behavior: ** SEE BELOW COMMENT FOR FIXED SCRIPT **

    Expected behavior Should return EMD around 1, instead says that the sets spherEng1 and pencilEnergy are not in the simplex

    Screenshots Here is comparing the EMDs calculated for less densely tiled to most densely tiled (number of particles = number of segments) with the two element set image

    Desktop (please complete the following information):

    • OS: [MacOSX]
    • Python version [3.6]
    • POT installed with pip

    import platform; print(platform.platform()) Darwin-16.7.0-x86_64-i386-64bit import sys; print("Python", sys.version) ('Python', '2.7.15 |Anaconda, Inc.| (default, Dec 14 2018, 13:10:39) \n[GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)]') import numpy; print("NumPy", numpy.version) ('NumPy', '1.15.4') import scipy; print("SciPy", scipy.version) ('SciPy', '1.1.0') import ot; print("POT", ot.version) ('POT', '0.5.1')

    opened by caricesarotti 25
  • [MRG] Sliced wasserstein

    [MRG] Sliced wasserstein

    Types of changes

    • [ ] Docs change / refactoring / dependency upgrade
    • [ ] Bug fix (non-breaking change which fixes an issue)
    • [X] New feature (non-breaking change which adds functionality)
    • [ ] Breaking change (fix or feature that would cause existing functionality to change)

    Motivation and context / Related issue

    Implement SWD: https://github.com/PythonOT/POT/issues/202

    How has this been tested (if it applies)

    Added specific tests (positive definiteness + matching the EMD in the 1D case)

    Checklist

    • [X] The documentation is up-to-date with the changes I made.
    • [X] I have read the CONTRIBUTING document.
    • [x] All tests passed, and additional code has been covered with new tests.

    Not sure why yet but the stuff doesn't build.

    I'm publishing this as a draft as I have some other changes in my branch that are pending for another merge (cf this: https://github.com/PythonOT/POT/issues/200)

    opened by AdrienCorenflos 19
  • [WIP] torch implementation of the Sliced Wasserstein Distance

    [WIP] torch implementation of the Sliced Wasserstein Distance

    Types of changes

    • [ ] Docs change / refactoring / dependency upgrade
    • [ ] Bug fix (non-breaking change which fixes an issue)
    • [x] New feature (non-breaking change which adds functionality)
    • [ ] Breaking change (fix or feature that would cause existing functionality to change)

    Motivation and context / Related issue

    Torch implementation of the SWD (or sliced OT loss? how do you want to call it?)

    https://github.com/PythonOT/POT/issues/225

    How has this been tested (if it applies)

    Added a few unittests, needs to be tested further (WIP)

    Checklist

    • [ ] The documentation is up-to-date with the changes I made.
    • [x] I have read the CONTRIBUTING document.
    • [ ] All tests passed, and additional code has been covered with new tests.
    opened by AdrienCorenflos 16
  • [MRG] Improved docs and changed scipy version

    [MRG] Improved docs and changed scipy version

    I changed the scipy version requirements since version scipy 1.2.1 made my POT crash (cannot remember on which call, sorry, it happened while building the docs) and the issue was fixed when upgrading to scipy 1.3

    Apart from that, the main goal of this PR is to homogenize a bit the presentation in the docs.

    opened by rtavenar 15
  • fail when using

    fail when using "pip install POT"

    When I use "pip install POT", it failed. It depended on Cython. However, it seems that it forgets to tell pip that it depends on Cython.

    I solve this problem by install Cython first. However, if we write both Cython and POT into requirements.txt, the installation will fail.

    Could anyone solve that?

    documentation 
    opened by Adoni 15
  • [MRG] Add Unbalanced KL Wasserstein distance + barycenter

    [MRG] Add Unbalanced KL Wasserstein distance + barycenter

    new unbalanced module for UOT with KL relaxation with the funcs:

    • sinkhorn_unbalanced: generalized Sinkhorn to compute W

    • barycenter_unbalanced: unbalanced Wasserstein barycenter

    • Tests of convergence for both algorithms

    • Examples plot_UOT_1D and plot_UOT_barycenter_1D with unbalanced gaussian distributions.

    new feature 
    opened by hichamjanati 14
  • An Error (RuntimeWarning: invalid value encountered in log) in ot.da.SinkhornL1lL2 after some iterations

    An Error (RuntimeWarning: invalid value encountered in log) in ot.da.SinkhornL1lL2 after some iterations

    Using ot.da.SinkhornL1l2Transport for a domain adaptation problem, I faced an error as follows:

    Datasets used:

    Xs.txt Xt.txt ys.txt

    ** To Reproduce**

    If you download the input files in C:\ , then the code is:

    import numpy as np
    import to
    
    Xs = np.loadtxt("C: / Xs.txt").reshape(604, 5)
    Xt = np.loadtxt("C: / Xt.txt").reshape(601, 5)
    ys = np.loadtxt("C: / ys.txt")
    
    ot_base = ot.da.SinkhornL1l2Transport(reg_e=10000, reg_cl=100, max_iter=100, verbose=True)
    ot_base.fit(Xs=Xs, ys=ys, Xt=Xt)
    

    Result and Error

     It.  |Loss        |Relative loss|Absolute loss
    ------------------------------------------------
    0|5.193677e+06|0.000000e+00|0.000000e+00
    1|3.150847e+05|1.548343e+01|4.878593e+06
    2|2.668420e+05|1.807914e-01|4.824274e+04
    3|2.663638e+05|1.795333e-03|4.782117e+02
    4|2.663590e+05|1.786689e-05|4.759007e+00
    5|2.663590e+05|1.312580e-07|3.496174e-02
    6|2.663588e+05|7.339658e-07|1.954982e-01
    7|2.663106e+05|1.808094e-04|4.815146e+01
    
    C:\Users\enayat.aria\PycharmProjects\pythonProject\venv\lib\site-packages\ot\optim.py:357: RuntimeWarning: 
    invalid value encountered in log
    return np.sum(M * G) + reg1 * np.sum(G * np.log(G)) + reg2 * f(G)
    Traceback (most recent call last):
    File "C:\Program Files\JetBrains\PyCharm Community Edition 2021.1.2\plugins\python- 
    ce\helpers\pydev\pydevd.py", line 1483, in _exec
    pydev_imports.execfile(file, globals, locals)  # execute the script
    File "C:\Program Files\JetBrains\PyCharm Community Edition 2021.1.2\plugins\python- 
    ce\helpers\pydev\_pydev_imps\_pydev_execfile.py", line 18, in execfile
    exec(compile(contents+"\n", file, 'exec'), glob, loc)
    File "C:/Users/enayat.aria/PycharmProjects/pythonProject/OT_for_DA.py", line 258, in <module>
    ot_base.fit(Xs=Xs, ys=ys, Xt=Xt)
    File "C:\Users\enayat.aria\PycharmProjects\pythonProject\venv\lib\site-packages\ot\da.py", line 1950, in fit
    returned_ = sinkhorn_l1l2_gl(
    File "C:\Users\enayat.aria\PycharmProjects\pythonProject\venv\lib\site-packages\ot\da.py", line 239, in 
    sinkhorn_l1l2_gl
    return gcg(a, b, M, reg, eta, f, df, G0=None, numItermax=numItermax,
    File "C:\Users\enayat.aria\PycharmProjects\pythonProject\venv\lib\site-packages\ot\optim.py", line 388, in gcg
    G = G + alpha * deltaG
    TypeError: unsupported operand type(s) for *: 'NoneType' and 'float'
    

    Checking the parameters, I found that the G matrix obtained in the optim.py code has negative values in the last iteration; due to the last update.

    Please let me know how to solve the problem, or if I should provide more information.

    Best,

    Environment (please complete the following information):

    • OS (e.g. MacOS, Windows, Linux): Windows 10
    • Python version: 3.9
    • How was POT installed (source, pip, conda): pip
    bug help wanted 
    opened by EnayatAria 12
  • Bugs for GPU based ot.sinkhorn, and very slow speed for GPU based ot.sinkhorn2

    Bugs for GPU based ot.sinkhorn, and very slow speed for GPU based ot.sinkhorn2

    Hi, I met a bug when I intend to use GPU to calculate sinkhorn OT:

    RuntimeError: CUDA error: device-side assert triggered CUDA kernel errors might be asynchronously reported at some other API call,so the stacktrace below might be incorrect. For debugging consider passing CUDA_LAUNCH_BLOCKING=1

    Also I will meet this bug after running ot.sinkhorn2 for a while.

    The errors come from my inside network codes, which is caused by choosing ot.sinkorn. If I choose ot.emd, then I will not meet such an error. Could you please help me? Thanks.

    bug help wanted 
    opened by HelloWorldLTY 1
  • Problem installing POT on Python 3.6

    Problem installing POT on Python 3.6

    when I tried to install POT use the commond "pip install POT", I always meet problem “Could not build wheels for POT, which is required to install pyproject.toml-based projects”

    Collecting POT
      Using cached POT-0.8.2.tar.gz (255 kB)
      Installing build dependencies ... done
      Getting requirements to build wheel ... done
      Preparing metadata (pyproject.toml) ... done
    Requirement already satisfied: numpy>=1.16 in ./anaconda3/envs/py36/lib/python3.6/site-packages (from POT) (1.19.2)
    Requirement already satisfied: scipy>=1.0 in ./anaconda3/envs/py36/lib/python3.6/site-packages (from POT) (1.5.4)
    Building wheels for collected packages: POT
      Building wheel for POT (pyproject.toml) ... error
      ERROR: Command errored out with exit status 1:
       command: /home/ll20/anaconda3/envs/py36/bin/python3 /home/ll20/anaconda3/envs/py36/lib/python3.6/site-packages/pip/_vendor/pep517/in_process/_in_process.py build_wheel /tmp/tmpw4i_wpdh
           cwd: /tmp/pip-install-9kg4vxnm/pot_4e7b690d6a354c238d684ac7e449ad42
      Complete output (346 lines):
      running bdist_wheel
      running build
      running build_py
      creating build
      creating build/lib.linux-x86_64-3.6
      creating build/lib.linux-x86_64-3.6/ot
      copying ot/__init__.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/backend.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/bregman.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/da.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/datasets.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/dr.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/factored.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/gromov.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/optim.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/partial.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/plot.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/regpath.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/sliced.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/smooth.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/stochastic.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/unbalanced.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/utils.py -> build/lib.linux-x86_64-3.6/ot
      copying ot/weak.py -> build/lib.linux-x86_64-3.6/ot
      creating build/lib.linux-x86_64-3.6/ot/helpers
      copying ot/helpers/__init__.py -> build/lib.linux-x86_64-3.6/ot/helpers
      copying ot/helpers/openmp_helpers.py -> build/lib.linux-x86_64-3.6/ot/helpers
      copying ot/helpers/pre_build_helpers.py -> build/lib.linux-x86_64-3.6/ot/helpers
      creating build/lib.linux-x86_64-3.6/ot/lp
      copying ot/lp/__init__.py -> build/lib.linux-x86_64-3.6/ot/lp
      copying ot/lp/cvx.py -> build/lib.linux-x86_64-3.6/ot/lp
      copying ot/lp/solver_1d.py -> build/lib.linux-x86_64-3.6/ot/lp
      running build_ext
      building 'ot.lp.emd_wrap' extension
      C compiler: gcc -pthread -B /home/ll20/anaconda3/envs/py36/compiler_compat -Wl,--sysroot=/ -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC
    
      creating build/temp.linux-x86_64-3.6
      creating build/temp.linux-x86_64-3.6/ot
      creating build/temp.linux-x86_64-3.6/ot/lp
      compile options: '-Iot/lp -I/tmp/pip-build-env-dgob8pab/overlay/lib/python3.6/site-packages/numpy/core/include -I/tmp/pip-install-9kg4vxnm/pot_4e7b690d6a354c238d684ac7e449ad42/ot/lp -I/home/ll20/anaconda3/envs/py36/include/python3.6m -c'
      extra options: '-O3 -fopenmp -DOMP'
      gcc: ot/lp/emd_wrap.cpp
      cc1plus: warning: command line option ‘-Wstrict-prototypes’ is valid for C/ObjC but not for C++ [enabled by default]
      In file included from /tmp/pip-build-env-dgob8pab/overlay/lib/python3.6/site-packages/numpy/core/include/numpy/ndarraytypes.h:1809:0,
                       from /tmp/pip-build-env-dgob8pab/overlay/lib/python3.6/site-packages/numpy/core/include/numpy/ndarrayobject.h:18,
                       from /tmp/pip-build-env-dgob8pab/overlay/lib/python3.6/site-packages/numpy/core/include/numpy/arrayobject.h:4,
                       from ot/lp/emd_wrap.cpp:792:
      /tmp/pip-build-env-dgob8pab/overlay/lib/python3.6/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: #warning "Using deprecated NumPy API, disable it by " "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-Wcpp]
       #warning "Using deprecated NumPy API, disable it by " \
        ^
      gcc: ot/lp/EMD_wrapper.cpp
      cc1plus: warning: command line option ‘-Wstrict-prototypes’ is valid for C/ObjC but not for C++ [enabled by default]
      In file included from /usr/include/c++/4.8.2/cstdint:35:0,
                       from ot/lp/full_bipartitegraph.h:29,
                       from ot/lp/network_simplex_simple.h:67,
                       from ot/lp/EMD_wrapper.cpp:16:
      /usr/include/c++/4.8.2/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
       #error This file requires compiler and library support for the \
        ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h:119:3: error: ‘unordered_map’ in namespace ‘std’ does not name a type
         std::unordered_map<size_t, T> data;
         ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘T lemon_omp::SparseValueVector<T>::operator[](size_t) const’:
      ot/lp/network_simplex_simple_omp.h:102:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::const_iterator it = data.find(id);
                        ^
      ot/lp/network_simplex_simple_omp.h:102:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::const_iterator it = data.find(id);
                                     ^
      ot/lp/network_simplex_simple_omp.h:106:8: error: ‘it’ was not declared in this scope
          if (it == data.end())
              ^
      ot/lp/network_simplex_simple_omp.h:106:14: error: ‘data’ was not declared in this scope
          if (it == data.end())
                    ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘lemon_omp::ProxyObject<T>::operator T()’:
      ot/lp/network_simplex_simple_omp.h:142:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                        ^
      ot/lp/network_simplex_simple_omp.h:142:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                                     ^
      ot/lp/network_simplex_simple_omp.h:146:8: error: ‘it’ was not declared in this scope
          if (it == _v->data.end())
              ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘void lemon_omp::ProxyObject<T>::operator+=(T)’:
      ot/lp/network_simplex_simple_omp.h:156:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                        ^
      ot/lp/network_simplex_simple_omp.h:156:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                                     ^
      ot/lp/network_simplex_simple_omp.h:160:8: error: ‘it’ was not declared in this scope
          if (it == _v->data.end())
              ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘void lemon_omp::ProxyObject<T>::operator-=(T)’:
      ot/lp/network_simplex_simple_omp.h:175:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                        ^
      ot/lp/network_simplex_simple_omp.h:175:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                                     ^
      ot/lp/network_simplex_simple_omp.h:179:8: error: ‘it’ was not declared in this scope
          if (it == _v->data.end())
              ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In member function ‘Number lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::totalCost() const’:
      ot/lp/network_simplex_simple_omp.h:1006:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, Value>::const_iterator it;
                        ^
      ot/lp/network_simplex_simple_omp.h:1006:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, Value>::const_iterator it;
                                     ^
      ot/lp/network_simplex_simple_omp.h:1010:9: error: ‘it’ was not declared in this scope
          for (it = _flow.data.begin(); it!=_flow.data.end(); ++it)
               ^
      In file included from ot/lp/EMD_wrapper.cpp:16:0:
      ot/lp/network_simplex_simple.h: In instantiation of ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::NetworkSimplexSimple(const GR&, bool, int, ArcsType, size_t) [with GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int; size_t = long unsigned int]’:
      ot/lp/EMD_wrapper.cpp:57:116:   required from here
      ot/lp/network_simplex_simple.h:523:18: warning: ‘lemon::NetworkSimplexSimple<lemon::FullBipartiteDigraph, double, double, unsigned int>::_init_nb_arcs’ will be initialized after [-Wreorder]
               ArcsType _init_nb_arcs;
                        ^
      ot/lp/network_simplex_simple.h:365:21: warning:   ‘const Value lemon::NetworkSimplexSimple<lemon::FullBipartiteDigraph, double, double, unsigned int>::MAX’ [-Wreorder]
               const Value MAX;
                           ^
      ot/lp/network_simplex_simple.h:236:9: warning:   when initialized here [-Wreorder]
               NetworkSimplexSimple(const GR& graph, bool arc_mixing, int nbnodes, ArcsType nb_arcs, size_t maxiters) :
               ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::NetworkSimplexSimple(const GR&, bool, int, ArcsType, size_t, int) [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int; size_t = long unsigned int]’:
      ot/lp/EMD_wrapper.cpp:159:128:   required from here
      ot/lp/network_simplex_simple_omp.h:661:12: warning: ‘lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::_init_nb_arcs’ will be initialized after [-Wreorder]
         ArcsType _init_nb_arcs;
                  ^
      ot/lp/network_simplex_simple_omp.h:392:15: warning:   ‘const Value lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::MAX’ [-Wreorder]
         const Value MAX;
                     ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h:247:3: warning:   when initialized here [-Wreorder]
         NetworkSimplexSimple(const GR& graph, bool arc_mixing, int nbnodes, ArcsType nb_arcs, size_t maxiters = 0, int numThreads=-1) :
         ^
      In file included from ot/lp/EMD_wrapper.cpp:16:0:
      ot/lp/network_simplex_simple.h: In instantiation of ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::ProblemType lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::start() [with PivotRuleImpl = lemon::NetworkSimplexSimple<lemon::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int]’:
      ot/lp/network_simplex_simple.h:1419:25:   required from ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::ProblemType lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::start() [with GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int]’
      ot/lp/network_simplex_simple.h:700:26:   required from ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::ProblemType lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::run() [with GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int]’
      ot/lp/EMD_wrapper.cpp:97:21:   required from here
      ot/lp/network_simplex_simple.h:1436:434: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘size_t {aka long unsigned int}’ [-Wformat=]
                           sprintf( errMess, "RESULT MIGHT BE INACURATE\nMax number of iteration reached, currently \%d. Sometimes iterations go on in cycle even though the solution has been reached, to check if it's the case here have a look at the minimal reduced cost. If it is very close to machine precision, you might actually have the correct solution, if not try setting the maximum number of iterations a bit higher\n",iter_number );
                                                                                                                                                                                                                                                                                                                                                                                                                                                        ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::ProxyObject<T>& lemon_omp::ProxyObject<T>::operator=(const T&) [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:1145:16:   required from ‘bool lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::init() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:833:14:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:134:13: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
           _v->data[_idx] = v;
                   ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with PivotRuleImpl = lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’:
      ot/lp/network_simplex_simple_omp.h:1555:16:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:838:17:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:1614:419: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘size_t {aka long unsigned int}’ [-Wformat=]
            sprintf( errMess, "RESULT MIGHT BE INACURATE\nMax number of iteration reached, currently \%d. Sometimes iterations go on in cycle even though the solution has been reached, to check if it's the case here have a look at the minimal reduced cost. If it is very close to machine precision, you might actually have the correct solution, if not try setting the maximum number of iterations a bit higher\n",iter_number );
                                                                                                                                                                                                                                                                                                                                                                                                                                         ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::ProxyObject<T>::operator T() [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:1659:19:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with PivotRuleImpl = lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:1555:16:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:838:17:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:146:11: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
          if (it == _v->data.end())
                 ^
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘void lemon_omp::ProxyObject<T>::operator+=(T) [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:1302:19:   required from ‘void lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::changeFlow(bool) [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:1595:23:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with PivotRuleImpl = lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:1555:16:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:838:17:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:160:11: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
          if (it == _v->data.end())
                 ^
      ot/lp/network_simplex_simple_omp.h:161:13: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
           _v->data[_idx] = val;
                   ^
      ot/lp/network_simplex_simple_omp.h:166:6: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
            _v->data.erase(it);
            ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘lemon_omp::ProxyObject<T>::operator T() [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:150:3: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘T lemon_omp::SparseValueVector<T>::operator[](size_t) const [with T = double; size_t = long unsigned int]’:
      ot/lp/network_simplex_simple_omp.h:110:3: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^
      cc1plus: warning: command line option ‘-Wstrict-prototypes’ is valid for C/ObjC but not for C++ [enabled by default]
      In file included from /usr/include/c++/4.8.2/cstdint:35:0,
                       from ot/lp/full_bipartitegraph.h:29,
                       from ot/lp/network_simplex_simple.h:67,
                       from ot/lp/EMD_wrapper.cpp:16:
      /usr/include/c++/4.8.2/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
       #error This file requires compiler and library support for the \
        ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h:119:3: error: ‘unordered_map’ in namespace ‘std’ does not name a type
         std::unordered_map<size_t, T> data;
         ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘T lemon_omp::SparseValueVector<T>::operator[](size_t) const’:
      ot/lp/network_simplex_simple_omp.h:102:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::const_iterator it = data.find(id);
                        ^
      ot/lp/network_simplex_simple_omp.h:102:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::const_iterator it = data.find(id);
                                     ^
      ot/lp/network_simplex_simple_omp.h:106:8: error: ‘it’ was not declared in this scope
          if (it == data.end())
              ^
      ot/lp/network_simplex_simple_omp.h:106:14: error: ‘data’ was not declared in this scope
          if (it == data.end())
                    ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘lemon_omp::ProxyObject<T>::operator T()’:
      ot/lp/network_simplex_simple_omp.h:142:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                        ^
      ot/lp/network_simplex_simple_omp.h:142:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                                     ^
      ot/lp/network_simplex_simple_omp.h:146:8: error: ‘it’ was not declared in this scope
          if (it == _v->data.end())
              ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘void lemon_omp::ProxyObject<T>::operator+=(T)’:
      ot/lp/network_simplex_simple_omp.h:156:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                        ^
      ot/lp/network_simplex_simple_omp.h:156:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                                     ^
      ot/lp/network_simplex_simple_omp.h:160:8: error: ‘it’ was not declared in this scope
          if (it == _v->data.end())
              ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘void lemon_omp::ProxyObject<T>::operator-=(T)’:
      ot/lp/network_simplex_simple_omp.h:175:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                        ^
      ot/lp/network_simplex_simple_omp.h:175:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, T>::iterator it = _v->data.find(_idx);
                                     ^
      ot/lp/network_simplex_simple_omp.h:179:8: error: ‘it’ was not declared in this scope
          if (it == _v->data.end())
              ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In member function ‘Number lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::totalCost() const’:
      ot/lp/network_simplex_simple_omp.h:1006:18: error: ‘unordered_map’ in namespace ‘std’ does not name a type
          typename std::unordered_map<size_t, Value>::const_iterator it;
                        ^
      ot/lp/network_simplex_simple_omp.h:1006:31: error: expected unqualified-id before ‘<’ token
          typename std::unordered_map<size_t, Value>::const_iterator it;
                                     ^
      ot/lp/network_simplex_simple_omp.h:1010:9: error: ‘it’ was not declared in this scope
          for (it = _flow.data.begin(); it!=_flow.data.end(); ++it)
               ^
      In file included from ot/lp/EMD_wrapper.cpp:16:0:
      ot/lp/network_simplex_simple.h: In instantiation of ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::NetworkSimplexSimple(const GR&, bool, int, ArcsType, size_t) [with GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int; size_t = long unsigned int]’:
      ot/lp/EMD_wrapper.cpp:57:116:   required from here
      ot/lp/network_simplex_simple.h:523:18: warning: ‘lemon::NetworkSimplexSimple<lemon::FullBipartiteDigraph, double, double, unsigned int>::_init_nb_arcs’ will be initialized after [-Wreorder]
               ArcsType _init_nb_arcs;
                        ^
      ot/lp/network_simplex_simple.h:365:21: warning:   ‘const Value lemon::NetworkSimplexSimple<lemon::FullBipartiteDigraph, double, double, unsigned int>::MAX’ [-Wreorder]
               const Value MAX;
                           ^
      ot/lp/network_simplex_simple.h:236:9: warning:   when initialized here [-Wreorder]
               NetworkSimplexSimple(const GR& graph, bool arc_mixing, int nbnodes, ArcsType nb_arcs, size_t maxiters) :
               ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::NetworkSimplexSimple(const GR&, bool, int, ArcsType, size_t, int) [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int; size_t = long unsigned int]’:
      ot/lp/EMD_wrapper.cpp:159:128:   required from here
      ot/lp/network_simplex_simple_omp.h:661:12: warning: ‘lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::_init_nb_arcs’ will be initialized after [-Wreorder]
         ArcsType _init_nb_arcs;
                  ^
      ot/lp/network_simplex_simple_omp.h:392:15: warning:   ‘const Value lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::MAX’ [-Wreorder]
         const Value MAX;
                     ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h:247:3: warning:   when initialized here [-Wreorder]
         NetworkSimplexSimple(const GR& graph, bool arc_mixing, int nbnodes, ArcsType nb_arcs, size_t maxiters = 0, int numThreads=-1) :
         ^
      In file included from ot/lp/EMD_wrapper.cpp:16:0:
      ot/lp/network_simplex_simple.h: In instantiation of ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::ProblemType lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::start() [with PivotRuleImpl = lemon::NetworkSimplexSimple<lemon::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int]’:
      ot/lp/network_simplex_simple.h:1419:25:   required from ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::ProblemType lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::start() [with GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int]’
      ot/lp/network_simplex_simple.h:700:26:   required from ‘lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::ProblemType lemon::NetworkSimplexSimple<GR, V, C, NodesType, ArcsType>::run() [with GR = lemon::FullBipartiteDigraph; V = double; C = double; NodesType = unsigned int; ArcsType = long int]’
      ot/lp/EMD_wrapper.cpp:97:21:   required from here
      ot/lp/network_simplex_simple.h:1436:434: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘size_t {aka long unsigned int}’ [-Wformat=]
                           sprintf( errMess, "RESULT MIGHT BE INACURATE\nMax number of iteration reached, currently \%d. Sometimes iterations go on in cycle even though the solution has been reached, to check if it's the case here have a look at the minimal reduced cost. If it is very close to machine precision, you might actually have the correct solution, if not try setting the maximum number of iterations a bit higher\n",iter_number );
                                                                                                                                                                                                                                                                                                                                                                                                                                                        ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::ProxyObject<T>& lemon_omp::ProxyObject<T>::operator=(const T&) [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:1145:16:   required from ‘bool lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::init() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:833:14:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:134:13: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
           _v->data[_idx] = v;
                   ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with PivotRuleImpl = lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’:
      ot/lp/network_simplex_simple_omp.h:1555:16:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:838:17:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:1614:419: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘size_t {aka long unsigned int}’ [-Wformat=]
            sprintf( errMess, "RESULT MIGHT BE INACURATE\nMax number of iteration reached, currently \%d. Sometimes iterations go on in cycle even though the solution has been reached, to check if it's the case here have a look at the minimal reduced cost. If it is very close to machine precision, you might actually have the correct solution, if not try setting the maximum number of iterations a bit higher\n",iter_number );
                                                                                                                                                                                                                                                                                                                                                                                                                                         ^
      In file included from ot/lp/EMD_wrapper.cpp:17:0:
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘lemon_omp::ProxyObject<T>::operator T() [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:1659:19:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with PivotRuleImpl = lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:1555:16:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:838:17:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:146:11: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
          if (it == _v->data.end())
                 ^
      ot/lp/network_simplex_simple_omp.h: In instantiation of ‘void lemon_omp::ProxyObject<T>::operator+=(T) [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:1302:19:   required from ‘void lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::changeFlow(bool) [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:1595:23:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with PivotRuleImpl = lemon_omp::NetworkSimplexSimple<lemon_omp::FullBipartiteDigraph, double, double, unsigned int>::BlockSearchPivotRule; GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:1555:16:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::start() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/network_simplex_simple_omp.h:838:17:   required from ‘lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::ProblemType lemon_omp::NetworkSimplexSimple<GR, V, C, ArcsType>::run() [with GR = lemon_omp::FullBipartiteDigraph; V = double; C = double; ArcsType = unsigned int]’
      ot/lp/EMD_wrapper.cpp:199:21:   required from here
      ot/lp/network_simplex_simple_omp.h:160:11: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
          if (it == _v->data.end())
                 ^
      ot/lp/network_simplex_simple_omp.h:161:13: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
           _v->data[_idx] = val;
                   ^
      ot/lp/network_simplex_simple_omp.h:166:6: error: ‘class lemon_omp::SparseValueVector<double>’ has no member named ‘data’
            _v->data.erase(it);
            ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘lemon_omp::ProxyObject<T>::operator T() [with T = double]’:
      ot/lp/network_simplex_simple_omp.h:150:3: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^
      ot/lp/network_simplex_simple_omp.h: In member function ‘T lemon_omp::SparseValueVector<T>::operator[](size_t) const [with T = double; size_t = long unsigned int]’:
      ot/lp/network_simplex_simple_omp.h:110:3: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^
      error: Command "gcc -pthread -B /home/ll20/anaconda3/envs/py36/compiler_compat -Wl,--sysroot=/ -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -Iot/lp -I/tmp/pip-build-env-dgob8pab/overlay/lib/python3.6/site-packages/numpy/core/include -I/tmp/pip-install-9kg4vxnm/pot_4e7b690d6a354c238d684ac7e449ad42/ot/lp -I/home/ll20/anaconda3/envs/py36/include/python3.6m -c ot/lp/EMD_wrapper.cpp -o build/temp.linux-x86_64-3.6/ot/lp/EMD_wrapper.o -O3 -fopenmp -DOMP" failed with exit status 1
      ----------------------------------------
      ERROR: Failed building wheel for POT
    Failed to build POT
    ERROR: Could not build wheels for POT, which is required to install pyproject.toml-based projects```
    
    bug help wanted 
    opened by LL0912 1
  • Negative Gromov-Wasserstein distance

    Negative Gromov-Wasserstein distance

    Hi,

    Thank you for the extremely helpful software! Sometimes I encounter a negative value of gw_dist returned by gromov.entropic_gromov_wasserstein() function:

    gw1, log1 = ot.gromov.entropic_gromov_wasserstein(
        C1, C2, p, q, 'square_loss', epsilon=0.01, log=True, verbose=True)
    print(log1['gw_dist'])
    

    However, from my understanding, the distance part has to be nonnegative given the square loss. Could you help me with my confusion? If helpful at all, my cost matrices are nonnegative, symmetric integer matrices of sizes 267267 and 250250, and the marginals p and q are uniform. The negative gw_dist value appears for epsilon=0.01, but not for epsilon=0.02 or 0.05.

    The version of packages is:

    macOS-10.16-x86_64-i386-64bit
    Python 3.8.8 (default, Apr 13 2021, 12:59:45) 
    [Clang 10.0.0 ]
    NumPy 1.20.1
    SciPy 1.6.2
    POT 0.8.1.0
    
    opened by WenjunZHAOwO 4
  • [WIP] Semi-relaxed (fused) gromov-wasserstein divergence with updates of current gromov-wasserstein solvers and dependencies

    [WIP] Semi-relaxed (fused) gromov-wasserstein divergence with updates of current gromov-wasserstein solvers and dependencies

    Types of changes

    • Integration of the semi-relaxed (fused) gromov-wasserstein solvers using conditional gradients --- Related new functions in gromov.py: init_matrix_semirelaxed / semirelaxed_gromov_wasserstein / semirelaxed_gromov_wasserstein2 / semirelaxed_fused_gromov_wasserstein/ semirelaxed_fused_gromov_wasserstein2/ --- Related new functions in optim.py: solve_semirelaxed_gromov_linesearch.

    • Factorization of the conditional gradient solvers in optim.py to take as entry any kind of linear program solver for the conditional gradient direction, and any kind of line search solver for the optimal line search step. --- Related new functions in optim.py: generic_cg / Might replace functions in optim.py: cg, gcg (an instance of how to replace cgc is given in a potentially temporary function named new_gcg)

    • New factoring for the (fused) gromov-wasserstein functions to fit the new function generic_cg, and support asymmetric matrices as started in another pull request [PR: Gromov-Wasserstein with asymmetric cost matrices #399] --- Related modified functions in gromov.py: gromov_wasserstein / gromov_wasserstein2 / fused_gromov_wasserstein / fused_gromov_wasserstein2 / gromov_barycenters / fgw_barycenters --- Related new functions in optim.py: solve_gromov_linesearch (generalizing the line seach coded in solve_linesearch, plus speeding up the function).

    • Updates of the (fused) gromov-wasserstein dictionary learning functions to leverage the new (fused) gromov-wasserstein solvers to also support asymmetric matrices.

    [ TO DO]

    • update test_gromov.py
    • update related examples
    • update dependencies with cg and gcg if necessary.
    • add semi-relaxed (fused) gromov-wasserstein barycenters ?

    Motivation and context / Related issue

    • The current conditional gradient solver (optim.py/cg) does not allow an easy integration of new lp solver, not new line search methods. The upgrade to the function generic_cg allows a such flexiblity.

    • The integration of the semi-relaxed fgw (srfgw) requires new lp solver and line-search solver, hence fits well with the function generic_cg. Moreover the implementation srfgw supports symmetric and asymmetric matrices, so fgw solvers have been updated to support asymmetric matrices for the sake of consistency.

    • The implementation of the (fused) gromov-wasserstein dictionary learning was also restrained to symmetric matrices. Actually wrong if asymmetric matrices were provided or if the dictionary atoms were not projected onto the set of symmetric matrices.

    How has this been tested (if it applies)

    • Test to come.

    PR checklist

    • [x] I have read the CONTRIBUTING document.
    • [ ] The documentation is up-to-date with the changes I made (check build artifacts).
    • [ ] All tests passed, and additional code has been covered with new tests.
    • [ ] I have added the PR and Issue fix to the RELEASES.md file.
    opened by cedricvincentcuaz 1
  • [WIP] Gromov-Wasserstein with asymmetric cost matrices

    [WIP] Gromov-Wasserstein with asymmetric cost matrices

    Types of changes

    • Support of a wider class of arguments for Gromov-Wasserstein functions
    • Signature of 2 functions modified
    • Docstrings updated

    Motivation and context / Related issue

    In [12] "Gromov-Wasserstein Averaging of Kernel and Distance Matrices", the authors make no explicit assumption about the symmetry of the cost mastrices C and C'. However, their formula (9) for the computation of the gradient misses at least a 2 factor in the case of symmetric matrices, and even a second term in the case of asymmetric matrices, as explained in subsection 5.1 of "Multilingual Alignment of Word Embedding Spaces", Dan Meller and Gonzague de Carpentier, 2021 (https://www.researchgate.net/publication/357505092_Multilingual_alignment_of_word_embedding_spaces). In the code of ot/gromov.py, the 2 factor has been corrected, but it is not sufficient to support asymmetric cost matrices, which can be useful in the case of directed graphs for example. This contribution corrects the expression of the gradient in ot.gromov.gwggrad to support asymmetric distance matrices, by adding the appropriate term instead of just multiplying by 2.

    How has this been tested (if it applies)

    PR checklist

    • [x] I have read the CONTRIBUTING document.
    • [x] The documentation is up-to-date with the changes I made (check build artifacts).
    • [x] All tests passed, and additional code has been covered with new tests.
    • [x] I have added the PR and Issue fix to the RELEASES.md file.
    opened by decarpentierg 3
Releases(0.8.2)
Owner
Python Optimal Transport
Python Optimal Transport
OCR system for Arabic language that converts images of typed text to machine-encoded text.

Arabic OCR OCR system for Arabic language that converts images of typed text to machine-encoded text. The system currently supports only letters (29 l

Hussein Youssef 144 Jan 05, 2023
color detection using python

colordetection color detection using python In this color detection Python project, we are going to build an application through which you can automat

Ruchith Kumar 1 Nov 04, 2021
基于Paddle框架的PSENet复现

PSENet-Paddle 基于Paddle框架的PSENet复现 本项目基于paddlepaddle框架复现PSENet,并参加百度第三届论文复现赛,将在2021年5月15日比赛完后提供AIStudio链接~敬请期待 AIStudio链接 参考项目: whai362-PSENet 环境配置 本项目

QuanHao Guo 4 Apr 24, 2022
[BMVC'21] Official PyTorch Implementation of Grounded Situation Recognition with Transformers

Grounded Situation Recognition with Transformers Paper | Model Checkpoint This is the official PyTorch implementation of Grounded Situation Recognitio

Junhyeong Cho 18 Jul 19, 2022
ERQA - Edge Restoration Quality Assessment

ERQA - a full-reference quality metric designed to analyze how good image and video restoration methods (SR, deblurring, denoising, etc) are restoring real details.

MSU Video Group 27 Dec 17, 2022
OpenGait is a flexible and extensible gait recognition project

A flexible and extensible framework for gait recognition. You can focus on designing your own models and comparing with state-of-the-arts easily with the help of OpenGait.

Shiqi Yu 335 Dec 22, 2022
Play the Namibian game of Owela against a terrible AI. Built using Django and htmx.

Owela Club A Django project for playing the Namibian game of Owela against a dumb AI. Built following the rules described on the Mancala World wiki pa

Adam Johnson 18 Jun 01, 2022
Source Code for AAAI 2022 paper "Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching"

Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching This repository is an official implementation of

HKUST-KnowComp 13 Sep 08, 2022
Open Source Computer Vision Library

OpenCV: Open Source Computer Vision Library Resources Homepage: https://opencv.org Courses: https://opencv.org/courses Docs: https://docs.opencv.org/m

OpenCV 65.7k Jan 03, 2023
Distort a video using Seam Carving (video) and Vibrato effect (sound)

Distort videos Applies a Seam Carving algorithm (aka liquid rescale) on every frame of a video, and a vibrato effect on the audio to distort the video

AlexZeGamer 6 Dec 06, 2022
A community-supported supercharged version of paperless: scan, index and archive all your physical documents

Paperless-ngx Paperless-ngx is a document management system that transforms your physical documents into a searchable online archive so you can keep,

5.2k Jan 04, 2023
This is a repository to learn and get more computer vision skills, make robotics projects integrating the computer vision as a perception tool and create a lot of awesome advanced controllers for the robots of the future.

This is a repository to learn and get more computer vision skills, make robotics projects integrating the computer vision as a perception tool and create a lot of awesome advanced controllers for the

Elkin Javier Guerra Galeano 17 Nov 03, 2022
ISI's Optical Character Recognition (OCR) software for machine-print and handwriting data

VistaOCR ISI's Optical Character Recognition (OCR) software for machine-print and handwriting data Publications "How to Efficiently Increase Resolutio

ISI Center for Vision, Image, Speech, and Text Analytics 21 Dec 08, 2021
Drowsiness Detection and Alert System

A countless number of people drive on the highway day and night. Taxi drivers, bus drivers, truck drivers, and people traveling long-distance suffer from lack of sleep.

Astitva Veer Garg 4 Aug 01, 2022
Code for generating synthetic text images as described in "Synthetic Data for Text Localisation in Natural Images", Ankush Gupta, Andrea Vedaldi, Andrew Zisserman, CVPR 2016.

SynthText Code for generating synthetic text images as described in "Synthetic Data for Text Localisation in Natural Images", Ankush Gupta, Andrea Ved

Ankush Gupta 1.8k Dec 28, 2022
Code for CVPR'2022 paper ✨ "Predict, Prevent, and Evaluate: Disentangled Text-Driven Image Manipulation Empowered by Pre-Trained Vision-Language Model"

PPE ✨ Repository for our CVPR'2022 paper: Predict, Prevent, and Evaluate: Disentangled Text-Driven Image Manipulation Empowered by Pre-Trained Vision-

Zipeng Xu 34 Nov 28, 2022
ocroseg - This is a deep learning model for page layout analysis / segmentation.

ocroseg This is a deep learning model for page layout analysis / segmentation. There are many different ways in which you can train and run it, but by

NVIDIA Research Projects 71 Dec 06, 2022
graph learning code for ogb

The final code for OGB Installation Requirements: ogb=1.3.1 torch=1.7.0 torch-geometric=1.7.0 torch-scatter=2.0.6 torch-sparse=0.6.9 Baseline models T

PierreHao 20 Nov 10, 2022
An unofficial implementation of the paper "AutoVC: Zero-Shot Voice Style Transfer with Only Autoencoder Loss".

AutoVC: Zero-Shot Voice Style Transfer with Only Autoencoder Loss This is an unofficial implementation of AutoVC based on the official one. The reposi

Chien-yu Huang 27 Jun 16, 2022
The virtual calculator will be above the live streaming from your camera

The virtual calculator is above the live streaming from my camera usb , the program first detect my hand and in each frame calculate the distance between two finger ,if the distance is lower than the

gasbaoui mohammed al amine 5 Jul 01, 2022