Incorrect total EMD value but correct flow values

[adam-ah]

When calculating the optimal flow the algorithm is correct but seems like the EMD is a little off from what I would correctly get with flow_matrix * distance_matrix

Distance matrix:

[[2.2360679775e+00 8.7952156412e+03 3.1622776602e+00]
 [8.7964805272e+03 0.0000000000e+00 8.7921069089e+03]
 [0.0000000000e+00 8.7964805272e+03 5.0000000000e+00]]

arr1:

[0.5 0.5 0.0]

arr2:

[0.0 0.5 0.5]

emd =  pyemd.emd_with_flow(arr1, arr2, distance_matrix)
= (1.57896825463524, [[0.0, 0.0, 0.5], [0.0, 0.5, 0.0], [0.0, 0.0, 0.0]])

The final value should be

np.sum(np.multiply(emd[1], distance_matrix))
= 0.5 * 3.1622776602 = 1.5811388301 (=sqrt(2.5))

but instead it is 1.57896825463524 (err=0.002170575465)

Types (distance, arr1, arr2): {dtype} float64
System: Mac OS X, 10.13.4
PIP pyemd: 0.5.1

Seems like too big of an error to be explained by floating point precision. Also, for floating point precision error the calculated flow should be off as well, but that seems to be accurate.

[adam-ah]

@madras380 FYI

[wmayner]

I'm not sure of the cause, but my guess is that it has to do with the iterative min-cost flow algorithm in the underlying C++ library. Unfortunately I don't have time to look into this right now.

[HaidYi]

@adam-ah The value is slightly different is because the definition of emd given in Fast and Robust Earth Mover’s Distances is different from the standard emd distance.