Source code for paper A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem
In order to build our program and run our code, you should first install CMake (>= 3.12) and Python 3 (>= 3.6). It is recommended to install pip.
sudo apt update && sudo apt install -y cmake python3 python3-pip
We use pybind11 library to build our code, and we use functions in Python Optimal Library (POT) as a baseline to measure our performance. It is recommended to run the following line in a virtual environment such as Conda.
python3 -m pip install "pybind11[global]" pot
To build our project through CMake, simply switch to the root directory of our project and execute the following
mkdir -p build && cd build && cmake .. && make
To install it, continue executing the following
make install
-
tree = make_emd(points, flows, dist_func)
builds a new dynamic optimal transport system. Points have to benp.array
instances in shape(n, d)
respectively, wheren
denotes the number of points andd
denotes the dimension of the space. Flows have to be a 1Dnp.array
of lengthn
, where the sum of all entries have to be exactly0
. Ifflows[i] > 0
, then pointi
is a supply point, otherwisei
is a demand point.dist_func
should be a callable object that takes two 1Dnp.array
with lengthd
and return their distance. All types have to be integers, i.e.,np.int32
ornp.int64
. The dynamic optimal transport system is stored intree
. Points are labeled from0
ton - 1
respectively. -
tree.modify(point_label, new_position)
moves the point labeled withpoint_label
to a new pointnew_position
in the current space$\mathbb R^d$ . -
tree.sendflow(supply_label, demand_label, flow)
sendsflow
amount of flow from point labeled assupply_label
to point labeled asdemand_label
. -
new_label = tree.insert(new_position)
inserts a new point into the system, and it is labeled asnew_label
. -
tree.delete(label)
deletes the point labeled aslabel
from the current system.