From 8e4f3d151818b78a29d11cdc6ca171947bfd6dd9 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 3 Mar 2020 15:33:17 +0100 Subject: update wasserstein distance with pot so that it can return optimal matching now! --- src/python/doc/wasserstein_distance_user.rst | 24 ++++++++++ src/python/gudhi/wasserstein.py | 69 ++++++++++++++++++++++------ src/python/test/test_wasserstein_distance.py | 31 +++++++++---- 3 files changed, 102 insertions(+), 22 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 94b454e2..d3daa318 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -47,3 +47,27 @@ The output is: .. testoutput:: Wasserstein distance value = 1.45 + +We can also have access to the optimal matching by letting `matching=True`. +It is encoded as a list of indices (i,j), meaning that the i-th point in X +is mapped to the j-th point in Y. +An index of -1 represents the diagonal. + +.. testcode:: + + import gudhi.wasserstein + import numpy as np + + diag1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) + diag2 = np.array([[2.8, 4.45], [5, 6], [9.5, 14.1]]) + cost, matching = gudhi.wasserstein.wasserstein_distance(diag1, diag2, matching=True, order=1., internal_p=2.) + + message = "Wasserstein distance value = %.2f, optimal matching: %s" %(cost, matching) + print(message) + +The output is: + +.. testoutput:: + + Wasserstein distance value = 2.15, optimal matching: [(0, 0), (1, 2), (2, -1), (-1, 1)] + diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 13102094..ba0f7343 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -62,14 +62,39 @@ def _perstot(X, order, internal_p): return (np.sum(np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order))**(1./order) -def wasserstein_distance(X, Y, order=2., internal_p=2.): +def _clean_match(match, n, m): ''' - :param X: (n x 2) numpy.array encoding the (finite points of the) first diagram. Must not contain essential points (i.e. with infinite coordinate). + :param match: a list of the form [(i,j) ...] + :param n: int, size of the first dgm + :param m: int, size of the second dgm + :return: a modified version of match where indices greater than n, m are replaced by -1, encoding the diagonal. + and (-1, -1) are removed + ''' + new_match = [] + for i,j in match: + if i >= n: + if j < m: + new_match.append((-1, j)) + elif j >= m: + if i < n: + new_match.append((i,-1)) + else: + new_match.append((i,j)) + return new_match + + +def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): + ''' + :param X: (n x 2) numpy.array encoding the (finite points of the) first diagram. Must not contain essential points + (i.e. with infinite coordinate). :param Y: (m x 2) numpy.array encoding the second diagram. + :param matching: if True, computes and returns the optimal matching between X and Y, encoded as... :param order: exponent for Wasserstein; Default value is 2. - :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); Default value is 2 (Euclidean norm). - :returns: the Wasserstein distance of order q (1 <= q < infinity) between persistence diagrams with respect to the internal_p-norm as ground metric. - :rtype: float + :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); + Default value is 2 (Euclidean norm). + :returns: the Wasserstein distance of order q (1 <= q < infinity) between persistence diagrams with + respect to the internal_p-norm as ground metric. + If matching is set to True, also returns the optimal matching between X and Y. ''' n = len(X) m = len(Y) @@ -77,21 +102,39 @@ def wasserstein_distance(X, Y, order=2., internal_p=2.): # handle empty diagrams if X.size == 0: if Y.size == 0: - return 0. + if not matching: + return 0. + else: + return 0., [] else: - return _perstot(Y, order, internal_p) + if not matching: + return _perstot(Y, order, internal_p) + else: + return _perstot(Y, order, internal_p), [(-1, j) for j in range(m)] elif Y.size == 0: - return _perstot(X, order, internal_p) + if not matching: + return _perstot(X, order, internal_p) + else: + return _perstot(X, order, internal_p), [(i, -1) for i in range(n)] M = _build_dist_matrix(X, Y, order=order, internal_p=internal_p) - a = np.full(n+1, 1. / (n + m) ) # weight vector of the input diagram. Uniform here. - a[-1] = a[-1] * m # normalized so that we have a probability measure, required by POT - b = np.full(m+1, 1. / (n + m) ) # weight vector of the input diagram. Uniform here. - b[-1] = b[-1] * n # so that we have a probability measure, required by POT + a = np.ones(n+1) # weight vector of the input diagram. Uniform here. + a[-1] = m + b = np.ones(m+1) # weight vector of the input diagram. Uniform here. + b[-1] = n + + if matching: + P = ot.emd(a=a,b=b,M=M, numItermax=2000000) + ot_cost = np.sum(np.multiply(P,M)) + P[P < 0.5] = 0 # trick to avoid numerical issue, could it be improved? + match = np.argwhere(P) + # Now we turn to -1 points encoding the diagonal + match = _clean_match(match, n, m) + return ot_cost ** (1./order) , match # Comptuation of the otcost using the ot.emd2 library. # Note: it is the Wasserstein distance to the power q. # The default numItermax=100000 is not sufficient for some examples with 5000 points, what is a good value? - ot_cost = (n+m) * ot.emd2(a, b, M, numItermax=2000000) + ot_cost = ot.emd2(a, b, M, numItermax=2000000) return ot_cost ** (1./order) diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index 6a6b217b..02a1d2c9 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -51,14 +51,27 @@ def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True): assert wasserstein_distance(diag3, diag4, internal_p=1., order=2.) == approx(np.sqrt(5)) assert wasserstein_distance(diag3, diag4, internal_p=4.5, order=2.) == approx(np.sqrt(5)) - if(not test_infinity): - return + if test_infinity: + diag5 = np.array([[0, 3], [4, np.inf]]) + diag6 = np.array([[7, 8], [4, 6], [3, np.inf]]) - diag5 = np.array([[0, 3], [4, np.inf]]) - diag6 = np.array([[7, 8], [4, 6], [3, np.inf]]) + assert wasserstein_distance(diag4, diag5) == np.inf + assert wasserstein_distance(diag5, diag6, order=1, internal_p=np.inf) == approx(4.) + + + if test_matching: + match = wasserstein_distance(emptydiag, emptydiag, matching=True, internal_p=1., order=2)[1] + assert match == [] + match = wasserstein_distance(emptydiag, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] + assert match == [] + match = wasserstein_distance(emptydiag, diag2, matching=True, internal_p=np.inf, order=2.)[1] + assert match == [(-1, 0), (-1, 1)] + match = wasserstein_distance(diag2, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] + assert match == [(0, -1), (1, -1)] + match = wasserstein_distance(diag1, diag2, matching=True, internal_p=2., order=2.)[1] + assert match == [(0, 0), (1, 1), (2, -1)] + - assert wasserstein_distance(diag4, diag5) == np.inf - assert wasserstein_distance(diag5, diag6, order=1, internal_p=np.inf) == approx(4.) def hera_wrap(delta): def fun(*kargs,**kwargs): @@ -66,8 +79,8 @@ def hera_wrap(delta): return fun def test_wasserstein_distance_pot(): - _basic_wasserstein(pot, 1e-15, test_infinity=False) + _basic_wasserstein(pot, 1e-15, test_infinity=False, test_matching=True) def test_wasserstein_distance_hera(): - _basic_wasserstein(hera_wrap(1e-12), 1e-12) - _basic_wasserstein(hera_wrap(.1), .1) + _basic_wasserstein(hera_wrap(1e-12), 1e-12, test_matching=False) + _basic_wasserstein(hera_wrap(.1), .1, test_matching=False) -- cgit v1.2.3 From 2141ef8adfee531f3eaf822cf4076b9b010e6f94 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 3 Mar 2020 16:22:48 +0100 Subject: correction missing arg in test_wasserstein_distance --- src/python/test/test_wasserstein_distance.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index 02a1d2c9..d0f0323c 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -17,7 +17,7 @@ __author__ = "Theo Lacombe" __copyright__ = "Copyright (C) 2019 Inria" __license__ = "MIT" -def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True): +def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True, test_matching=True): diag1 = np.array([[2.7, 3.7], [9.6, 14.0], [34.2, 34.974]]) diag2 = np.array([[2.8, 4.45], [9.5, 14.1]]) diag3 = np.array([[0, 2], [4, 6]]) -- cgit v1.2.3 From 570a9b83eb3f714bc52735dae289a5195874bf41 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Thu, 5 Mar 2020 15:40:45 +0100 Subject: completed as... --- src/python/gudhi/wasserstein.py | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index ba0f7343..aab0cb3c 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -30,7 +30,9 @@ def _build_dist_matrix(X, Y, order=2., internal_p=2.): :param order: exponent for the Wasserstein metric. :param internal_p: Ground metric (i.e. norm L^p). :returns: (n+1) x (m+1) np.array encoding the cost matrix C. - For 1 <= i <= n, 1 <= j <= m, C[i,j] encodes the distance between X[i] and Y[j], while C[i, m+1] (resp. C[n+1, j]) encodes the distance (to the p) between X[i] (resp Y[j]) and its orthogonal proj onto the diagonal. + For 1 <= i <= n, 1 <= j <= m, C[i,j] encodes the distance between X[i] and Y[j], + while C[i, m+1] (resp. C[n+1, j]) encodes the distance (to the p) between X[i] (resp Y[j]) + and its orthogonal proj onto the diagonal. note also that C[n+1, m+1] = 0 (it costs nothing to move from the diagonal to the diagonal). ''' Xdiag = _proj_on_diag(X) @@ -88,7 +90,9 @@ def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): :param X: (n x 2) numpy.array encoding the (finite points of the) first diagram. Must not contain essential points (i.e. with infinite coordinate). :param Y: (m x 2) numpy.array encoding the second diagram. - :param matching: if True, computes and returns the optimal matching between X and Y, encoded as... + :param matching: if True, computes and returns the optimal matching between X and Y, encoded as + a list of tuple [...(i,j)...], meaning the i-th point in X is matched to + the j-th point in Y, with the convention (-1) represents the diagonal. :param order: exponent for Wasserstein; Default value is 2. :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); Default value is 2 (Euclidean norm). -- cgit v1.2.3 From 2eca5c75b1fbd7157e2656b875e730dc5f00f373 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 10 Mar 2020 15:45:45 +0100 Subject: removed P[P < 0.5] thresholding ; as it shouldn't happen anymore. --- src/python/gudhi/wasserstein.py | 1 - 1 file changed, 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index aab0cb3c..e28c63e6 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -130,7 +130,6 @@ def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): if matching: P = ot.emd(a=a,b=b,M=M, numItermax=2000000) ot_cost = np.sum(np.multiply(P,M)) - P[P < 0.5] = 0 # trick to avoid numerical issue, could it be improved? match = np.argwhere(P) # Now we turn to -1 points encoding the diagonal match = _clean_match(match, n, m) -- cgit v1.2.3 From 967ceab26b09ad74e0cff0d84429a766af267f6b Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 10 Mar 2020 16:47:09 +0100 Subject: removed _clean_match and changed matching format, it is now a (n x 2) numpy array --- src/python/gudhi/wasserstein.py | 31 ++++++------------------------- 1 file changed, 6 insertions(+), 25 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index e28c63e6..9efa946e 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -64,34 +64,13 @@ def _perstot(X, order, internal_p): return (np.sum(np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order))**(1./order) -def _clean_match(match, n, m): - ''' - :param match: a list of the form [(i,j) ...] - :param n: int, size of the first dgm - :param m: int, size of the second dgm - :return: a modified version of match where indices greater than n, m are replaced by -1, encoding the diagonal. - and (-1, -1) are removed - ''' - new_match = [] - for i,j in match: - if i >= n: - if j < m: - new_match.append((-1, j)) - elif j >= m: - if i < n: - new_match.append((i,-1)) - else: - new_match.append((i,j)) - return new_match - - def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): ''' :param X: (n x 2) numpy.array encoding the (finite points of the) first diagram. Must not contain essential points (i.e. with infinite coordinate). :param Y: (m x 2) numpy.array encoding the second diagram. :param matching: if True, computes and returns the optimal matching between X and Y, encoded as - a list of tuple [...(i,j)...], meaning the i-th point in X is matched to + a (n x 2) np.array [...[i,j]...], meaning the i-th point in X is matched to the j-th point in Y, with the convention (-1) represents the diagonal. :param order: exponent for Wasserstein; Default value is 2. :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); @@ -114,12 +93,12 @@ def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): if not matching: return _perstot(Y, order, internal_p) else: - return _perstot(Y, order, internal_p), [(-1, j) for j in range(m)] + return _perstot(Y, order, internal_p), np.array([[-1, j] for j in range(m)]) elif Y.size == 0: if not matching: return _perstot(X, order, internal_p) else: - return _perstot(X, order, internal_p), [(i, -1) for i in range(n)] + return _perstot(X, order, internal_p), np.array([[i, -1] for i in range(n)]) M = _build_dist_matrix(X, Y, order=order, internal_p=internal_p) a = np.ones(n+1) # weight vector of the input diagram. Uniform here. @@ -130,9 +109,11 @@ def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): if matching: P = ot.emd(a=a,b=b,M=M, numItermax=2000000) ot_cost = np.sum(np.multiply(P,M)) + P[-1, -1] = 0 # Remove matching corresponding to the diagonal match = np.argwhere(P) # Now we turn to -1 points encoding the diagonal - match = _clean_match(match, n, m) + match[:,0][match[:,0] >= n] = -1 + match[:,1][match[:,1] >= m] = -1 return ot_cost ** (1./order) , match # Comptuation of the otcost using the ot.emd2 library. -- cgit v1.2.3 From 4aea5deab6ce4cbb491f4c9c2b7e9f023efbbe01 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 10 Mar 2020 17:41:38 +0100 Subject: changed output of matching as a (n x 2) array, adapted tests and doc --- src/python/doc/wasserstein_distance_user.rst | 2 +- src/python/gudhi/wasserstein.py | 2 +- src/python/test/test_wasserstein_distance.py | 10 +++++----- 3 files changed, 7 insertions(+), 7 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index d3daa318..9519caa6 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -69,5 +69,5 @@ The output is: .. testoutput:: - Wasserstein distance value = 2.15, optimal matching: [(0, 0), (1, 2), (2, -1), (-1, 1)] + Wasserstein distance value = 2.15, optimal matching: [[0, 0], [1, 2], [2, -1], [-1, 1]] diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 9efa946e..9e4dc7d5 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -88,7 +88,7 @@ def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): if not matching: return 0. else: - return 0., [] + return 0., np.array([]) else: if not matching: return _perstot(Y, order, internal_p) diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index d0f0323c..ca9a4a61 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -61,15 +61,15 @@ def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True, test_mat if test_matching: match = wasserstein_distance(emptydiag, emptydiag, matching=True, internal_p=1., order=2)[1] - assert match == [] + assert np.array_equal(match, np.array([])) match = wasserstein_distance(emptydiag, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] - assert match == [] + assert np.array_equal(match, np.array([])) match = wasserstein_distance(emptydiag, diag2, matching=True, internal_p=np.inf, order=2.)[1] - assert match == [(-1, 0), (-1, 1)] + assert np.array_equal(match , np.array([[-1, 0], [-1, 1]])) match = wasserstein_distance(diag2, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] - assert match == [(0, -1), (1, -1)] + assert np.array_equal(match , np.array([[0, -1], [1, -1]])) match = wasserstein_distance(diag1, diag2, matching=True, internal_p=2., order=2.)[1] - assert match == [(0, 0), (1, 1), (2, -1)] + assert np.array_equal(match, np.array_equal([[0, 0], [1, 1], [2, -1]])) -- cgit v1.2.3 From fc4e10863d103ee6bc22863f48548fe246a3ddd6 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 10 Mar 2020 18:03:21 +0100 Subject: correction of typo in the doc --- src/python/gudhi/wasserstein.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 9e4dc7d5..12337780 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -30,10 +30,10 @@ def _build_dist_matrix(X, Y, order=2., internal_p=2.): :param order: exponent for the Wasserstein metric. :param internal_p: Ground metric (i.e. norm L^p). :returns: (n+1) x (m+1) np.array encoding the cost matrix C. - For 1 <= i <= n, 1 <= j <= m, C[i,j] encodes the distance between X[i] and Y[j], - while C[i, m+1] (resp. C[n+1, j]) encodes the distance (to the p) between X[i] (resp Y[j]) + For 0 <= i < n, 0 <= j < m, C[i,j] encodes the distance between X[i] and Y[j], + while C[i, m] (resp. C[n, j]) encodes the distance (to the p) between X[i] (resp Y[j]) and its orthogonal proj onto the diagonal. - note also that C[n+1, m+1] = 0 (it costs nothing to move from the diagonal to the diagonal). + note also that C[n, m] = 0 (it costs nothing to move from the diagonal to the diagonal). ''' Xdiag = _proj_on_diag(X) Ydiag = _proj_on_diag(Y) -- cgit v1.2.3 From 6c369a6aa566dfcb8cdb501d0c39eafb32219669 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 10 Mar 2020 18:08:15 +0100 Subject: fix typo in test_wasserstein_distance --- src/python/test/test_wasserstein_distance.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index ca9a4a61..f92208c0 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -69,7 +69,7 @@ def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True, test_mat match = wasserstein_distance(diag2, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] assert np.array_equal(match , np.array([[0, -1], [1, -1]])) match = wasserstein_distance(diag1, diag2, matching=True, internal_p=2., order=2.)[1] - assert np.array_equal(match, np.array_equal([[0, 0], [1, 1], [2, -1]])) + assert np.array_equal(match, np.array([[0, 0], [1, 1], [2, -1]])) -- cgit v1.2.3 From 753290475ab6e95c2de1baad97ee6f755a0ce19a Mon Sep 17 00:00:00 2001 From: Théo Lacombe Date: Tue, 10 Mar 2020 18:25:10 +0100 Subject: Update src/python/gudhi/wasserstein.py Co-Authored-By: Marc Glisse --- src/python/gudhi/wasserstein.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 12337780..83a682df 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -32,7 +32,7 @@ def _build_dist_matrix(X, Y, order=2., internal_p=2.): :returns: (n+1) x (m+1) np.array encoding the cost matrix C. For 0 <= i < n, 0 <= j < m, C[i,j] encodes the distance between X[i] and Y[j], while C[i, m] (resp. C[n, j]) encodes the distance (to the p) between X[i] (resp Y[j]) - and its orthogonal proj onto the diagonal. + and its orthogonal projection onto the diagonal. note also that C[n, m] = 0 (it costs nothing to move from the diagonal to the diagonal). ''' Xdiag = _proj_on_diag(X) -- cgit v1.2.3 From c9d6e27495c8927d736d593afb0450360b46ccc9 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 10 Mar 2020 18:55:19 +0100 Subject: fix indentation in wasserstein --- src/python/gudhi/wasserstein.py | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 83a682df..3dd993f9 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -70,13 +70,13 @@ def wasserstein_distance(X, Y, matching=False, order=2., internal_p=2.): (i.e. with infinite coordinate). :param Y: (m x 2) numpy.array encoding the second diagram. :param matching: if True, computes and returns the optimal matching between X and Y, encoded as - a (n x 2) np.array [...[i,j]...], meaning the i-th point in X is matched to - the j-th point in Y, with the convention (-1) represents the diagonal. + a (n x 2) np.array [...[i,j]...], meaning the i-th point in X is matched to + the j-th point in Y, with the convention (-1) represents the diagonal. :param order: exponent for Wasserstein; Default value is 2. :param internal_p: Ground metric on the (upper-half) plane (i.e. norm L^p in R^2); - Default value is 2 (Euclidean norm). + Default value is 2 (Euclidean norm). :returns: the Wasserstein distance of order q (1 <= q < infinity) between persistence diagrams with - respect to the internal_p-norm as ground metric. + respect to the internal_p-norm as ground metric. If matching is set to True, also returns the optimal matching between X and Y. ''' n = len(X) -- cgit v1.2.3 From a17a09a2c58bba79e897d0ba00aada05da556967 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Wed, 11 Mar 2020 10:41:53 +0100 Subject: clean test_wasserstein from useless np.array --- src/python/test/test_wasserstein_distance.py | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'src/python') diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index f92208c0..0d70e11a 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -61,15 +61,15 @@ def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True, test_mat if test_matching: match = wasserstein_distance(emptydiag, emptydiag, matching=True, internal_p=1., order=2)[1] - assert np.array_equal(match, np.array([])) + assert np.array_equal(match, []) match = wasserstein_distance(emptydiag, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] - assert np.array_equal(match, np.array([])) + assert np.array_equal(match, []) match = wasserstein_distance(emptydiag, diag2, matching=True, internal_p=np.inf, order=2.)[1] - assert np.array_equal(match , np.array([[-1, 0], [-1, 1]])) + assert np.array_equal(match , [[-1, 0], [-1, 1]]) match = wasserstein_distance(diag2, emptydiag, matching=True, internal_p=np.inf, order=2.24)[1] - assert np.array_equal(match , np.array([[0, -1], [1, -1]])) + assert np.array_equal(match , [[0, -1], [1, -1]]) match = wasserstein_distance(diag1, diag2, matching=True, internal_p=2., order=2.)[1] - assert np.array_equal(match, np.array([[0, 0], [1, 1], [2, -1]])) + assert np.array_equal(match, [[0, 0], [1, 1], [2, -1]]) -- cgit v1.2.3 From 5c55e976606b4dd020bd4e21c93ae22143ef5348 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Mar 2020 18:01:16 +0100 Subject: changed doc of matchings for a more explicit (and hopefully sphinx-valid) version --- src/python/doc/wasserstein_distance_user.rst | 29 ++++++++++++++++++++-------- 1 file changed, 21 insertions(+), 8 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 9519caa6..4c3b53dd 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -58,16 +58,29 @@ An index of -1 represents the diagonal. import gudhi.wasserstein import numpy as np - diag1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) - diag2 = np.array([[2.8, 4.45], [5, 6], [9.5, 14.1]]) - cost, matching = gudhi.wasserstein.wasserstein_distance(diag1, diag2, matching=True, order=1., internal_p=2.) - - message = "Wasserstein distance value = %.2f, optimal matching: %s" %(cost, matching) - print(message) + dgm1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) + dgm2 = np.array([[2.8, 4.45], [5, 6], [9.5, 14.1]]) + cost, matchings = gudhi.wasserstein.wasserstein_distance(diag1, diag2, matching=True, order=1., internal_p=2.) + + message_cost = "Wasserstein distance value = %.2f" %cost + print(message_cost) + dgm1_to_diagonal = matchings[np.where(matchings[:,0] == -1)][:,1] + dgm2_to_diagonal = matchings[np.where(matchings[:,1] == -1)][:,0] + off_diagonal_match = np.delete(matchings, np.where(matchings == -1)[0], axis=0) + + for i,j in off_diagonal_match: + print("point %s in dgm1 is matched to point %s in dgm2" %(i,j)) + for i in dgm1_to_diagonal: + print("point %s in dgm1 is matched to the diagonal" %i) + for j in dgm2_to_diagonal: + print("point %s in dgm2 is matched to the diagonal" %j) The output is: .. testoutput:: - Wasserstein distance value = 2.15, optimal matching: [[0, 0], [1, 2], [2, -1], [-1, 1]] - + Wasserstein distance value = 2.15 + point 0 in dgm1 is matched to point 0 in dgm2 + point 1 in dgm1 is matched to point 2 in dgm2 + point 2 in dgm1 is matched to the diagonal + point 1 in dgm2 is matched to the diagonal -- cgit v1.2.3 From 66f0b08a8f8d5006f8d29352c169525cc53a22e6 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Mar 2020 19:11:30 +0100 Subject: changed typo in doc (diag --> dgm), used integer for order and internal p, simplify th ecode --- src/python/doc/wasserstein_distance_user.rst | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 4c3b53dd..f43b2217 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -36,10 +36,10 @@ Note that persistence diagrams must be submitted as (n x 2) numpy arrays and mus import gudhi.wasserstein import numpy as np - diag1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) - diag2 = np.array([[2.8, 4.45],[9.5, 14.1]]) + dgm1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) + dgm2 = np.array([[2.8, 4.45],[9.5, 14.1]]) - message = "Wasserstein distance value = " + '%.2f' % gudhi.wasserstein.wasserstein_distance(diag1, diag2, order=1., internal_p=2.) + message = "Wasserstein distance value = " + '%.2f' % gudhi.wasserstein.wasserstein_distance(dgm1, dgm2, order=1., internal_p=2.) print(message) The output is: @@ -60,12 +60,12 @@ An index of -1 represents the diagonal. dgm1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) dgm2 = np.array([[2.8, 4.45], [5, 6], [9.5, 14.1]]) - cost, matchings = gudhi.wasserstein.wasserstein_distance(diag1, diag2, matching=True, order=1., internal_p=2.) + cost, matchings = gudhi.wasserstein.wasserstein_distance(dgm1, dgm2, matching=True, order=1, internal_p=2) message_cost = "Wasserstein distance value = %.2f" %cost print(message_cost) - dgm1_to_diagonal = matchings[np.where(matchings[:,0] == -1)][:,1] - dgm2_to_diagonal = matchings[np.where(matchings[:,1] == -1)][:,0] + dgm1_to_diagonal = matching[matching[:,0] == -1, 1] + dgm2_to_diagonal = matching[matching[:,1] == -1, 0] off_diagonal_match = np.delete(matchings, np.where(matchings == -1)[0], axis=0) for i,j in off_diagonal_match: -- cgit v1.2.3 From a253c0c4f54a9a148740ed9c20457df0ea43c842 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Mar 2020 19:36:07 +0100 Subject: correction typo in usr.rst --- src/python/doc/wasserstein_distance_user.rst | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index f43b2217..25e51d68 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -64,8 +64,8 @@ An index of -1 represents the diagonal. message_cost = "Wasserstein distance value = %.2f" %cost print(message_cost) - dgm1_to_diagonal = matching[matching[:,0] == -1, 1] - dgm2_to_diagonal = matching[matching[:,1] == -1, 0] + dgm1_to_diagonal = matchings[matchings[:,0] == -1, 1] + dgm2_to_diagonal = matchings[matchings[:,1] == -1, 0] off_diagonal_match = np.delete(matchings, np.where(matchings == -1)[0], axis=0) for i,j in off_diagonal_match: -- cgit v1.2.3 From 60d11e3f06e08b66e49997f389c4dc01b00b793f Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Mar 2020 21:17:38 +0100 Subject: correction of typo in usr.rst --- src/python/doc/wasserstein_distance_user.rst | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 25e51d68..a9b21fa5 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -64,8 +64,8 @@ An index of -1 represents the diagonal. message_cost = "Wasserstein distance value = %.2f" %cost print(message_cost) - dgm1_to_diagonal = matchings[matchings[:,0] == -1, 1] - dgm2_to_diagonal = matchings[matchings[:,1] == -1, 0] + dgm1_to_diagonal = matchings[matchings[:,1] == -1, 0] + dgm2_to_diagonal = matchings[matchings[:,0] == -1, 1] off_diagonal_match = np.delete(matchings, np.where(matchings == -1)[0], axis=0) for i,j in off_diagonal_match: -- cgit v1.2.3