From cce93208f383969d718c92c526c5e834cd3a2733 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 18 Oct 2019 22:43:09 +0200 Subject: commit first draft of barycenter.py --- src/python/gudhi/barycenter.py | 187 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 187 insertions(+) create mode 100644 src/python/gudhi/barycenter.py (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py new file mode 100644 index 00000000..c46f6926 --- /dev/null +++ b/src/python/gudhi/barycenter.py @@ -0,0 +1,187 @@ +import ot +import numpy as np +import matplotlib.pyplot as plt +from matplotlib.patches import Polygon + +def _proj_on_diag(x): + return np.array([(x[0] + x[1]) / 2, (x[0] + x[1]) / 2]) + + +def _norm2(x, y): + return (y[0] - x[0])**2 + (y[1] - x[1])**2 + + +def _norm_inf(x, y): + return np.max(np.abs(y[0] - x[0]), np.abs(y[1] - x[1])) + + +def _cost_matrix(X, Y): + """ + :param X: (n x 2) numpy.array encoding the first diagram + :param Y: (m x 2) numpy.array encoding the second diagram + :return: The cost matrix with size (k x k) where k = |d_1| + |d_2| in order to encode matching to diagonal + """ + n, m = len(X), len(Y) + k = n + m + M = np.zeros((k, k)) + for i in range(n): # go throught X points + x_i = X[i] + p_x_i = _proj_on_diag(x_i) # proj of x_i on the diagonal + dist_x_delta = _norm2(x_i, p_x_i) # distance to the diagonal regarding the ground norm + for j in range(m): # go throught d_2 points + y_j = Y[j] + p_y_j = _proj_on_diag(y_j) + M[i, j] = _norm2(x_i, y_j) + dist_y_delta = _norm2(y_j, p_y_j) + for it in range(m): + M[n + it, j] = dist_y_delta + for it in range(n): + M[i, m + it] = dist_x_delta + + return M + + +def _optimal_matching(M): + n = len(M) + # if input weights are empty lists, pot treat the uniform assignement problem and returns a bistochastic matrix (up to *n). + P = ot.emd(a=[], b=[], M=M) * n + # return the list of indices j such that L[i] = j iff P[i,j] = 1 + return np.nonzero(P)[1] + + +def _mean(x, m): + """ + :param x: a list of 2D-points, of diagonal, x_0... x_{k-1} + :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal + :returns: the weighted mean of x with (m-k) copies of Delta taken into account (defined by mukherjee etc.) + """ + k = len(x) + if k > 0: + w = np.mean(x, axis=0) + w_delta = _proj_on_diag(w) + return (k * w + (m-k) * w_delta) / m + else: + return np.array([0, 0]) + + +def lagrangian_barycenter(pdiagset, init=None, verbose=False): + """ + Compute the estimated barycenter computed with the Hungarian algorithm provided by Mukherjee et al + It is a local minima of the corresponding Frechet function. + It exactly belongs to the persistence diagram space (because all computations are made on it). + :param pdiagset: a list of size N containing numpy.array of shape (n x + 2) (n can variate), encoding a set of persistence diagrams with only finite + coordinates. + :param init: The initial value for barycenter estimate. If None, init is made on a random diagram from the dataset. Otherwise, it must be a (n x 2) numpy.array enconding a persistence diagram with n points. + :returns: If not verbose (default), the barycenter estimate (local minima of the energy function). If verbose, returns a triplet (Y, a, e) where Y is the barycenter estimate, a is the assignments between the points of Y and thoses of the diagrams, and e is the energy value reached by the estimate. + """ + m = len(pdiagset) # number of diagrams we are averaging + X = pdiagset # to shorten notations + nb_off_diag = np.array([len(X_i) for X_i in X]) # store the number of off-diagonal point for each of the X_i + + # Initialisation of barycenter + if init is None: + i0 = np.random.randint(m) # Index of first state for the barycenter + Y = X[i0].copy() + else: + Y = init.copy() + + not_converged = True # stoping criterion + while not_converged: + K = len(Y) # current nb of points in Y (some might be on diagonal) + G = np.zeros((K, m)) # will store for each j, the (index) point matched in each other diagram (might be the diagonal). + updated_points = np.zeros((K, 2)) # will store the new positions of the points of Y + new_created_points = [] # will store eventual new points. + + # Step 1 : compute optimal matching (Y, X_i) for each X_i + for i in range(m): + M = _cost_matrix(Y, X[i]) + indices = _optimal_matching(M) + for y_j, x_i_j in enumerate(indices): + if y_j < K: # we matched an off diagonal point to x_i_j... + if x_i_j < nb_off_diag[i]: # ...which is also an off-diagonal point + G[y_j, i] = x_i_j + else: # ...which is a diagonal point + G[y_j, i] = -1 # -1 stands for the diagonal (mask) + else: # We matched a diagonal point to x_i_j... + if x_i_j < nb_off_diag[i]: # which is a off-diag point ! so we need to create a new point in Y + new_y = _mean(np.array([X[i][x_i_j]]), m) # Average this point with (m-1) copies of Delta + new_created_points.append(new_y) + + # Step 2 : Compute new points (mean) + for j in range(K): + matched_points = [X[i][int(G[j, i])] for i in range(m) if G[j, i] > -1] + updated_points[j] = _mean(matched_points, m) + + if new_created_points: + Y = np.concatenate((updated_points, new_created_points)) + else: + Y = updated_points + + # Step 3 : we update our estimation of the barycenter + if len(new_created_points) == 0 and np.array_equal(updated_points, Y): + not_converged = False + + if verbose: + matchings = [] + energy = 0 + n_y = len(Y) + for i in range(m): + M = _cost_matrix(Y, X[i]) + edges = _optimal_matching(M) + matchings.append([x_i_j for (y_j, x_i_j) in enumerate(edges) if y_j < n_y]) + #energy += total_cost + + #energy /= m + _plot_barycenter(X, Y, matchings) + plt.show() + return Y, matchings, energy + else: + return Y + +def _plot_barycenter(X, Y, matchings): + fig = plt.figure() + ax = fig.add_subplot(111) + + # n_y = len(Y.points) + for i in range(len(X)): + indices = matchings[i] + n_i = len(X[i]) + + for (y_j, x_i_j) in enumerate(indices): + y = Y[y_j] + if y[0] != y[1]: + if x_i_j < n_i: # not mapped with the diag + x = X[i][x_i_j] + else: # y_j is matched to the diagonal + x = _proj_on_diag(y) + ax.plot([y[0], x[0]], [y[1], x[1]], c='black', + linestyle="dashed") + + ax.scatter(Y[:,0], Y[:,1], color='purple', marker='d') + + for dgm in X: + ax.scatter(dgm[:,0], dgm[:,1], marker ='o') + + shift = 0.1 # for improved rendering + xmin = min([np.min(x[:,0]) for x in X]) - shift + xmax = max([np.max(x[:,0]) for x in X]) + shift + ymin = min([np.max(x[:,1]) for x in X]) - shift + ymax = max([np.max(x[:,1]) for x in X]) + shift + themin = min(xmin, ymin) + themax = max(xmax, ymax) + ax.set_xlim(themin, themax) + ax.set_ylim(themin, themax) + ax.add_patch(Polygon([[themin,themin], [themax,themin], [themax,themax]], fill=True, color='lightgrey')) + ax.set_xticks([]) + ax.set_yticks([]) + ax.set_aspect('equal', adjustable='box') + ax.set_title("example of (estimated) barycenter") + + +if __name__=="__main__": + dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) + dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) + dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) + X = [dg1, dg2, dg3] + Y, a, e = lagrangian_barycenter(X, verbose=True) -- cgit v1.2.3 From 48f7e17c5e9d4f6936bfdf6384015fe833e30c74 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 18 Oct 2019 23:18:53 +0200 Subject: updated documentation in barycenter.py --- src/python/gudhi/barycenter.py | 78 ++++++++++++++++++++++++++++++------------ 1 file changed, 57 insertions(+), 21 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index c46f6926..85666631 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -4,22 +4,30 @@ import matplotlib.pyplot as plt from matplotlib.patches import Polygon def _proj_on_diag(x): + """ + :param x: numpy.array of length 2, encoding a point on the upper half plane. + :returns: numpy.array of length 2, orthogonal projection of the point onto + the diagonal. + """ return np.array([(x[0] + x[1]) / 2, (x[0] + x[1]) / 2]) def _norm2(x, y): + """ + :param x: numpy.array of length 2, encoding a point on the upper half plane. + :param y: numpy.array of length 2, encoding a point on the upper half plane. + :returns: distance between the two points for the euclidean norm. + """ return (y[0] - x[0])**2 + (y[1] - x[1])**2 -def _norm_inf(x, y): - return np.max(np.abs(y[0] - x[0]), np.abs(y[1] - x[1])) - - def _cost_matrix(X, Y): """ :param X: (n x 2) numpy.array encoding the first diagram :param Y: (m x 2) numpy.array encoding the second diagram - :return: The cost matrix with size (k x k) where k = |d_1| + |d_2| in order to encode matching to diagonal + :return: numpy.array with size (k x k) where k = |X| + |Y|, encoding the + cost matrix between points (including the diagonal, with repetition to + ensure one-to-one matchings. """ n, m = len(X), len(Y) k = n + m @@ -42,8 +50,15 @@ def _cost_matrix(X, Y): def _optimal_matching(M): + """ + :param M: numpy.array of size (k x k), encoding the cost matrix between the + points of two diagrams. + :returns: list of length (k) such that L[i] = j if and only if P[i,j]=1 + where P is a bi-stochastic matrix that minimize . + """ n = len(M) - # if input weights are empty lists, pot treat the uniform assignement problem and returns a bistochastic matrix (up to *n). + # if input weights are empty lists, pot treats the uniform assignement + # problem and returns a bistochastic matrix (up to *n). P = ot.emd(a=[], b=[], M=M) * n # return the list of indices j such that L[i] = j iff P[i,j] = 1 return np.nonzero(P)[1] @@ -53,7 +68,8 @@ def _mean(x, m): """ :param x: a list of 2D-points, of diagonal, x_0... x_{k-1} :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal - :returns: the weighted mean of x with (m-k) copies of Delta taken into account (defined by mukherjee etc.) + :returns: the weighted mean of x with (m-k) copies of Delta taken into + account. """ k = len(x) if k > 0: @@ -66,14 +82,23 @@ def _mean(x, m): def lagrangian_barycenter(pdiagset, init=None, verbose=False): """ - Compute the estimated barycenter computed with the Hungarian algorithm provided by Mukherjee et al - It is a local minima of the corresponding Frechet function. - It exactly belongs to the persistence diagram space (because all computations are made on it). - :param pdiagset: a list of size N containing numpy.array of shape (n x - 2) (n can variate), encoding a set of persistence diagrams with only finite - coordinates. - :param init: The initial value for barycenter estimate. If None, init is made on a random diagram from the dataset. Otherwise, it must be a (n x 2) numpy.array enconding a persistence diagram with n points. - :returns: If not verbose (default), the barycenter estimate (local minima of the energy function). If verbose, returns a triplet (Y, a, e) where Y is the barycenter estimate, a is the assignments between the points of Y and thoses of the diagrams, and e is the energy value reached by the estimate. + Compute the estimated barycenter computed with the algorithm provided + by Turner et al (2014). + It is a local minima of the corresponding Frechet function. + :param pdiagset: a list of size N containing numpy.array of shape (n x 2) + (n can variate), encoding a set of + persistence diagrams with only finite coordinates. + :param init: The initial value for barycenter estimate. + If None, init is made on a random diagram from the dataset. + Otherwise, it must be a (n x 2) numpy.array enconding a persistence diagram with n points. + :param verbose: if True, returns additional information about the + barycenters (assignment and energy). + :returns: If not verbose (default), a numpy.array encoding + the barycenter estimate (local minima of the energy function). + If verbose, returns a triplet (Y, a, e) + where Y is the barycenter estimate, a is the assignments between the + points of Y and thoses of the diagrams, + and e is the energy value reached by the estimate. """ m = len(pdiagset) # number of diagrams we are averaging X = pdiagset # to shorten notations @@ -90,7 +115,10 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): while not_converged: K = len(Y) # current nb of points in Y (some might be on diagonal) G = np.zeros((K, m)) # will store for each j, the (index) point matched in each other diagram (might be the diagonal). - updated_points = np.zeros((K, 2)) # will store the new positions of the points of Y + updated_points = np.zeros((K, 2)) # will store the new positions of + # the points of Y. + # If points disappear, there thrown + # on [0,0] by default. new_created_points = [] # will store eventual new points. # Step 1 : compute optimal matching (Y, X_i) for each X_i @@ -130,16 +158,22 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): M = _cost_matrix(Y, X[i]) edges = _optimal_matching(M) matchings.append([x_i_j for (y_j, x_i_j) in enumerate(edges) if y_j < n_y]) - #energy += total_cost + energy += sum([M[i,j] for i,j in enumerate(edges)]) - #energy /= m - _plot_barycenter(X, Y, matchings) - plt.show() + energy = energy/m return Y, matchings, energy else: return Y def _plot_barycenter(X, Y, matchings): + """ + :param X: list of persistence diagrams. + :param Y: numpy.array of (n x 2). Aims to be an estimate of the barycenter + returned by lagrangian_barycenter(X, verbose=True). + :param matchings: list of lists, such that L[k][i] = j if and only if + the i-th point of the barycenter is grouped with the j-th point of the k-th + diagram. + """ fig = plt.figure() ax = fig.add_subplot(111) @@ -176,7 +210,7 @@ def _plot_barycenter(X, Y, matchings): ax.set_xticks([]) ax.set_yticks([]) ax.set_aspect('equal', adjustable='box') - ax.set_title("example of (estimated) barycenter") + ax.set_title("Estimated barycenter") if __name__=="__main__": @@ -185,3 +219,5 @@ if __name__=="__main__": dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) X = [dg1, dg2, dg3] Y, a, e = lagrangian_barycenter(X, verbose=True) + _plot_barycenter(X, Y, a) + plt.show() -- cgit v1.2.3 From 80aa14d1b92d1a61366d798b07073289d4db4fda Mon Sep 17 00:00:00 2001 From: tlacombe Date: Thu, 5 Dec 2019 18:42:48 +0100 Subject: first version of barycenter for persistence diagrams --- src/python/doc/barycenter_sum.inc | 22 +++ src/python/doc/barycenter_user.rst | 51 ++++++ src/python/gudhi/barycenter.py | 322 +++++++++++++++++++++++++------------ 3 files changed, 292 insertions(+), 103 deletions(-) create mode 100644 src/python/doc/barycenter_sum.inc create mode 100644 src/python/doc/barycenter_user.rst (limited to 'src/python') diff --git a/src/python/doc/barycenter_sum.inc b/src/python/doc/barycenter_sum.inc new file mode 100644 index 00000000..7801a845 --- /dev/null +++ b/src/python/doc/barycenter_sum.inc @@ -0,0 +1,22 @@ +.. table:: + :widths: 30 50 20 + + +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ + | .. figure:: | A Frechet mean (or barycenter) is a generalization of the arithmetic | :Author: Theo Lacombe | + | ../../doc/Barycenter/barycenter.png | mean in a non linear space such as the one of persistence diagrams. | | + | :figclass: align-center | Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is | :Introduced in: GUDHI 3.1.0 | + | | defined as a minimizer of the variance functional, that is of | | + | Illustration of Frechet mean between persistence | :math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. | :Copyright: MIT | + | diagrams. | where :math:`d_2` denotes the Wasserstein-2 distance between persis- | | + | | tence diagrams. | | + | | It is known to exist and is generically unique. However, an exact | | + | | computation is in general untractable. Current implementation avai- | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | + | | -lable is based on [Turner et al, 2014], and uses an EM-scheme to | | + | | provide a local minimum of the variance functional (somewhat similar | | + | | to the Lloyd algorithm to estimate a solution to the k-means | | + | | problem). The combinatorial structure of the algorithm limits its | | + | | scaling on large scale problems (thousands of diagrams and of points | | + | | per diagram). | | + +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ + | * :doc:`barycenter_user` | | + +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst new file mode 100644 index 00000000..fae2854a --- /dev/null +++ b/src/python/doc/barycenter_user.rst @@ -0,0 +1,51 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Wasserstein distance user manual +================================ +Definition +---------- + +.. include:: wasserstein_distance_sum.inc + +This implementation is based on ideas from "Large Scale Computation of Means and Cluster for Persistence Diagrams via Optimal Transport". + +Function +-------- +.. autofunction:: gudhi.barycenter.lagrangian_barycenter + + +Basic example +------------- + +This example computes the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. +It is initialized on the 4th diagram, which is the empty diagram. It is encoded by np.array([]). +Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. + +.. testcode:: + + import gudhi.barycenter + import numpy as np + + dg1 = np.array([[0.2, 0.5]]) + dg2 = np.array([[0.2, 0.7]]) + dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + dg4 = np.array([]) + + bary = gudhi.barycenter.lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3)) + + message = "Wasserstein barycenter estimated:" + print(message) + print(bary) + +The output is: + +.. testoutput:: + + Wasserstein barycenter estimated: + [[0.27916667 0.55416667] + [0.7375 0.7625 ] + [0.2375 0.2625 ]] + + diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 85666631..3cd214a7 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -1,75 +1,105 @@ import ot import numpy as np -import matplotlib.pyplot as plt -from matplotlib.patches import Polygon +import scipy.spatial.distance as sc -def _proj_on_diag(x): - """ - :param x: numpy.array of length 2, encoding a point on the upper half plane. - :returns: numpy.array of length 2, orthogonal projection of the point onto - the diagonal. - """ - return np.array([(x[0] + x[1]) / 2, (x[0] + x[1]) / 2]) +# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. +# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. +# Author(s): Theo Lacombe +# +# Copyright (C) 2019 Inria +# +# Modification(s): +# - YYYY/MM Author: Description of the modification -def _norm2(x, y): - """ - :param x: numpy.array of length 2, encoding a point on the upper half plane. - :param y: numpy.array of length 2, encoding a point on the upper half plane. - :returns: distance between the two points for the euclidean norm. - """ - return (y[0] - x[0])**2 + (y[1] - x[1])**2 +def _proj_on_diag(w): + ''' + Util function to project a point on the diag. + ''' + return np.array([(w[0] + w[1])/2 , (w[0] + w[1])/2]) -def _cost_matrix(X, Y): - """ - :param X: (n x 2) numpy.array encoding the first diagram - :param Y: (m x 2) numpy.array encoding the second diagram - :return: numpy.array with size (k x k) where k = |X| + |Y|, encoding the - cost matrix between points (including the diagonal, with repetition to - ensure one-to-one matchings. - """ - n, m = len(X), len(Y) - k = n + m - M = np.zeros((k, k)) - for i in range(n): # go throught X points - x_i = X[i] - p_x_i = _proj_on_diag(x_i) # proj of x_i on the diagonal - dist_x_delta = _norm2(x_i, p_x_i) # distance to the diagonal regarding the ground norm - for j in range(m): # go throught d_2 points - y_j = Y[j] - p_y_j = _proj_on_diag(y_j) - M[i, j] = _norm2(x_i, y_j) - dist_y_delta = _norm2(y_j, p_y_j) - for it in range(m): - M[n + it, j] = dist_y_delta - for it in range(n): - M[i, m + it] = dist_x_delta - - return M - - -def _optimal_matching(M): + +def _proj_on_diag_array(X): + ''' + :param X: (n x 2) array encoding the points of a persistent diagram. + :returns: (n x 2) array encoding the (respective orthogonal) projections of the points onto the diagonal + ''' + Z = (X[:,0] + X[:,1]) / 2. + return np.array([Z , Z]).T + + +def _build_dist_matrix(X, Y, p=2., q=2.): + ''' + :param X: (n x 2) numpy.array encoding the (points of the) first diagram. + :param Y: (m x 2) numpy.array encoding the second diagram. + :param q: Ground metric (i.e. norm l_q). + :param p: exponent for the Wasserstein metric. + :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. + note also that C[n+1, m+1] = 0 (it costs nothing to move from the diagonal to the diagonal). + Note that for lagrangian_barycenter, one must use p=q=2. + ''' + Xdiag = _proj_on_diag_array(X) + Ydiag = _proj_on_diag_array(Y) + if np.isinf(q): + C = sc.cdist(X, Y, metric='chebyshev')**p + Cxd = np.linalg.norm(X - Xdiag, ord=q, axis=1)**p + Cdy = np.linalg.norm(Y - Ydiag, ord=q, axis=1)**p + else: + C = sc.cdist(X,Y, metric='minkowski', p=q)**p + Cxd = np.linalg.norm(X - Xdiag, ord=q, axis=1)**p + Cdy = np.linalg.norm(Y - Ydiag, ord=q, axis=1)**p + Cf = np.hstack((C, Cxd[:,None])) + Cdy = np.append(Cdy, 0) + + Cf = np.vstack((Cf, Cdy[None,:])) + + return Cf + + +def _optimal_matching(X, Y): """ - :param M: numpy.array of size (k x k), encoding the cost matrix between the - points of two diagrams. - :returns: list of length (k) such that L[i] = j if and only if P[i,j]=1 - where P is a bi-stochastic matrix that minimize . + :param X: numpy.array of size (n x 2) + :param Y: numpy.array of size (m x 2) + :returns: numpy.array of shape (k x 2) encoding the list of edges in the optimal matching. + That is, [[(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] + if i > len(X) or j > len(Y), it means they represent the diagonal. + """ - n = len(M) - # if input weights are empty lists, pot treats the uniform assignement - # problem and returns a bistochastic matrix (up to *n). - P = ot.emd(a=[], b=[], M=M) * n - # return the list of indices j such that L[i] = j iff P[i,j] = 1 - return np.nonzero(P)[1] + + n = len(X) + m = len(Y) + if X.size == 0: # X is empty + if Y.size == 0: # Y is empty + return np.array([[0,0]]) # the diagonal is matched to the diagonal and that's it... + else: + return np.column_stack([np.zeros(m+1, dtype=int), np.arange(m+1, dtype=int)]) # TO BE CORRECTED + elif Y.size == 0: # X is not empty but Y is empty + return np.column_stack([np.zeros(n+1, dtype=int), np.arange(n+1, dtype=int)]) # TO BE CORRECTED + + # we know X, Y are not empty diags now + M = _build_dist_matrix(X, Y) + + 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 + P = ot.emd(a=a, b=b, M=M)*(n+m) + # Note : it seems POT return a permutation matrix in this situation, + # ...guarantee...? + # It should be enough to check that the algorithm only iterates on vertices of the transportation polytope. + P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to be improved. + # return the list of (i,j) such that P[i,j] > 0, i.e. x_i is matched to y_j (should it be the diag). + res = np.nonzero(P) + return np.column_stack(res) def _mean(x, m): """ - :param x: a list of 2D-points, of diagonal, x_0... x_{k-1} + :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal - :returns: the weighted mean of x with (m-k) copies of Delta taken into - account. + :returns: the weighted mean of x with (m-k) copies of the diagonal """ k = len(x) if k > 0: @@ -88,44 +118,54 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): :param pdiagset: a list of size N containing numpy.array of shape (n x 2) (n can variate), encoding a set of persistence diagrams with only finite coordinates. - :param init: The initial value for barycenter estimate. - If None, init is made on a random diagram from the dataset. - Otherwise, it must be a (n x 2) numpy.array enconding a persistence diagram with n points. - :param verbose: if True, returns additional information about the - barycenters (assignment and energy). - :returns: If not verbose (default), a numpy.array encoding + :param init: The initial value for barycenter estimate. + If None, init is made on a random diagram from the dataset. + Otherwise, it must be an int (then we init with diagset[init]) + or a (n x 2) numpy.array enconding a persistence diagram with n points. + :param verbose: if True, returns additional information about the + barycenters (assignment and energy). + :returns: If not verbose (default), a numpy.array encoding the barycenter estimate (local minima of the energy function). If verbose, returns a triplet (Y, a, e) where Y is the barycenter estimate, a is the assignments between the points of Y and thoses of the diagrams, and e is the energy value reached by the estimate. """ - m = len(pdiagset) # number of diagrams we are averaging - X = pdiagset # to shorten notations + X = pdiagset # to shorten notations, not a copy + m = len(X) # number of diagrams we are averaging + if m == 0: + print("Warning: computing barycenter of empty diag set. Returns None") + return None + nb_off_diag = np.array([len(X_i) for X_i in X]) # store the number of off-diagonal point for each of the X_i # Initialisation of barycenter if init is None: i0 = np.random.randint(m) # Index of first state for the barycenter - Y = X[i0].copy() + Y = X[i0].copy() #copy() ensure that we do not modify X[i0] else: - Y = init.copy() + if type(init)==int: + Y = X[init].copy() + else: + Y = init.copy() - not_converged = True # stoping criterion - while not_converged: + converged = False # stoping criterion + while not converged: K = len(Y) # current nb of points in Y (some might be on diagonal) - G = np.zeros((K, m)) # will store for each j, the (index) point matched in each other diagram (might be the diagonal). + G = np.zeros((K, m), dtype=int)-1 # will store for each j, the (index) point matched in each other diagram (might be the diagonal). + # that is G[j, i] = k <=> y_j is matched to + # x_k in the diagram i-th diagram X[i] updated_points = np.zeros((K, 2)) # will store the new positions of # the points of Y. # If points disappear, there thrown # on [0,0] by default. - new_created_points = [] # will store eventual new points. + new_created_points = [] # will store potential new points. # Step 1 : compute optimal matching (Y, X_i) for each X_i + # and create new points in Y if needed for i in range(m): - M = _cost_matrix(Y, X[i]) - indices = _optimal_matching(M) - for y_j, x_i_j in enumerate(indices): + indices = _optimal_matching(Y, X[i]) + for y_j, x_i_j in indices: if y_j < K: # we matched an off diagonal point to x_i_j... if x_i_j < nb_off_diag[i]: # ...which is also an off-diagonal point G[y_j, i] = x_i_j @@ -136,32 +176,40 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): new_y = _mean(np.array([X[i][x_i_j]]), m) # Average this point with (m-1) copies of Delta new_created_points.append(new_y) - # Step 2 : Compute new points (mean) + # Step 2 : Update current point position thanks to the groupings computed + + to_delete = [] for j in range(K): - matched_points = [X[i][int(G[j, i])] for i in range(m) if G[j, i] > -1] - updated_points[j] = _mean(matched_points, m) + matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] + new_y_j = _mean(matched_points, m) + if not np.array_equal(new_y_j, np.array([0,0])): + updated_points[j] = new_y_j + else: # this points is no longer of any use. + to_delete.append(j) + # we remove the point to be deleted now. + updated_points = np.delete(updated_points, to_delete, axis=0) # cannot be done in-place. - if new_created_points: + + if new_created_points: # we cannot converge if there have been new created points. Y = np.concatenate((updated_points, new_created_points)) else: + # Step 3 : we check convergence + if np.array_equal(updated_points, Y): + converged = True Y = updated_points - # Step 3 : we update our estimation of the barycenter - if len(new_created_points) == 0 and np.array_equal(updated_points, Y): - not_converged = False if verbose: matchings = [] - energy = 0 + #energy = 0 n_y = len(Y) for i in range(m): - M = _cost_matrix(Y, X[i]) - edges = _optimal_matching(M) + edges = _optimal_matching(Y, X[i]) matchings.append([x_i_j for (y_j, x_i_j) in enumerate(edges) if y_j < n_y]) - energy += sum([M[i,j] for i,j in enumerate(edges)]) + # energy += sum([M[i,j] for i,j in enumerate(edges)]) - energy = energy/m - return Y, matchings, energy + # energy = energy/m + return Y, matchings #, energy else: return Y @@ -174,6 +222,11 @@ def _plot_barycenter(X, Y, matchings): the i-th point of the barycenter is grouped with the j-th point of the k-th diagram. """ + # import matplotlib now to avoid useless dependancies + + import matplotlib.pyplot as plt + from matplotlib.patches import Polygon + fig = plt.figure() ax = fig.add_subplot(111) @@ -182,7 +235,7 @@ def _plot_barycenter(X, Y, matchings): indices = matchings[i] n_i = len(X[i]) - for (y_j, x_i_j) in enumerate(indices): + for (y_j, x_i_j) in indices: y = Y[y_j] if y[0] != y[1]: if x_i_j < n_i: # not mapped with the diag @@ -192,16 +245,20 @@ def _plot_barycenter(X, Y, matchings): ax.plot([y[0], x[0]], [y[1], x[1]], c='black', linestyle="dashed") - ax.scatter(Y[:,0], Y[:,1], color='purple', marker='d') + ax.scatter(Y[:,0], Y[:,1], color='purple', marker='d', zorder=2) - for dgm in X: - ax.scatter(dgm[:,0], dgm[:,1], marker ='o') + for X_i in X: + if X_i.size > 0: + ax.scatter(X_i[:,0], X_i[:,1], marker ='o', zorder=2) shift = 0.1 # for improved rendering - xmin = min([np.min(x[:,0]) for x in X]) - shift - xmax = max([np.max(x[:,0]) for x in X]) + shift - ymin = min([np.max(x[:,1]) for x in X]) - shift - ymax = max([np.max(x[:,1]) for x in X]) + shift + try: + xmin = np.min(np.array([np.min(x[:,0]) for x in X if len(x) > 0]) - shift) + xmax = np.max(np.array([np.max(x[:,0]) for x in X if len(x) > 0]) + shift) + ymin = np.min(np.array([np.max(x[:,1]) for x in X if len(x) > 0]) - shift) + ymax = np.max(np.array([np.max(x[:,1]) for x in X if len(x) > 0]) + shift) + except ValueError: # to handle the pecular case where we only average empty diagrams. + xmin, xmax, ymin, ymax = 0, 1, 0, 1 themin = min(xmin, ymin) themax = max(xmax, ymax) ax.set_xlim(themin, themax) @@ -212,12 +269,71 @@ def _plot_barycenter(X, Y, matchings): ax.set_aspect('equal', adjustable='box') ax.set_title("Estimated barycenter") + plt.show() + + +def _test_perf(): + nb_repeat = 10 + nb_points_in_dgm = [5, 10, 20, 50, 100] + nb_dmg = [3, 5, 10, 20] + + from time import time + for m in nb_dmg: + for n in nb_points_in_dgm: + tstart = time() + for _ in range(nb_repeat): + X = [np.random.rand(n, 2) for _ in range(m)] + for diag in X: + #enforce having diagrams + diag[:,1] = diag[:,1] + diag[:,0] + _ = lagrangian_barycenter(X) + tend = time() + print("Computation of barycenter in %s sec, with k = %s diags and n = %s points per diag."%(np.round((tend - tstart)/nb_repeat, 2), m, n)) + print("********************") + + +def _sanity_check(verbose): + #dg1 = np.array([[0.2, 0.5]]) + #dg2 = np.array([[0.2, 0.7]]) + #dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + #dg4 = np.array([[0.72, 0.82]]) + #X = [dg1, dg2, dg3, dg4] + #Y, a = lagrangian_barycenter(X, verbose=verbose) + #_plot_barycenter(X, Y, a) + + #dg1 = np.array([[0.2, 0.5]]) + #dg2 = np.array([]) # The empty diagram + #dg3 = np.array([[0.4, 0.8]]) + #X = [dg1, dg2, dg3] + #Y, a = lagrangian_barycenter(X, verbose=verbose) + #_plot_barycenter(X, Y, a) + + #dg1 = np.array([]) + #dg2 = np.array([]) # The empty diagram + #dg3 = np.array([]) + #X = [dg1, dg2, dg3] + #Y, a = lagrangian_barycenter(X, verbose=verbose) + #_plot_barycenter(X, Y, a) + + #dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) + #dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) + #dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) + #X = [dg1, dg2, dg3] + #Y, a = lagrangian_barycenter(X, init=1, verbose=verbose) + #_plot_barycenter(X, Y, a) + + + dg1 = np.array([[0.2, 0.5]]) + dg2 = np.array([[0.2, 0.7]]) + dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + dg4 = np.array([]) + + bary = lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3) + + message = "Wasserstein barycenter estimated:" + print(message) + print(bary) if __name__=="__main__": - dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) - dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) - dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) - X = [dg1, dg2, dg3] - Y, a, e = lagrangian_barycenter(X, verbose=True) - _plot_barycenter(X, Y, a) - plt.show() + _sanity_check(verbose = True) + #_test_perf() -- cgit v1.2.3 From 56a9294ede73d0660ba724b4f448c02dcd5e3dcc Mon Sep 17 00:00:00 2001 From: tlacombe Date: Thu, 5 Dec 2019 18:52:16 +0100 Subject: added image for barycenter in the /img repository --- src/python/doc/barycenter_sum.inc | 6 ++++-- src/python/doc/img/barycenter.png | Bin 0 -> 12433 bytes src/python/gudhi/barycenter.py | 33 ++++++++++++++++----------------- 3 files changed, 20 insertions(+), 19 deletions(-) create mode 100644 src/python/doc/img/barycenter.png (limited to 'src/python') diff --git a/src/python/doc/barycenter_sum.inc b/src/python/doc/barycenter_sum.inc index 7801a845..afac07d7 100644 --- a/src/python/doc/barycenter_sum.inc +++ b/src/python/doc/barycenter_sum.inc @@ -3,7 +3,7 @@ +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ | .. figure:: | A Frechet mean (or barycenter) is a generalization of the arithmetic | :Author: Theo Lacombe | - | ../../doc/Barycenter/barycenter.png | mean in a non linear space such as the one of persistence diagrams. | | + | ./img/barycenter.png | mean in a non linear space such as the one of persistence diagrams. | | | :figclass: align-center | Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is | :Introduced in: GUDHI 3.1.0 | | | defined as a minimizer of the variance functional, that is of | | | Illustration of Frechet mean between persistence | :math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. | :Copyright: MIT | @@ -14,7 +14,9 @@ | | -lable is based on [Turner et al, 2014], and uses an EM-scheme to | | | | provide a local minimum of the variance functional (somewhat similar | | | | to the Lloyd algorithm to estimate a solution to the k-means | | - | | problem). The combinatorial structure of the algorithm limits its | | + | | problem). The local minimum returned depends on the initialization of| | + | | the barycenter. | | + | | The combinatorial structure of the algorithm limits its | | | | scaling on large scale problems (thousands of diagrams and of points | | | | per diagram). | | +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ diff --git a/src/python/doc/img/barycenter.png b/src/python/doc/img/barycenter.png new file mode 100644 index 00000000..cad6af70 Binary files /dev/null and b/src/python/doc/img/barycenter.png differ diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 3cd214a7..b4afdb6a 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -293,13 +293,12 @@ def _test_perf(): def _sanity_check(verbose): - #dg1 = np.array([[0.2, 0.5]]) - #dg2 = np.array([[0.2, 0.7]]) - #dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) - #dg4 = np.array([[0.72, 0.82]]) - #X = [dg1, dg2, dg3, dg4] - #Y, a = lagrangian_barycenter(X, verbose=verbose) - #_plot_barycenter(X, Y, a) + dg1 = np.array([[0.2, 0.5]]) + dg2 = np.array([[0.2, 0.7], [0.73, 0.88]]) + dg3 = np.array([[0.3, 0.6], [0.7, 0.85], [0.2, 0.3]]) + X = [dg1, dg2, dg3] + Y, a = lagrangian_barycenter(X, verbose=verbose) + _plot_barycenter(X, Y, a) #dg1 = np.array([[0.2, 0.5]]) #dg2 = np.array([]) # The empty diagram @@ -323,16 +322,16 @@ def _sanity_check(verbose): #_plot_barycenter(X, Y, a) - dg1 = np.array([[0.2, 0.5]]) - dg2 = np.array([[0.2, 0.7]]) - dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) - dg4 = np.array([]) - - bary = lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3) - - message = "Wasserstein barycenter estimated:" - print(message) - print(bary) + #dg1 = np.array([[0.2, 0.5]]) + #dg2 = np.array([[0.2, 0.7]]) + #dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + #dg4 = np.array([]) + # + #bary, a = lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=True) + #_plot_barycenter([dg1, dg2, dg3, dg4], bary, a) + #message = "Wasserstein barycenter estimated:" + #print(message) + #print(bary) if __name__=="__main__": _sanity_check(verbose = True) -- cgit v1.2.3 From aba9ad68394b0c5aae22c450cac7162733132002 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Thu, 5 Dec 2019 18:55:46 +0100 Subject: correction of bibliography --- src/python/doc/barycenter_user.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst index fae2854a..1c4cb812 100644 --- a/src/python/doc/barycenter_user.rst +++ b/src/python/doc/barycenter_user.rst @@ -9,7 +9,7 @@ Definition .. include:: wasserstein_distance_sum.inc -This implementation is based on ideas from "Large Scale Computation of Means and Cluster for Persistence Diagrams via Optimal Transport". +This implementation is based on ideas from "Frechet means for distribution of persistence diagrams", Turner et al. 2014. Function -------- -- cgit v1.2.3 From 5877b4d3b7aca645ba906dfe0be598b1881d8798 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Dec 2019 17:53:59 +0100 Subject: update CMakeLists and create test_wasserstein_bary --- src/python/CMakeLists.txt | 3 +++ src/python/gudhi/barycenter.py | 26 ++++++++++---------- src/python/test/test_wasserstein_barycenter.py | 33 ++++++++++++++++++++++++++ 3 files changed, 50 insertions(+), 12 deletions(-) create mode 100755 src/python/test/test_wasserstein_barycenter.py (limited to 'src/python') diff --git a/src/python/CMakeLists.txt b/src/python/CMakeLists.txt index 9af85eac..7f9ff38f 100644 --- a/src/python/CMakeLists.txt +++ b/src/python/CMakeLists.txt @@ -52,6 +52,7 @@ if(PYTHONINTERP_FOUND) # Modules that should not be auto-imported in __init__.py set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'representations', ") set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'wasserstein', ") + set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'barycenter', ") add_gudhi_debug_info("Python version ${PYTHON_VERSION_STRING}") add_gudhi_debug_info("Cython version ${CYTHON_VERSION}") @@ -210,6 +211,7 @@ if(PYTHONINTERP_FOUND) file(COPY "gudhi/persistence_graphical_tools.py" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") file(COPY "gudhi/representations" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi/") file(COPY "gudhi/wasserstein.py" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") + file(COPY "gudhi/barycenter.py" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") add_custom_command( OUTPUT gudhi.so @@ -385,6 +387,7 @@ if(PYTHONINTERP_FOUND) # Wasserstein if(OT_FOUND) add_gudhi_py_test(test_wasserstein_distance) + add_gudhi_py_test(test_wasserstein_barycenter) endif(OT_FOUND) # Representations diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index b4afdb6a..41418454 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -293,12 +293,12 @@ def _test_perf(): def _sanity_check(verbose): - dg1 = np.array([[0.2, 0.5]]) - dg2 = np.array([[0.2, 0.7], [0.73, 0.88]]) - dg3 = np.array([[0.3, 0.6], [0.7, 0.85], [0.2, 0.3]]) - X = [dg1, dg2, dg3] - Y, a = lagrangian_barycenter(X, verbose=verbose) - _plot_barycenter(X, Y, a) + #dg1 = np.array([[0.2, 0.5]]) + #dg2 = np.array([[0.2, 0.7], [0.73, 0.88]]) + #dg3 = np.array([[0.3, 0.6], [0.7, 0.85], [0.2, 0.3]]) + #X = [dg1, dg2, dg3] + #Y, a = lagrangian_barycenter(X, verbose=verbose) + #_plot_barycenter(X, Y, a) #dg1 = np.array([[0.2, 0.5]]) #dg2 = np.array([]) # The empty diagram @@ -313,13 +313,15 @@ def _sanity_check(verbose): #X = [dg1, dg2, dg3] #Y, a = lagrangian_barycenter(X, verbose=verbose) #_plot_barycenter(X, Y, a) + #print(Y) - #dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) - #dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) - #dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) - #X = [dg1, dg2, dg3] - #Y, a = lagrangian_barycenter(X, init=1, verbose=verbose) - #_plot_barycenter(X, Y, a) + dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) + dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) + dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) + X = [dg3] + Y, a = lagrangian_barycenter(X, verbose=verbose) + _plot_barycenter(X, Y, a) + print(Y) #dg1 = np.array([[0.2, 0.5]]) diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py new file mode 100755 index 00000000..6074f250 --- /dev/null +++ b/src/python/test/test_wasserstein_barycenter.py @@ -0,0 +1,33 @@ +from gudhi.barycenter import lagrangian_barycenter +import numpy as np + +""" This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + Author(s): Theo Lacombe + + Copyright (C) 2019 Inria + + Modification(s): + - YYYY/MM Author: Description of the modification +""" + +__author__ = "Theo Lacombe" +__copyright__ = "Copyright (C) 2019 Inria" +__license__ = "MIT" + + +def test_lagrangian_barycenter(): + + dg1 = np.array([[0.2, 0.5]]) + dg2 = np.array([[0.2, 0.7]]) + dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + dg4 = np.array([]) + dg5 = np.array([]) + dg6 = np.array([]) + res = np.array([[0.27916667, 0.55416667], [0.7375, 0.7625], [0.2375, 0.2625]]) + + dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) + + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < 0.001 + assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.array([])) + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < 0.001 -- cgit v1.2.3 From b4fcc875393df12f42aea84b918b5b35f99f7283 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Dec 2019 18:11:27 +0100 Subject: correction of typo in _user.rst and of empty array shape in test_wasserstein_barycenter --- src/python/doc/barycenter_user.rst | 2 +- src/python/test/test_wasserstein_barycenter.py | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst index 1c4cb812..5344583f 100644 --- a/src/python/doc/barycenter_user.rst +++ b/src/python/doc/barycenter_user.rst @@ -33,7 +33,7 @@ Note that persistence diagrams must be submitted as (n x 2) numpy arrays and mus dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) dg4 = np.array([]) - bary = gudhi.barycenter.lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3)) + bary = gudhi.barycenter.lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3) message = "Wasserstein barycenter estimated:" print(message) diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index 6074f250..ae3f6579 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -29,5 +29,5 @@ def test_lagrangian_barycenter(): dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < 0.001 - assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.array([])) + assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), shape=(0,2), np.array([])) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < 0.001 -- cgit v1.2.3 From 0c2fdc65cc1ea676fa8d11c24bba0d34eb5b7a3c Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Dec 2019 18:34:24 +0100 Subject: Correction of typo in barycenter_user --- src/python/doc/barycenter_user.rst | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst index 5344583f..714d807e 100644 --- a/src/python/doc/barycenter_user.rst +++ b/src/python/doc/barycenter_user.rst @@ -2,12 +2,12 @@ .. To get rid of WARNING: document isn't included in any toctree -Wasserstein distance user manual +Barycenter user manual ================================ Definition ---------- -.. include:: wasserstein_distance_sum.inc +.. include:: barycenter_sum.inc This implementation is based on ideas from "Frechet means for distribution of persistence diagrams", Turner et al. 2014. -- cgit v1.2.3 From 20047b94e693f31fd88ca142ba7256767ac753eb Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Dec 2019 18:34:55 +0100 Subject: correction of typo in test_wasserstein_barycenter --- src/python/test/test_wasserstein_barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index ae3f6579..dc82a57c 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -29,5 +29,5 @@ def test_lagrangian_barycenter(): dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < 0.001 - assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), shape=(0,2), np.array([])) + assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.array([], shape=(0,2))) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < 0.001 -- cgit v1.2.3 From b23813b90aaf1b0ce2b21bdfb33d2a6ea5bfe4cc Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Dec 2019 19:32:26 +0100 Subject: correction test --- src/python/gudhi/barycenter.py | 6 ++++-- src/python/test/test_wasserstein_barycenter.py | 2 +- 2 files changed, 5 insertions(+), 3 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 41418454..b76166c0 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -318,10 +318,12 @@ def _sanity_check(verbose): dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) - X = [dg3] + dg4 = np.array([]) + X = [dg4] Y, a = lagrangian_barycenter(X, verbose=verbose) - _plot_barycenter(X, Y, a) + #_plot_barycenter(X, Y, a) print(Y) + print(np.array_equal(Y, np.empty(shape=(0,2) ))) #dg1 = np.array([[0.2, 0.5]]) diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index dc82a57c..910d23ff 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -29,5 +29,5 @@ def test_lagrangian_barycenter(): dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < 0.001 - assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.array([], shape=(0,2))) + assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.empty(shape=(0,2))) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < 0.001 -- cgit v1.2.3 From d91585af64805a11a4d446d9e3f6467f3394d0c6 Mon Sep 17 00:00:00 2001 From: Théo Lacombe Date: Tue, 17 Dec 2019 18:58:48 +0100 Subject: Update src/python/gudhi/barycenter.py correction of typo Co-Authored-By: Marc Glisse --- src/python/gudhi/barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index b76166c0..43602a6e 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -114,7 +114,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): """ Compute the estimated barycenter computed with the algorithm provided by Turner et al (2014). - It is a local minima of the corresponding Frechet function. + It is a local minimum of the corresponding Frechet function. :param pdiagset: a list of size N containing numpy.array of shape (n x 2) (n can variate), encoding a set of persistence diagrams with only finite coordinates. -- cgit v1.2.3 From 180add9067bc9bd0609362717972eeeb8d2f6713 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Thu, 19 Dec 2019 17:25:01 +0100 Subject: clean code and doc --- src/python/gudhi/barycenter.py | 129 ++++++++++++----------------------------- 1 file changed, 36 insertions(+), 93 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 43602a6e..c2173dba 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -58,12 +58,13 @@ def _build_dist_matrix(X, Y, p=2., q=2.): return Cf -def _optimal_matching(X, Y): +def _optimal_matching(X, Y, withcost=False): """ :param X: numpy.array of size (n x 2) :param Y: numpy.array of size (m x 2) + :param withcost: returns also the cost corresponding to this optimal matching :returns: numpy.array of shape (k x 2) encoding the list of edges in the optimal matching. - That is, [[(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] + That is, [(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] if i > len(X) or j > len(Y), it means they represent the diagonal. """ @@ -74,10 +75,10 @@ def _optimal_matching(X, Y): if Y.size == 0: # Y is empty return np.array([[0,0]]) # the diagonal is matched to the diagonal and that's it... else: - return np.column_stack([np.zeros(m+1, dtype=int), np.arange(m+1, dtype=int)]) # TO BE CORRECTED + return np.column_stack([np.zeros(m+1, dtype=int), np.arange(m+1, dtype=int)]) elif Y.size == 0: # X is not empty but Y is empty - return np.column_stack([np.zeros(n+1, dtype=int), np.arange(n+1, dtype=int)]) # TO BE CORRECTED - + return np.column_stack([np.zeros(n+1, dtype=int), np.arange(n+1, dtype=int)]) + # we know X, Y are not empty diags now M = _build_dist_matrix(X, Y) @@ -86,12 +87,16 @@ def _optimal_matching(X, Y): 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 P = ot.emd(a=a, b=b, M=M)*(n+m) - # Note : it seems POT return a permutation matrix in this situation, - # ...guarantee...? - # It should be enough to check that the algorithm only iterates on vertices of the transportation polytope. + # Note : it seems POT return a permutation matrix in this situation, ie a vertex of the constraint set (generically true). + if withcost: + cost = np.sqrt(np.sum(np.multiply(P, M))) P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to be improved. # return the list of (i,j) such that P[i,j] > 0, i.e. x_i is matched to y_j (should it be the diag). res = np.nonzero(P) + + if withcost: + return np.column_stack(res), cost + return np.column_stack(res) @@ -123,13 +128,16 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): Otherwise, it must be an int (then we init with diagset[init]) or a (n x 2) numpy.array enconding a persistence diagram with n points. :param verbose: if True, returns additional information about the - barycenters (assignment and energy). + barycenter. :returns: If not verbose (default), a numpy.array encoding the barycenter estimate (local minima of the energy function). - If verbose, returns a triplet (Y, a, e) - where Y is the barycenter estimate, a is the assignments between the - points of Y and thoses of the diagrams, - and e is the energy value reached by the estimate. + If verbose, returns a couple (Y, log) + where Y is the barycenter estimate, + and log is a dict that contains additional informations: + - assigments, a list of list of pairs (i,j), + That is, a[k] = [(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] + if i > len(X) or j > len(Y), it means they represent the diagonal. + - energy, a float representing the Frechet mean value obtained. """ X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging @@ -200,25 +208,29 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): if verbose: - matchings = [] - #energy = 0 + groupings = [] + energy = 0 + log = {} n_y = len(Y) for i in range(m): - edges = _optimal_matching(Y, X[i]) - matchings.append([x_i_j for (y_j, x_i_j) in enumerate(edges) if y_j < n_y]) - # energy += sum([M[i,j] for i,j in enumerate(edges)]) - - # energy = energy/m - return Y, matchings #, energy + edges, cost = _optimal_matching(Y, X[i], withcost=True) + print(edges) + groupings.append([x_i_j for (y_j, x_i_j) in enumerate(edges) if y_j < n_y]) + energy += cost + log["groupings"] = groupings + energy = energy/m + log["energy"] = energy + + return Y, log else: return Y -def _plot_barycenter(X, Y, matchings): +def _plot_barycenter(X, Y, groupings): """ :param X: list of persistence diagrams. :param Y: numpy.array of (n x 2). Aims to be an estimate of the barycenter returned by lagrangian_barycenter(X, verbose=True). - :param matchings: list of lists, such that L[k][i] = j if and only if + :param groupings: list of lists, such that L[k][i] = j if and only if the i-th point of the barycenter is grouped with the j-th point of the k-th diagram. """ @@ -232,7 +244,7 @@ def _plot_barycenter(X, Y, matchings): # n_y = len(Y.points) for i in range(len(X)): - indices = matchings[i] + indices = groupings[i] n_i = len(X[i]) for (y_j, x_i_j) in indices: @@ -271,72 +283,3 @@ def _plot_barycenter(X, Y, matchings): plt.show() - -def _test_perf(): - nb_repeat = 10 - nb_points_in_dgm = [5, 10, 20, 50, 100] - nb_dmg = [3, 5, 10, 20] - - from time import time - for m in nb_dmg: - for n in nb_points_in_dgm: - tstart = time() - for _ in range(nb_repeat): - X = [np.random.rand(n, 2) for _ in range(m)] - for diag in X: - #enforce having diagrams - diag[:,1] = diag[:,1] + diag[:,0] - _ = lagrangian_barycenter(X) - tend = time() - print("Computation of barycenter in %s sec, with k = %s diags and n = %s points per diag."%(np.round((tend - tstart)/nb_repeat, 2), m, n)) - print("********************") - - -def _sanity_check(verbose): - #dg1 = np.array([[0.2, 0.5]]) - #dg2 = np.array([[0.2, 0.7], [0.73, 0.88]]) - #dg3 = np.array([[0.3, 0.6], [0.7, 0.85], [0.2, 0.3]]) - #X = [dg1, dg2, dg3] - #Y, a = lagrangian_barycenter(X, verbose=verbose) - #_plot_barycenter(X, Y, a) - - #dg1 = np.array([[0.2, 0.5]]) - #dg2 = np.array([]) # The empty diagram - #dg3 = np.array([[0.4, 0.8]]) - #X = [dg1, dg2, dg3] - #Y, a = lagrangian_barycenter(X, verbose=verbose) - #_plot_barycenter(X, Y, a) - - #dg1 = np.array([]) - #dg2 = np.array([]) # The empty diagram - #dg3 = np.array([]) - #X = [dg1, dg2, dg3] - #Y, a = lagrangian_barycenter(X, verbose=verbose) - #_plot_barycenter(X, Y, a) - #print(Y) - - dg1 = np.array([[0.1, 0.12], [0.21, 0.7], [0.4, 0.5], [0.3, 0.4], [0.35, 0.7], [0.5, 0.55], [0.32, 0.42], [0.1, 0.4], [0.2, 0.4]]) - dg2 = np.array([[0.09, 0.11], [0.3, 0.43], [0.5, 0.61], [0.3, 0.7], [0.42, 0.5], [0.35, 0.41], [0.74, 0.9], [0.5, 0.95], [0.35, 0.45], [0.13, 0.48], [0.32, 0.45]]) - dg3 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) - dg4 = np.array([]) - X = [dg4] - Y, a = lagrangian_barycenter(X, verbose=verbose) - #_plot_barycenter(X, Y, a) - print(Y) - print(np.array_equal(Y, np.empty(shape=(0,2) ))) - - - #dg1 = np.array([[0.2, 0.5]]) - #dg2 = np.array([[0.2, 0.7]]) - #dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) - #dg4 = np.array([]) - # - #bary, a = lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=True) - #_plot_barycenter([dg1, dg2, dg3, dg4], bary, a) - #message = "Wasserstein barycenter estimated:" - #print(message) - #print(bary) - -if __name__=="__main__": - _sanity_check(verbose = True) - #_test_perf() -- cgit v1.2.3 From b7138871d42197c94c58b9938279455b75723606 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Thu, 19 Dec 2019 17:28:06 +0100 Subject: removed plot barycenter. Will be integrated in a tutorial --- src/python/gudhi/barycenter.py | 58 ------------------------------------------ 1 file changed, 58 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index c2173dba..11098afe 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -225,61 +225,3 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): else: return Y -def _plot_barycenter(X, Y, groupings): - """ - :param X: list of persistence diagrams. - :param Y: numpy.array of (n x 2). Aims to be an estimate of the barycenter - returned by lagrangian_barycenter(X, verbose=True). - :param groupings: list of lists, such that L[k][i] = j if and only if - the i-th point of the barycenter is grouped with the j-th point of the k-th - diagram. - """ - # import matplotlib now to avoid useless dependancies - - import matplotlib.pyplot as plt - from matplotlib.patches import Polygon - - fig = plt.figure() - ax = fig.add_subplot(111) - - # n_y = len(Y.points) - for i in range(len(X)): - indices = groupings[i] - n_i = len(X[i]) - - for (y_j, x_i_j) in indices: - y = Y[y_j] - if y[0] != y[1]: - if x_i_j < n_i: # not mapped with the diag - x = X[i][x_i_j] - else: # y_j is matched to the diagonal - x = _proj_on_diag(y) - ax.plot([y[0], x[0]], [y[1], x[1]], c='black', - linestyle="dashed") - - ax.scatter(Y[:,0], Y[:,1], color='purple', marker='d', zorder=2) - - for X_i in X: - if X_i.size > 0: - ax.scatter(X_i[:,0], X_i[:,1], marker ='o', zorder=2) - - shift = 0.1 # for improved rendering - try: - xmin = np.min(np.array([np.min(x[:,0]) for x in X if len(x) > 0]) - shift) - xmax = np.max(np.array([np.max(x[:,0]) for x in X if len(x) > 0]) + shift) - ymin = np.min(np.array([np.max(x[:,1]) for x in X if len(x) > 0]) - shift) - ymax = np.max(np.array([np.max(x[:,1]) for x in X if len(x) > 0]) + shift) - except ValueError: # to handle the pecular case where we only average empty diagrams. - xmin, xmax, ymin, ymax = 0, 1, 0, 1 - themin = min(xmin, ymin) - themax = max(xmax, ymax) - ax.set_xlim(themin, themax) - ax.set_ylim(themin, themax) - ax.add_patch(Polygon([[themin,themin], [themax,themin], [themax,themax]], fill=True, color='lightgrey')) - ax.set_xticks([]) - ax.set_yticks([]) - ax.set_aspect('equal', adjustable='box') - ax.set_title("Estimated barycenter") - - plt.show() - -- cgit v1.2.3 From 85ceea9512634a62664208cd2d0f1ce48bafa171 Mon Sep 17 00:00:00 2001 From: mathieu Date: Thu, 16 Jan 2020 17:02:55 -0500 Subject: added wasserstein class --- .../diagram_vectorizations_distances_kernels.py | 7 ++- src/python/gudhi/representations/metrics.py | 59 ++++++++++++++++++++++ 2 files changed, 65 insertions(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/example/diagram_vectorizations_distances_kernels.py b/src/python/example/diagram_vectorizations_distances_kernels.py index 119072eb..66c32cc2 100755 --- a/src/python/example/diagram_vectorizations_distances_kernels.py +++ b/src/python/example/diagram_vectorizations_distances_kernels.py @@ -9,7 +9,7 @@ from gudhi.representations import DiagramSelector, Clamping, Landscape, Silhouet TopologicalVector, DiagramScaler, BirthPersistenceTransform,\ PersistenceImage, PersistenceWeightedGaussianKernel, Entropy, \ PersistenceScaleSpaceKernel, SlicedWassersteinDistance,\ - SlicedWassersteinKernel, BottleneckDistance, PersistenceFisherKernel + SlicedWassersteinKernel, BottleneckDistance, WassersteinDistance, PersistenceFisherKernel D = np.array([[0.,4.],[1.,2.],[3.,8.],[6.,8.], [0., np.inf], [5., np.inf]]) diags = [D] @@ -117,6 +117,11 @@ X = SW.fit(diags) Y = SW.transform(diags2) print("SW kernel is " + str(Y[0][0])) +W = WassersteinDistance(order=2, internal_p=2) +X = W.fit(diags) +Y = W.transform(diags2) +print("Wasserstein distance is " + str(Y[0][0])) + W = BottleneckDistance(epsilon=.001) X = W.fit(diags) Y = W.transform(diags2) diff --git a/src/python/gudhi/representations/metrics.py b/src/python/gudhi/representations/metrics.py index 5f9ec6ab..290c1d07 100644 --- a/src/python/gudhi/representations/metrics.py +++ b/src/python/gudhi/representations/metrics.py @@ -10,6 +10,7 @@ import numpy as np from sklearn.base import BaseEstimator, TransformerMixin from sklearn.metrics import pairwise_distances +from gudhi.wasserstein import wasserstein_distance try: from .. import bottleneck_distance USE_GUDHI = True @@ -145,6 +146,64 @@ class BottleneckDistance(BaseEstimator, TransformerMixin): return Xfit +class WassersteinDistance(BaseEstimator, TransformerMixin): + """ + This is a class for computing the Wasserstein distance matrix from a list of persistence diagrams. + """ + def __init__(self, order=2, internal_p=2): + """ + Constructor for the WassersteinDistance class. + + Parameters: + order (int): exponent for Wasserstein, default value is 2., see :func:`gudhi.wasserstein.wasserstein_distance`. + internal_p (int): ground metric on the (upper-half) plane (i.e. norm l_p in R^2), default value is 2 (euclidean norm), see :func:`gudhi.wasserstein.wasserstein_distance`. + """ + self.order, self.internal_p = order, internal_p + + def fit(self, X, y=None): + """ + Fit the WassersteinDistance class on a list of persistence diagrams: persistence diagrams are stored in a numpy array called **diagrams**. + + Parameters: + X (list of n x 2 numpy arrays): input persistence diagrams. + y (n x 1 array): persistence diagram labels (unused). + """ + self.diagrams_ = X + return self + + def transform(self, X): + """ + Compute all Wasserstein distances between the persistence diagrams that were stored after calling the fit() method, and a given list of (possibly different) persistence diagrams. + + Parameters: + X (list of n x 2 numpy arrays): input persistence diagrams. + + Returns: + numpy array of shape (number of diagrams in **diagrams**) x (number of diagrams in X): matrix of pairwise Wasserstein distances. + """ + num_diag1 = len(X) + + #if len(self.diagrams_) == len(X) and np.all([np.array_equal(self.diagrams_[i], X[i]) for i in range(len(X))]): + if X is self.diagrams_: + matrix = np.zeros((num_diag1, num_diag1)) + + for i in range(num_diag1): + for j in range(i+1, num_diag1): + matrix[i,j] = wasserstein_distance(X[i], X[j], self.order, self.internal_p) + matrix[j,i] = matrix[i,j] + + else: + num_diag2 = len(self.diagrams_) + matrix = np.zeros((num_diag1, num_diag2)) + + for i in range(num_diag1): + for j in range(num_diag2): + matrix[i,j] = wasserstein_distance(X[i], self.diagrams_[j], self.order, self.internal_p) + + Xfit = matrix + + return Xfit + class PersistenceFisherDistance(BaseEstimator, TransformerMixin): """ This is a class for computing the persistence Fisher distance matrix from a list of persistence diagrams. The persistence Fisher distance is obtained by computing the original Fisher distance between the probability distributions associated to the persistence diagrams given by convolving them with a Gaussian kernel. See http://papers.nips.cc/paper/8205-persistence-fisher-kernel-a-riemannian-manifold-kernel-for-persistence-diagrams for more details. -- cgit v1.2.3 From 6a6bed7ca21c1ffcf6de9ed09c2a6512ecb66585 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 17 Jan 2020 15:37:03 +0100 Subject: improving doc output --- src/python/doc/barycenter_sum.inc | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_sum.inc b/src/python/doc/barycenter_sum.inc index afac07d7..da2bdd84 100644 --- a/src/python/doc/barycenter_sum.inc +++ b/src/python/doc/barycenter_sum.inc @@ -7,11 +7,11 @@ | :figclass: align-center | Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is | :Introduced in: GUDHI 3.1.0 | | | defined as a minimizer of the variance functional, that is of | | | Illustration of Frechet mean between persistence | :math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. | :Copyright: MIT | - | diagrams. | where :math:`d_2` denotes the Wasserstein-2 distance between persis- | | - | | tence diagrams. | | + | diagrams. | where :math:`d_2` denotes the Wasserstein-2 distance between | | + | | persistence diagrams. | | | | It is known to exist and is generically unique. However, an exact | | - | | computation is in general untractable. Current implementation avai- | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | - | | -lable is based on [Turner et al, 2014], and uses an EM-scheme to | | + | | computation is in general untractable. Current implementation | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | + | | available is based on [Turner et al, 2014], and uses an EM-scheme to | | | | provide a local minimum of the variance functional (somewhat similar | | | | to the Lloyd algorithm to estimate a solution to the k-means | | | | problem). The local minimum returned depends on the initialization of| | -- cgit v1.2.3 From 4c0e6e4144dd3cf6da9600fd4b9bbcac5e664b73 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Sun, 26 Jan 2020 02:54:35 -0500 Subject: added extended persistence function --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 71 +++++++++++++++++++++++++++ src/python/gudhi/simplex_tree.pxd | 2 + src/python/gudhi/simplex_tree.pyx | 14 ++++++ 3 files changed, 87 insertions(+) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 76608008..4786b244 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -125,6 +125,8 @@ class Simplex_tree { private: typedef typename Dictionary::iterator Dictionary_it; typedef typename Dictionary_it::value_type Dit_value_t; + double minval_; + double maxval_; struct return_first { Vertex_handle operator()(const Dit_value_t& p_sh) const { @@ -1465,6 +1467,75 @@ class Simplex_tree { } } + /** \brief Retrieve good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. Need extend_filtration to be called first! + * @param[in] dgm Persistence diagram obtained after calling this->extend_filtration and this->get_persistence. + * @return A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. + */ + std::vector>>> convert(const std::vector>>& dgm){ + std::vector>>> new_dgm(4); double x, y; + for(unsigned int i = 0; i < dgm.size(); i++){ int h = dgm[i].first; double px = dgm[i].second.first; double py = dgm[i].second.second; + if(std::isinf(py)) continue; + else{ + if ((px <= -1) & (py <= -1)){x = minval_ + (maxval_-minval_)*(px + 2); y = minval_ + (maxval_-minval_)*(py + 2); new_dgm[0].push_back(std::make_pair(h, std::make_pair(x,y))); } + if ((px >= 1) & (py >= 1)){x = minval_ - (maxval_-minval_)*(px - 2); y = minval_ - (maxval_-minval_)*(py - 2); new_dgm[1].push_back(std::make_pair(h, std::make_pair(x,y))); } + if ((px <= -1) & (py >= 1)){x = minval_ + (maxval_-minval_)*(px + 2); y = minval_ - (maxval_-minval_)*(py - 2); + if (x <= y) new_dgm[2].push_back(std::make_pair(h, std::make_pair(x,y))); + else new_dgm[3].push_back(std::make_pair(h, std::make_pair(x,y))); + } + } + } + return new_dgm; + } + + /** \brief Extend filtration for computing extended persistence. + */ + void extend_filtration() { + + // Compute maximum and minimum of filtration values + int maxvert = -std::numeric_limits::infinity(); + std::vector filt; + for (auto sh : this->complex_simplex_range()) {if (this->dimension(sh) == 0){filt.push_back(this->filtration(sh)); maxvert = std::max(*this->simplex_vertex_range(sh).begin(), maxvert);}} + minval_ = *std::min_element(filt.begin(), filt.end()); + maxval_ = *std::max_element(filt.begin(), filt.end()); + maxvert += 1; + + // Compute vectors of integers corresponding to the Simplex handles + std::vector > splxs; + for (auto sh : this->complex_simplex_range()) { + std::vector vr; for (auto vh : this->simplex_vertex_range(sh)){vr.push_back(vh);} + splxs.push_back(vr); + } + + // Add point for coning the simplicial complex + int count = this->num_simplices(); + std::vector cone; cone.push_back(maxvert); auto ins = this->insert_simplex(cone, -3); this->assign_key(ins.first, count); count++; + + // For each simplex + for (auto vr : splxs){ + // Create cone on simplex + auto sh = this->find(vr); vr.push_back(maxvert); + if (this->dimension(sh) == 0){ + // Assign ascending value between -2 and -1 to vertex + double v = this->filtration(sh); + this->assign_filtration(sh, -2 + (v-minval_)/(maxval_-minval_)); + // Assign descending value between 1 and 2 to cone on vertex + auto ins = this->insert_simplex(vr, 2 - (v-minval_)/(maxval_-minval_)); + this->assign_key(ins.first, count); + } + else{ + // Assign value -3 to simplex and cone on simplex + this->assign_filtration(sh, -3); + auto ins = this->insert_simplex(vr, -3); + this->assign_key(ins.first, count); + } + count++; + } + + this->make_filtration_non_decreasing(); this->initialize_filtration(); + + } + + private: Vertex_handle null_vertex_; /** \brief Total number of simplices in the complex, without the empty simplex.*/ diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 1066d44b..39f2a45f 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -43,6 +43,8 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": void remove_maximal_simplex(vector[int] simplex) bool prune_above_filtration(double filtration) bool make_filtration_non_decreasing() + void extend_filtration() + vector[vector[pair[int, pair[double, double]]]] convert(vector[pair[int, pair[double, double]]]) cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": cdef cppclass Simplex_tree_persistence_interface "Gudhi::Persistent_cohomology_interface>": diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index b18627c4..cfab14f4 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -386,6 +386,20 @@ cdef class SimplexTree: """ return self.get_ptr().make_filtration_non_decreasing() + def extend_filtration(self): + """ This function extends filtration for computing extended persistence. + """ + return self.get_ptr().extend_filtration() + + def convert(self, dgm): + """This function retrieves good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. Need extend_filtration to be called first! + + :param dgm: Persistence diagram obtained after calling this->extend_filtration and this->get_persistence. + :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. + """ + return self.get_ptr().convert(dgm) + + def persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): """This function returns the persistence of the simplicial complex. -- cgit v1.2.3 From 1dd1c554a962db70809eadb470eb2eaa733970d4 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Fri, 31 Jan 2020 14:59:32 -0500 Subject: revert first commit --- .../diagram_vectorizations_distances_kernels.py | 7 +-- src/python/gudhi/representations/metrics.py | 59 ---------------------- 2 files changed, 1 insertion(+), 65 deletions(-) (limited to 'src/python') diff --git a/src/python/example/diagram_vectorizations_distances_kernels.py b/src/python/example/diagram_vectorizations_distances_kernels.py index 66c32cc2..119072eb 100755 --- a/src/python/example/diagram_vectorizations_distances_kernels.py +++ b/src/python/example/diagram_vectorizations_distances_kernels.py @@ -9,7 +9,7 @@ from gudhi.representations import DiagramSelector, Clamping, Landscape, Silhouet TopologicalVector, DiagramScaler, BirthPersistenceTransform,\ PersistenceImage, PersistenceWeightedGaussianKernel, Entropy, \ PersistenceScaleSpaceKernel, SlicedWassersteinDistance,\ - SlicedWassersteinKernel, BottleneckDistance, WassersteinDistance, PersistenceFisherKernel + SlicedWassersteinKernel, BottleneckDistance, PersistenceFisherKernel D = np.array([[0.,4.],[1.,2.],[3.,8.],[6.,8.], [0., np.inf], [5., np.inf]]) diags = [D] @@ -117,11 +117,6 @@ X = SW.fit(diags) Y = SW.transform(diags2) print("SW kernel is " + str(Y[0][0])) -W = WassersteinDistance(order=2, internal_p=2) -X = W.fit(diags) -Y = W.transform(diags2) -print("Wasserstein distance is " + str(Y[0][0])) - W = BottleneckDistance(epsilon=.001) X = W.fit(diags) Y = W.transform(diags2) diff --git a/src/python/gudhi/representations/metrics.py b/src/python/gudhi/representations/metrics.py index 290c1d07..5f9ec6ab 100644 --- a/src/python/gudhi/representations/metrics.py +++ b/src/python/gudhi/representations/metrics.py @@ -10,7 +10,6 @@ import numpy as np from sklearn.base import BaseEstimator, TransformerMixin from sklearn.metrics import pairwise_distances -from gudhi.wasserstein import wasserstein_distance try: from .. import bottleneck_distance USE_GUDHI = True @@ -146,64 +145,6 @@ class BottleneckDistance(BaseEstimator, TransformerMixin): return Xfit -class WassersteinDistance(BaseEstimator, TransformerMixin): - """ - This is a class for computing the Wasserstein distance matrix from a list of persistence diagrams. - """ - def __init__(self, order=2, internal_p=2): - """ - Constructor for the WassersteinDistance class. - - Parameters: - order (int): exponent for Wasserstein, default value is 2., see :func:`gudhi.wasserstein.wasserstein_distance`. - internal_p (int): ground metric on the (upper-half) plane (i.e. norm l_p in R^2), default value is 2 (euclidean norm), see :func:`gudhi.wasserstein.wasserstein_distance`. - """ - self.order, self.internal_p = order, internal_p - - def fit(self, X, y=None): - """ - Fit the WassersteinDistance class on a list of persistence diagrams: persistence diagrams are stored in a numpy array called **diagrams**. - - Parameters: - X (list of n x 2 numpy arrays): input persistence diagrams. - y (n x 1 array): persistence diagram labels (unused). - """ - self.diagrams_ = X - return self - - def transform(self, X): - """ - Compute all Wasserstein distances between the persistence diagrams that were stored after calling the fit() method, and a given list of (possibly different) persistence diagrams. - - Parameters: - X (list of n x 2 numpy arrays): input persistence diagrams. - - Returns: - numpy array of shape (number of diagrams in **diagrams**) x (number of diagrams in X): matrix of pairwise Wasserstein distances. - """ - num_diag1 = len(X) - - #if len(self.diagrams_) == len(X) and np.all([np.array_equal(self.diagrams_[i], X[i]) for i in range(len(X))]): - if X is self.diagrams_: - matrix = np.zeros((num_diag1, num_diag1)) - - for i in range(num_diag1): - for j in range(i+1, num_diag1): - matrix[i,j] = wasserstein_distance(X[i], X[j], self.order, self.internal_p) - matrix[j,i] = matrix[i,j] - - else: - num_diag2 = len(self.diagrams_) - matrix = np.zeros((num_diag1, num_diag2)) - - for i in range(num_diag1): - for j in range(num_diag2): - matrix[i,j] = wasserstein_distance(X[i], self.diagrams_[j], self.order, self.internal_p) - - Xfit = matrix - - return Xfit - class PersistenceFisherDistance(BaseEstimator, TransformerMixin): """ This is a class for computing the persistence Fisher distance matrix from a list of persistence diagrams. The persistence Fisher distance is obtained by computing the original Fisher distance between the probability distributions associated to the persistence diagrams given by convolving them with a Gaussian kernel. See http://papers.nips.cc/paper/8205-persistence-fisher-kernel-a-riemannian-manifold-kernel-for-persistence-diagrams for more details. -- cgit v1.2.3 From 360cc2cc31e9e81b99f5c21aa2b4e79b066baabf Mon Sep 17 00:00:00 2001 From: mathieu Date: Tue, 4 Feb 2020 19:44:52 -0500 Subject: fixed Vincent's comments --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 74 ++++++++++++++++++----- src/python/gudhi/simplex_tree.pxd | 2 +- src/python/gudhi/simplex_tree.pyx | 14 +++-- src/python/test/test_simplex_tree.py | 86 +++++++++++++++++++++++++-- 4 files changed, 150 insertions(+), 26 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 301f7aae..42cf4246 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1467,34 +1467,68 @@ class Simplex_tree { } } - /** \brief Retrieve good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. Need extend_filtration to be called first! - * @param[in] dgm Persistence diagram obtained after calling this->extend_filtration and this->get_persistence. - * @return A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. + /** \brief Retrieve good values for extended persistence, and separate the + * diagrams into the ordinary, relative, extended+ and extended- subdiagrams. + * Need extend_filtration to be called first! + * @param[in] dgm Persistence diagram obtained after calling this->extend_filtration + * and this->get_persistence. + * @return A vector of four persistence diagrams. The first one is Ordinary, the + * second one is Relative, the third one is Extended+ and the fourth one is Extended-. */ std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm){ - std::vector>>> new_dgm(4); double x, y; - for(unsigned int i = 0; i < dgm.size(); i++){ int h = dgm[i].first; double px = dgm[i].second.first; double py = dgm[i].second.second; + std::vector>>> new_dgm(4); + double x, y; + for(unsigned int i = 0; i < dgm.size(); i++){ + int h = dgm[i].first; + double px = dgm[i].second.first; + double py = dgm[i].second.second; if(std::isinf(py)) continue; else{ - if ((px <= -1) & (py <= -1)){x = minval_ + (maxval_-minval_)*(px + 2); y = minval_ + (maxval_-minval_)*(py + 2); new_dgm[0].push_back(std::make_pair(h, std::make_pair(x,y))); } - if ((px >= 1) & (py >= 1)){x = minval_ - (maxval_-minval_)*(px - 2); y = minval_ - (maxval_-minval_)*(py - 2); new_dgm[1].push_back(std::make_pair(h, std::make_pair(x,y))); } - if ((px <= -1) & (py >= 1)){x = minval_ + (maxval_-minval_)*(px + 2); y = minval_ - (maxval_-minval_)*(py - 2); - if (x <= y) new_dgm[2].push_back(std::make_pair(h, std::make_pair(x,y))); - else new_dgm[3].push_back(std::make_pair(h, std::make_pair(x,y))); + if ((px <= -1) & (py <= -1)){ + x = minval_ + (maxval_-minval_)*(px + 2); + y = minval_ + (maxval_-minval_)*(py + 2); + new_dgm[0].push_back(std::make_pair(h, std::make_pair(x,y))); + } + if ((px >= 1) & (py >= 1)){ + x = minval_ - (maxval_-minval_)*(px - 2); + y = minval_ - (maxval_-minval_)*(py - 2); + new_dgm[1].push_back(std::make_pair(h, std::make_pair(x,y))); + } + if ((px <= -1) & (py >= 1)){ + x = minval_ + (maxval_-minval_)*(px + 2); + y = minval_ - (maxval_-minval_)*(py - 2); + if (x <= y){ + new_dgm[2].push_back(std::make_pair(h, std::make_pair(x,y))); + } + else{ + new_dgm[3].push_back(std::make_pair(h, std::make_pair(x,y))); + } } } } return new_dgm; } - /** \brief Extend filtration for computing extended persistence. This function only uses the filtration values at the 0-dimensional simplices, and computes the extended persistence diagram induced by the lower-star filtration computed with these values. Note that after calling this function, the filtration values are actually modified. The function compute_extended_persistence_subdiagrams retrieves the original values and separates the extended persistence diagram points w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after computing the persistent homology of the extended simplicial complex. + /** \brief Extend filtration for computing extended persistence. + * This function only uses the filtration values at the 0-dimensional simplices, + * and computes the extended persistence diagram induced by the lower-star filtration + * computed with these values. Note that after calling this function, the filtration + * values are actually modified. The function compute_extended_persistence_subdiagrams + * retrieves the original values and separates the extended persistence diagram points + * w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after + * computing the persistent homology of the extended simplicial complex. */ void extend_filtration() { // Compute maximum and minimum of filtration values - int maxvert = -std::numeric_limits::infinity(); + int maxvert = -std::numeric_limits::infinity(); std::vector filt; - for (auto sh : this->complex_simplex_range()) {if (this->dimension(sh) == 0){filt.push_back(this->filtration(sh)); maxvert = std::max(*this->simplex_vertex_range(sh).begin(), maxvert);}} + for (auto sh : this->complex_simplex_range()) { + if (this->dimension(sh) == 0){ + filt.push_back(this->filtration(sh)); + maxvert = std::max(*this->simplex_vertex_range(sh).begin(), maxvert); + } + } minval_ = *std::min_element(filt.begin(), filt.end()); maxval_ = *std::max_element(filt.begin(), filt.end()); maxvert += 1; @@ -1502,13 +1536,20 @@ class Simplex_tree { // Compute vectors of integers corresponding to the Simplex handles std::vector > splxs; for (auto sh : this->complex_simplex_range()) { - std::vector vr; for (auto vh : this->simplex_vertex_range(sh)){vr.push_back(vh);} + std::vector vr; + for (auto vh : this->simplex_vertex_range(sh)){ + vr.push_back(vh); + } splxs.push_back(vr); } // Add point for coning the simplicial complex int count = this->num_simplices(); - std::vector cone; cone.push_back(maxvert); auto ins = this->insert_simplex(cone, -3); this->assign_key(ins.first, count); count++; + std::vector cone; + cone.push_back(maxvert); + auto ins = this->insert_simplex(cone, -3); + this->assign_key(ins.first, count); + count++; // For each simplex for (auto vr : splxs){ @@ -1531,7 +1572,8 @@ class Simplex_tree { count++; } - this->make_filtration_non_decreasing(); this->initialize_filtration(); + this->make_filtration_non_decreasing(); + this->initialize_filtration(); } diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 4393047f..7aa16926 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -44,7 +44,7 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": bool prune_above_filtration(double filtration) bool make_filtration_non_decreasing() void extend_filtration() - vector[vector[pair[int, pair[double, double]]]] convert(vector[pair[int, pair[double, double]]]) + vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]]) cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": cdef cppclass Simplex_tree_persistence_interface "Gudhi::Persistent_cohomology_interface>": diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index cfab14f4..e429e28a 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -387,17 +387,21 @@ cdef class SimplexTree: return self.get_ptr().make_filtration_non_decreasing() def extend_filtration(self): - """ This function extends filtration for computing extended persistence. + """ Extend filtration for computing extended persistence. This function only uses the filtration values at the 0-dimensional simplices, and computes the extended persistence diagram induced by the lower-star filtration computed with these values. Note that after calling this function, the filtration values are actually modified. The function :func:`compute_extended_persistence_subdiagrams()` retrieves the original values and separates the extended persistence diagram points w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after computing the persistent homology of the extended simplicial complex. """ return self.get_ptr().extend_filtration() - def convert(self, dgm): - """This function retrieves good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. Need extend_filtration to be called first! + def compute_extended_persistence_subdiagrams(self, dgm): + """This function retrieves good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. - :param dgm: Persistence diagram obtained after calling this->extend_filtration and this->get_persistence. + :param dgm: Persistence diagram obtained after calling :func:`extend_filtration()` and :func:`persistence()`. :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. + + .. note:: + + This function should be called only after calling :func:`extend_filtration()` and :func:`persistence()`. """ - return self.get_ptr().convert(dgm) + return self.get_ptr().compute_extended_persistence_subdiagrams(dgm) def persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index 1822c43b..7e3d843e 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -244,7 +244,85 @@ def test_make_filtration_non_decreasing(): assert st.filtration([0, 1, 6]) == 1.0 assert st.filtration([0, 1]) == 1.0 assert st.filtration([0]) == 1.0 - assert st.filtration([1]) == 1.0 - assert st.filtration([3, 4, 5]) == 2.0 - assert st.filtration([3, 4]) == 2.0 - assert st.filtration([4, 5]) == 2.0 + +def test_extend_filtration(): + + # Inserted simplex: + # 5 4 + # o o + # / \ / + # o o + # /2\ /3 + # o o + # 1 0 + + st = SimplexTree() + st.insert([0,2]) + st.insert([1,2]) + st.insert([0,3]) + st.insert([2,5]) + st.insert([3,4]) + st.insert([3,5]) + st.assign_filtration([0], 1.) + st.assign_filtration([1], 2.) + st.assign_filtration([2], 3.) + st.assign_filtration([3], 4.) + st.assign_filtration([4], 5.) + st.assign_filtration([5], 6.) + + assert st.get_filtration() == [ + ([0, 2], 0.0), + ([1, 2], 0.0), + ([0, 3], 0.0), + ([3, 4], 0.0), + ([2, 5], 0.0), + ([3, 5], 0.0), + ([0], 1.0), + ([1], 2.0), + ([2], 3.0), + ([3], 4.0), + ([4], 5.0), + ([5], 6.0) + ] + + + st.extend_filtration() + + assert st.get_filtration() == [ + ([6], -3.0), + ([0], -2.0), + ([1], -1.8), + ([2], -1.6), + ([0, 2], -1.6), + ([1, 2], -1.6), + ([3], -1.4), + ([0, 3], -1.4), + ([4], -1.2), + ([3, 4], -1.2), + ([5], -1.0), + ([2, 5], -1.0), + ([3, 5], -1.0), + ([5, 6], 1.0), + ([4, 6], 1.2), + ([3, 6], 1.4), + ([3, 4, 6], 1.4), + ([3, 5, 6], 1.4), + ([2, 6], 1.6), + ([2, 5, 6], 1.6), + ([1, 6], 1.8), + ([1, 2, 6], 1.8), + ([0, 6], 2.0), + ([0, 2, 6], 2.0), + ([0, 3, 6], 2.0) + ] + + + dgm = st.persistence() + L = st.compute_extended_persistence_subdiagrams(dgm) + assert L == [ + [(0, (1.9999999999999998, 2.9999999999999996))], + [(1, (5.0, 4.0))], + [(0, (1.0, 6.0))], + [(1, (6.0, 1.0))] + ] + -- cgit v1.2.3 From dc4442bc402ac25290eb529b57407607434bb7ae Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 14 Feb 2020 14:53:51 +0100 Subject: barycenter update, adding more tests and details about log (assigments, cost, nb iter) --- src/python/gudhi/barycenter.py | 125 +++++++++++-------------- src/python/test/test_wasserstein_barycenter.py | 15 ++- 2 files changed, 69 insertions(+), 71 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 11098afe..4a00c457 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -2,6 +2,7 @@ import ot import numpy as np import scipy.spatial.distance as sc +from wasserstein import _build_dist_matrix, _perstot # This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. # See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. @@ -20,42 +21,19 @@ def _proj_on_diag(w): return np.array([(w[0] + w[1])/2 , (w[0] + w[1])/2]) -def _proj_on_diag_array(X): - ''' - :param X: (n x 2) array encoding the points of a persistent diagram. - :returns: (n x 2) array encoding the (respective orthogonal) projections of the points onto the diagonal - ''' - Z = (X[:,0] + X[:,1]) / 2. - return np.array([Z , Z]).T - - -def _build_dist_matrix(X, Y, p=2., q=2.): - ''' - :param X: (n x 2) numpy.array encoding the (points of the) first diagram. - :param Y: (m x 2) numpy.array encoding the second diagram. - :param q: Ground metric (i.e. norm l_q). - :param p: exponent for the Wasserstein metric. - :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. - note also that C[n+1, m+1] = 0 (it costs nothing to move from the diagonal to the diagonal). - Note that for lagrangian_barycenter, one must use p=q=2. - ''' - Xdiag = _proj_on_diag_array(X) - Ydiag = _proj_on_diag_array(Y) - if np.isinf(q): - C = sc.cdist(X, Y, metric='chebyshev')**p - Cxd = np.linalg.norm(X - Xdiag, ord=q, axis=1)**p - Cdy = np.linalg.norm(Y - Ydiag, ord=q, axis=1)**p +def _mean(x, m): + """ + :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} + :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal + :returns: the weighted mean of x with (m-k) copies of the diagonal + """ + k = len(x) + if k > 0: + w = np.mean(x, axis=0) + w_delta = _proj_on_diag(w) + return (k * w + (m-k) * w_delta) / m else: - C = sc.cdist(X,Y, metric='minkowski', p=q)**p - Cxd = np.linalg.norm(X - Xdiag, ord=q, axis=1)**p - Cdy = np.linalg.norm(Y - Ydiag, ord=q, axis=1)**p - Cf = np.hstack((C, Cxd[:,None])) - Cdy = np.append(Cdy, 0) - - Cf = np.vstack((Cf, Cdy[None,:])) - - return Cf + return np.array([0, 0]) def _optimal_matching(X, Y, withcost=False): @@ -64,63 +42,63 @@ def _optimal_matching(X, Y, withcost=False): :param Y: numpy.array of size (m x 2) :param withcost: returns also the cost corresponding to this optimal matching :returns: numpy.array of shape (k x 2) encoding the list of edges in the optimal matching. - That is, [(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] - if i > len(X) or j > len(Y), it means they represent the diagonal. - + That is, [[i, j] ...], where (i,j) indicates that X[i] is matched to Y[j] + if i >= len(X) or j >= len(Y), it means they represent the diagonal. + They will be encoded by -1 afterwards. """ n = len(X) m = len(Y) + # Start by handling empty diagrams. Could it be shorten? if X.size == 0: # X is empty if Y.size == 0: # Y is empty - return np.array([[0,0]]) # the diagonal is matched to the diagonal and that's it... - else: - return np.column_stack([np.zeros(m+1, dtype=int), np.arange(m+1, dtype=int)]) + res = np.array([[0,0]]) # the diagonal is matched to the diagonal and that's it... + if withcost: + return res, 0 + else: + return res + else: # X is empty but not Y + res = np.array([[0, i] for i in range(m)]) + cost = _perstot(Y, order=2, internal_p=2)**2 + if withcost: + return res, cost + else: + return res elif Y.size == 0: # X is not empty but Y is empty - return np.column_stack([np.zeros(n+1, dtype=int), np.arange(n+1, dtype=int)]) - + res = np.array([[i,0] for i in range(n)]) + cost = _perstot(X, order=2, internal_p=2)**2 + if withcost: + return res, cost + else: + return res + # we know X, Y are not empty diags now - M = _build_dist_matrix(X, Y) + M = _build_dist_matrix(X, Y, order=2, internal_p=2) 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 P = ot.emd(a=a, b=b, M=M)*(n+m) - # Note : it seems POT return a permutation matrix in this situation, ie a vertex of the constraint set (generically true). + # Note : it seems POT returns a permutation matrix in this situation, ie a vertex of the constraint set (generically true). if withcost: - cost = np.sqrt(np.sum(np.multiply(P, M))) + cost = np.sum(np.multiply(P, M)) P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to be improved. - # return the list of (i,j) such that P[i,j] > 0, i.e. x_i is matched to y_j (should it be the diag). res = np.nonzero(P) + # return the list of (i,j) such that P[i,j] > 0, i.e. x_i is matched to y_j (should it be the diag). if withcost: return np.column_stack(res), cost return np.column_stack(res) -def _mean(x, m): - """ - :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} - :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal - :returns: the weighted mean of x with (m-k) copies of the diagonal - """ - k = len(x) - if k > 0: - w = np.mean(x, axis=0) - w_delta = _proj_on_diag(w) - return (k * w + (m-k) * w_delta) / m - else: - return np.array([0, 0]) - - def lagrangian_barycenter(pdiagset, init=None, verbose=False): """ Compute the estimated barycenter computed with the algorithm provided by Turner et al (2014). It is a local minimum of the corresponding Frechet function. - :param pdiagset: a list of size N containing numpy.array of shape (n x 2) + :param pdiagset: a list of size m containing numpy.array of shape (n x 2) (n can variate), encoding a set of persistence diagrams with only finite coordinates. :param init: The initial value for barycenter estimate. @@ -134,10 +112,13 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): If verbose, returns a couple (Y, log) where Y is the barycenter estimate, and log is a dict that contains additional informations: - - assigments, a list of list of pairs (i,j), - That is, a[k] = [(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] + - groupings, a list of list of pairs (i,j), + That is, G[k] = [(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] if i > len(X) or j > len(Y), it means they represent the diagonal. - - energy, a float representing the Frechet mean value obtained. + - energy, a float representing the Frechet energy value obtained, + that is the mean of squared distances of observations to the output. + - nb_iter, integer representing the number of iterations performed before convergence + of the algorithm. """ X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging @@ -157,8 +138,11 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): else: Y = init.copy() + nb_iter = 0 + converged = False # stoping criterion while not converged: + nb_iter += 1 K = len(Y) # current nb of points in Y (some might be on diagonal) G = np.zeros((K, m), dtype=int)-1 # will store for each j, the (index) point matched in each other diagram (might be the diagonal). # that is G[j, i] = k <=> y_j is matched to @@ -185,7 +169,6 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): new_created_points.append(new_y) # Step 2 : Update current point position thanks to the groupings computed - to_delete = [] for j in range(K): matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] @@ -214,12 +197,16 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): n_y = len(Y) for i in range(m): edges, cost = _optimal_matching(Y, X[i], withcost=True) - print(edges) - groupings.append([x_i_j for (y_j, x_i_j) in enumerate(edges) if y_j < n_y]) + n_x = len(X[i]) + G = edges[np.where(edges[:,0]= n_x) + G[idx,1] = -1 # -1 will encode the diagonal + groupings.append(G) energy += cost log["groupings"] = groupings energy = energy/m log["energy"] = energy + log["nb_iter"] = nb_iter return Y, log else: diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index 910d23ff..07242582 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -27,7 +27,18 @@ def test_lagrangian_barycenter(): res = np.array([[0.27916667, 0.55416667], [0.7375, 0.7625], [0.2375, 0.2625]]) dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) + dg8 = np.array([[0., 4.]]) + + # error crit. + eps = 0.000001 - assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < 0.001 + + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < eps assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.empty(shape=(0,2))) - assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < 0.001 + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < eps + Y, log = lagrangian_barycenter(pdiagset=[dg4, dg8], verbose=True) + assert np.linalg.norm(Y - np.array([[1,3]])) < eps + assert np.abs(log["energy"] - 2) < eps + assert np.array_equal(log["groupings"][0] , np.array([[0, -1]])) + assert np.array_equal(log["groupings"][1] , np.array([[0, 0]])) + assert lagrangian_barycenter(pdiagset = []) is None -- cgit v1.2.3 From dc5c7ac2167bfa467b52d0a36ecb9999fe03ba91 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 14 Feb 2020 14:58:53 +0100 Subject: added two more tests for barycenter --- src/python/test/test_wasserstein_barycenter.py | 1 + 1 file changed, 1 insertion(+) (limited to 'src/python') diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index 07242582..a58a4d62 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -41,4 +41,5 @@ def test_lagrangian_barycenter(): assert np.abs(log["energy"] - 2) < eps assert np.array_equal(log["groupings"][0] , np.array([[0, -1]])) assert np.array_equal(log["groupings"][1] , np.array([[0, 0]])) + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg8, dg4], init=np.array([[0.2, 0.6], [0.5, 0.7]]), verbose=False) - np.array([[1, 3]])) < eps assert lagrangian_barycenter(pdiagset = []) is None -- cgit v1.2.3 From 3eaba12b66518717e90ffb1e410b7f8d769719cf Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 14 Feb 2020 15:41:23 +0100 Subject: update import gudhi.wasserstein --- src/python/gudhi/barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 4a00c457..a2af7a58 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -2,7 +2,7 @@ import ot import numpy as np import scipy.spatial.distance as sc -from wasserstein import _build_dist_matrix, _perstot +from gudhi.wasserstein import _build_dist_matrix, _perstot # This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. # See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. -- cgit v1.2.3 From f8fe3fdb01f6161b57da732a1c3f0c14a8b359a6 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 14 Feb 2020 18:45:34 +0100 Subject: moved import after docstring + reduce lines < 80 char --- src/python/gudhi/barycenter.py | 99 +++++++++++++++++++++++++----------------- 1 file changed, 59 insertions(+), 40 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index a2af7a58..4a877b4a 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -1,9 +1,3 @@ -import ot -import numpy as np -import scipy.spatial.distance as sc - -from gudhi.wasserstein import _build_dist_matrix, _perstot - # This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. # See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. # Author(s): Theo Lacombe @@ -14,6 +8,13 @@ from gudhi.wasserstein import _build_dist_matrix, _perstot # - YYYY/MM Author: Description of the modification +import ot +import numpy as np +import scipy.spatial.distance as sc + +from gudhi.wasserstein import _build_dist_matrix, _perstot + + def _proj_on_diag(w): ''' Util function to project a point on the diag. @@ -24,7 +25,8 @@ def _proj_on_diag(w): def _mean(x, m): """ :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} - :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal + :param m: total amount of points taken into account, + that is we have (m-k) copies of diagonal :returns: the weighted mean of x with (m-k) copies of the diagonal """ k = len(x) @@ -40,11 +42,14 @@ def _optimal_matching(X, Y, withcost=False): """ :param X: numpy.array of size (n x 2) :param Y: numpy.array of size (m x 2) - :param withcost: returns also the cost corresponding to this optimal matching - :returns: numpy.array of shape (k x 2) encoding the list of edges in the optimal matching. - That is, [[i, j] ...], where (i,j) indicates that X[i] is matched to Y[j] - if i >= len(X) or j >= len(Y), it means they represent the diagonal. - They will be encoded by -1 afterwards. + :param withcost: returns also the cost corresponding to the optimal matching + :returns: numpy.array of shape (k x 2) encoding the list of edges + in the optimal matching. + That is, [[i, j] ...], where (i,j) indicates + that X[i] is matched to Y[j] + if i >= len(X) or j >= len(Y), it means they + represent the diagonal. + They will be encoded by -1 afterwards. """ n = len(X) @@ -52,7 +57,7 @@ def _optimal_matching(X, Y, withcost=False): # Start by handling empty diagrams. Could it be shorten? if X.size == 0: # X is empty if Y.size == 0: # Y is empty - res = np.array([[0,0]]) # the diagonal is matched to the diagonal and that's it... + res = np.array([[0,0]]) # the diagonal is matched to the diagonal if withcost: return res, 0 else: @@ -75,18 +80,20 @@ def _optimal_matching(X, Y, withcost=False): # we know X, Y are not empty diags now M = _build_dist_matrix(X, Y, order=2, internal_p=2) - 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.full(n+1, 1. / (n + m) ) + a[-1] = a[-1] * m + b = np.full(m+1, 1. / (n + m) ) + b[-1] = b[-1] * n P = ot.emd(a=a, b=b, M=M)*(n+m) - # Note : it seems POT returns a permutation matrix in this situation, ie a vertex of the constraint set (generically true). + # Note : it seems POT returns a permutation matrix in this situation, + # ie a vertex of the constraint set (generically true). if withcost: cost = np.sum(np.multiply(P, M)) - P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to be improved. + P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to improve. res = np.nonzero(P) - # return the list of (i,j) such that P[i,j] > 0, i.e. x_i is matched to y_j (should it be the diag). + # return the list of (i,j) such that P[i,j] > 0, + #i.e. x_i is matched to y_j (should it be the diag). if withcost: return np.column_stack(res), cost @@ -103,31 +110,38 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): persistence diagrams with only finite coordinates. :param init: The initial value for barycenter estimate. If None, init is made on a random diagram from the dataset. - Otherwise, it must be an int (then we init with diagset[init]) - or a (n x 2) numpy.array enconding a persistence diagram with n points. + Otherwise, it must be an int + (then we init with diagset[init]) + or a (n x 2) numpy.array enconding + a persistence diagram with n points. :param verbose: if True, returns additional information about the barycenter. :returns: If not verbose (default), a numpy.array encoding - the barycenter estimate (local minima of the energy function). + the barycenter estimate + (local minima of the energy function). If verbose, returns a couple (Y, log) where Y is the barycenter estimate, and log is a dict that contains additional informations: - groupings, a list of list of pairs (i,j), - That is, G[k] = [(i, j) ...], where (i,j) indicates that X[i] is matched to Y[j] - if i > len(X) or j > len(Y), it means they represent the diagonal. - - energy, a float representing the Frechet energy value obtained, - that is the mean of squared distances of observations to the output. - - nb_iter, integer representing the number of iterations performed before convergence - of the algorithm. + That is, G[k] = [(i, j) ...], where (i,j) indicates + that X[i] is matched to Y[j] + if i > len(X) or j > len(Y), it means they + represent the diagonal. + - energy, a float representing the Frechet + energy value obtained, + that is the mean of squared distances + of observations to the output. + - nb_iter, integer representing the number of iterations + performed before convergence of the algorithm. """ X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging if m == 0: print("Warning: computing barycenter of empty diag set. Returns None") return None - - nb_off_diag = np.array([len(X_i) for X_i in X]) # store the number of off-diagonal point for each of the X_i - + + # store the number of off-diagonal point for each of the X_i + nb_off_diag = np.array([len(X_i) for X_i in X]) # Initialisation of barycenter if init is None: i0 = np.random.randint(m) # Index of first state for the barycenter @@ -144,7 +158,9 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): while not converged: nb_iter += 1 K = len(Y) # current nb of points in Y (some might be on diagonal) - G = np.zeros((K, m), dtype=int)-1 # will store for each j, the (index) point matched in each other diagram (might be the diagonal). + G = np.zeros((K, m), dtype=int)-1 # will store for each j, the (index) + # point matched in each other diagram + #(might be the diagonal). # that is G[j, i] = k <=> y_j is matched to # x_k in the diagram i-th diagram X[i] updated_points = np.zeros((K, 2)) # will store the new positions of @@ -159,16 +175,19 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): indices = _optimal_matching(Y, X[i]) for y_j, x_i_j in indices: if y_j < K: # we matched an off diagonal point to x_i_j... - if x_i_j < nb_off_diag[i]: # ...which is also an off-diagonal point + # ...which is also an off-diagonal point. + if x_i_j < nb_off_diag[i]: G[y_j, i] = x_i_j else: # ...which is a diagonal point G[y_j, i] = -1 # -1 stands for the diagonal (mask) else: # We matched a diagonal point to x_i_j... - if x_i_j < nb_off_diag[i]: # which is a off-diag point ! so we need to create a new point in Y - new_y = _mean(np.array([X[i][x_i_j]]), m) # Average this point with (m-1) copies of Delta + if x_i_j < nb_off_diag[i]: # which is a off-diag point ! + # need to create new point in Y + new_y = _mean(np.array([X[i][x_i_j]]), m) + # Average this point with (m-1) copies of Delta new_created_points.append(new_y) - # Step 2 : Update current point position thanks to the groupings computed + # Step 2 : Update current point position thanks to groupings computed to_delete = [] for j in range(K): matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] @@ -178,10 +197,10 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): else: # this points is no longer of any use. to_delete.append(j) # we remove the point to be deleted now. - updated_points = np.delete(updated_points, to_delete, axis=0) # cannot be done in-place. - + updated_points = np.delete(updated_points, to_delete, axis=0) - if new_created_points: # we cannot converge if there have been new created points. + # we cannot converge if there have been new created points. + if new_created_points: Y = np.concatenate((updated_points, new_created_points)) else: # Step 3 : we check convergence -- cgit v1.2.3 From 5e4bc93510f50dacdb59f1a7578aca72817c9631 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 17 Feb 2020 17:50:37 +0100 Subject: update doc + removed normalization + use argwhere --- src/python/doc/barycenter_user.rst | 7 ++++++- src/python/gudhi/barycenter.py | 29 ++++++++++++----------------- 2 files changed, 18 insertions(+), 18 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst index 714d807e..f81e9358 100644 --- a/src/python/doc/barycenter_user.rst +++ b/src/python/doc/barycenter_user.rst @@ -9,7 +9,8 @@ Definition .. include:: barycenter_sum.inc -This implementation is based on ideas from "Frechet means for distribution of persistence diagrams", Turner et al. 2014. +This implementation is based on ideas from "Frechet means for distribution of +persistence diagrams", Turner et al. 2014. Function -------- @@ -21,6 +22,10 @@ Basic example This example computes the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. It is initialized on the 4th diagram, which is the empty diagram. It is encoded by np.array([]). +As the algorithm is not convex, its output depends on the initialization and is only a local minimum of the objective function. +Initialization can be either given as an integer (in which case the i-th diagram of the list is used as initial estimate) +or as a diagram. +If None, it will randomly select one of the diagram of the list as initial estimate. Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. .. testcode:: diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 4a877b4a..c54066ec 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -15,12 +15,6 @@ import scipy.spatial.distance as sc from gudhi.wasserstein import _build_dist_matrix, _perstot -def _proj_on_diag(w): - ''' - Util function to project a point on the diag. - ''' - return np.array([(w[0] + w[1])/2 , (w[0] + w[1])/2]) - def _mean(x, m): """ @@ -32,7 +26,7 @@ def _mean(x, m): k = len(x) if k > 0: w = np.mean(x, axis=0) - w_delta = _proj_on_diag(w) + w_delta = (w[0] + w[1]) / 2 * np.ones(2) return (k * w + (m-k) * w_delta) / m else: return np.array([0, 0]) @@ -80,31 +74,32 @@ def _optimal_matching(X, Y, withcost=False): # we know X, Y are not empty diags now M = _build_dist_matrix(X, Y, order=2, internal_p=2) - a = np.full(n+1, 1. / (n + m) ) - a[-1] = a[-1] * m - b = np.full(m+1, 1. / (n + m) ) - b[-1] = b[-1] * n - P = ot.emd(a=a, b=b, M=M)*(n+m) + a = np.ones(n+1) + a[-1] = m + b = np.ones(m+1) + b[-1] = n + P = ot.emd(a=a, b=b, M=M) # Note : it seems POT returns a permutation matrix in this situation, # ie a vertex of the constraint set (generically true). if withcost: cost = np.sum(np.multiply(P, M)) P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to improve. - res = np.nonzero(P) + res = np.argwhere(P) # return the list of (i,j) such that P[i,j] > 0, #i.e. x_i is matched to y_j (should it be the diag). if withcost: - return np.column_stack(res), cost - - return np.column_stack(res) + return res, cost + return res def lagrangian_barycenter(pdiagset, init=None, verbose=False): """ - Compute the estimated barycenter computed with the algorithm provided + Returns the estimated barycenter computed with the algorithm provided by Turner et al (2014). + As the algorithm is not convex, the output depends on initialization. It is a local minimum of the corresponding Frechet function. + :param pdiagset: a list of size m containing numpy.array of shape (n x 2) (n can variate), encoding a set of persistence diagrams with only finite coordinates. -- cgit v1.2.3 From 16e80e921e1edbc63398f7dbc342bd25d1f169de Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 17 Feb 2020 17:53:39 +0100 Subject: removed message about empty dgm --- src/python/doc/barycenter_user.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst index f81e9358..59f758fa 100644 --- a/src/python/doc/barycenter_user.rst +++ b/src/python/doc/barycenter_user.rst @@ -21,7 +21,7 @@ Basic example ------------- This example computes the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. -It is initialized on the 4th diagram, which is the empty diagram. It is encoded by np.array([]). +It is initialized on the 4th diagram. As the algorithm is not convex, its output depends on the initialization and is only a local minimum of the objective function. Initialization can be either given as an integer (in which case the i-th diagram of the list is used as initial estimate) or as a diagram. -- cgit v1.2.3 From a9b0d8185ecab51428c1aeeb3bf78787420103b2 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 17 Feb 2020 17:54:01 +0100 Subject: specified that the alg returns None if input is empty --- src/python/gudhi/barycenter.py | 1 + 1 file changed, 1 insertion(+) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index c54066ec..dc9e8241 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -103,6 +103,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): :param pdiagset: a list of size m containing numpy.array of shape (n x 2) (n can variate), encoding a set of persistence diagrams with only finite coordinates. + If empty, returns None. :param init: The initial value for barycenter estimate. If None, init is made on a random diagram from the dataset. Otherwise, it must be an int -- cgit v1.2.3 From 59f046cd0f405b124a6e08f26ca7b0248f707374 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 24 Feb 2020 10:14:09 +0100 Subject: update doc for barycenter --- src/python/doc/index.rst | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/python') diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst index 3387a64f..96cd3513 100644 --- a/src/python/doc/index.rst +++ b/src/python/doc/index.rst @@ -71,6 +71,11 @@ Wasserstein distance .. include:: wasserstein_distance_sum.inc +Barycenter +============ + +.. include:: barycenter_sum.inc + Persistence representations =========================== -- cgit v1.2.3 From 3e15e9fe5bffb0ffcf8f7f3a0dac1c331646630a Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 24 Feb 2020 10:14:31 +0100 Subject: changed double quote into simple quote to be consistent with wasserstein.py --- src/python/gudhi/barycenter.py | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index dc9e8241..4e132c23 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -17,12 +17,12 @@ from gudhi.wasserstein import _build_dist_matrix, _perstot def _mean(x, m): - """ + ''' :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal :returns: the weighted mean of x with (m-k) copies of the diagonal - """ + ''' k = len(x) if k > 0: w = np.mean(x, axis=0) @@ -33,7 +33,7 @@ def _mean(x, m): def _optimal_matching(X, Y, withcost=False): - """ + ''' :param X: numpy.array of size (n x 2) :param Y: numpy.array of size (m x 2) :param withcost: returns also the cost corresponding to the optimal matching @@ -44,7 +44,7 @@ def _optimal_matching(X, Y, withcost=False): if i >= len(X) or j >= len(Y), it means they represent the diagonal. They will be encoded by -1 afterwards. - """ + ''' n = len(X) m = len(Y) @@ -94,7 +94,7 @@ def _optimal_matching(X, Y, withcost=False): def lagrangian_barycenter(pdiagset, init=None, verbose=False): - """ + ''' Returns the estimated barycenter computed with the algorithm provided by Turner et al (2014). As the algorithm is not convex, the output depends on initialization. @@ -129,7 +129,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): of observations to the output. - nb_iter, integer representing the number of iterations performed before convergence of the algorithm. - """ + ''' X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging if m == 0: -- cgit v1.2.3 From 2dc7b150576d959b489d3f52890242fd6a492171 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 24 Feb 2020 13:18:38 +0100 Subject: changed doc for CI ? --- src/python/gudhi/barycenter.py | 5 ----- 1 file changed, 5 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 4e132c23..a41b5906 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -95,11 +95,6 @@ def _optimal_matching(X, Y, withcost=False): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' - Returns the estimated barycenter computed with the algorithm provided - by Turner et al (2014). - As the algorithm is not convex, the output depends on initialization. - It is a local minimum of the corresponding Frechet function. - :param pdiagset: a list of size m containing numpy.array of shape (n x 2) (n can variate), encoding a set of persistence diagrams with only finite coordinates. -- cgit v1.2.3 From 0998cecac7f15e3c68058d33acc21fb427f803e9 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 28 Feb 2020 11:18:59 +0100 Subject: shorten < 80 char the doc --- src/python/doc/barycenter_user.rst | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst index 59f758fa..83e9bebb 100644 --- a/src/python/doc/barycenter_user.rst +++ b/src/python/doc/barycenter_user.rst @@ -20,13 +20,17 @@ Function Basic example ------------- -This example computes the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. +This example computes the Frechet mean (aka Wasserstein barycenter) between +four persistence diagrams. It is initialized on the 4th diagram. -As the algorithm is not convex, its output depends on the initialization and is only a local minimum of the objective function. -Initialization can be either given as an integer (in which case the i-th diagram of the list is used as initial estimate) -or as a diagram. -If None, it will randomly select one of the diagram of the list as initial estimate. -Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. +As the algorithm is not convex, its output depends on the initialization and +is only a local minimum of the objective function. +Initialization can be either given as an integer (in which case the i-th +diagram of the list is used as initial estimate) or as a diagram. +If None, it will randomly select one of the diagram of the list +as initial estimate. +Note that persistence diagrams must be submitted as +(n x 2) numpy arrays and must not contain inf values. .. testcode:: @@ -37,8 +41,8 @@ Note that persistence diagrams must be submitted as (n x 2) numpy arrays and mus dg2 = np.array([[0.2, 0.7]]) dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) dg4 = np.array([]) - - bary = gudhi.barycenter.lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3) + pdiagset = [dg1, dg2, dg3, dg4] + bary = gudhi.barycenter.lagrangian_barycenter(pdiagset=pdiagset,init=3) message = "Wasserstein barycenter estimated:" print(message) -- cgit v1.2.3 From 4b546a43fe14178dcfb2b327e27a580fc9811499 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Mar 2020 13:16:04 +0100 Subject: update doc (indentation, mention of -1 for the diag) and added a few more tests --- src/python/gudhi/barycenter.py | 30 +++++++++++++------------- src/python/test/test_wasserstein_barycenter.py | 15 +++++++------ 2 files changed, 23 insertions(+), 22 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index a41b5906..3af12c14 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -96,9 +96,8 @@ def _optimal_matching(X, Y, withcost=False): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' :param pdiagset: a list of size m containing numpy.array of shape (n x 2) - (n can variate), encoding a set of - persistence diagrams with only finite coordinates. - If empty, returns None. + (n can variate), encoding a set of + persistence diagrams with only finite coordinates. :param init: The initial value for barycenter estimate. If None, init is made on a random diagram from the dataset. Otherwise, it must be an int @@ -106,24 +105,25 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): or a (n x 2) numpy.array enconding a persistence diagram with n points. :param verbose: if True, returns additional information about the - barycenter. + barycenter. :returns: If not verbose (default), a numpy.array encoding - the barycenter estimate + the barycenter estimate of pdiagset (local minima of the energy function). + If pdiagset is empty, returns None. If verbose, returns a couple (Y, log) where Y is the barycenter estimate, and log is a dict that contains additional informations: - groupings, a list of list of pairs (i,j), - That is, G[k] = [(i, j) ...], where (i,j) indicates - that X[i] is matched to Y[j] - if i > len(X) or j > len(Y), it means they - represent the diagonal. + That is, G[k] = [(i, j) ...], where (i,j) indicates + that X[i] is matched to Y[j] + if i = -1 or j = -1, it means they + represent the diagonal. - energy, a float representing the Frechet - energy value obtained, - that is the mean of squared distances - of observations to the output. + energy value obtained, + that is the mean of squared distances + of observations to the output. - nb_iter, integer representing the number of iterations - performed before convergence of the algorithm. + performed before convergence of the algorithm. ''' X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging @@ -136,7 +136,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): # Initialisation of barycenter if init is None: i0 = np.random.randint(m) # Index of first state for the barycenter - Y = X[i0].copy() #copy() ensure that we do not modify X[i0] + Y = X[i0].copy() else: if type(init)==int: Y = X[init].copy() @@ -149,7 +149,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): while not converged: nb_iter += 1 K = len(Y) # current nb of points in Y (some might be on diagonal) - G = np.zeros((K, m), dtype=int)-1 # will store for each j, the (index) + G = np.full((K, m), -1, dtype=int) # will store for each j, the (index) # point matched in each other diagram #(might be the diagonal). # that is G[j, i] = k <=> y_j is matched to diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index a58a4d62..5167cb84 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -27,19 +27,20 @@ def test_lagrangian_barycenter(): res = np.array([[0.27916667, 0.55416667], [0.7375, 0.7625], [0.2375, 0.2625]]) dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) - dg8 = np.array([[0., 4.]]) + dg8 = np.array([[0., 4.], [4, 8]]) # error crit. - eps = 0.000001 + eps = 1e-7 assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < eps assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.empty(shape=(0,2))) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < eps Y, log = lagrangian_barycenter(pdiagset=[dg4, dg8], verbose=True) - assert np.linalg.norm(Y - np.array([[1,3]])) < eps - assert np.abs(log["energy"] - 2) < eps - assert np.array_equal(log["groupings"][0] , np.array([[0, -1]])) - assert np.array_equal(log["groupings"][1] , np.array([[0, 0]])) - assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg8, dg4], init=np.array([[0.2, 0.6], [0.5, 0.7]]), verbose=False) - np.array([[1, 3]])) < eps + assert np.linalg.norm(Y - np.array([[1,3], [5, 7]])) < eps + assert np.abs(log["energy"] - 4) < eps + assert np.array_equal(log["groupings"][0] , np.array([[0, -1], [1, -1]])) + assert np.array_equal(log["groupings"][1] , np.array([[0, 0], [1, 1]])) + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg8, dg4], init=np.array([[0.2, 0.6], [0.5, 0.7]]), verbose=False) - np.array([[1, 3], [5, 7]])) < eps assert lagrangian_barycenter(pdiagset = []) is None + -- cgit v1.2.3 From aa93247860bb01e3fc15926658dd9e6a95198f3d Mon Sep 17 00:00:00 2001 From: tlacombe Date: Mon, 16 Mar 2020 13:18:58 +0100 Subject: added mention that _optimal matching should be removed at some point --- src/python/gudhi/barycenter.py | 3 +++ 1 file changed, 3 insertions(+) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 3af12c14..517cdb2f 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -44,6 +44,9 @@ def _optimal_matching(X, Y, withcost=False): if i >= len(X) or j >= len(Y), it means they represent the diagonal. They will be encoded by -1 afterwards. + + NOTE : this code will be removed for final merge, + and wasserstein.optimal_matching will be used instead. ''' n = len(X) -- cgit v1.2.3 From 6e289999fab86bf06cd69c5b7b846c4f26e0a525 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Tue, 17 Mar 2020 00:13:32 -0400 Subject: fixes --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 74 +++++++++++++++------------ src/python/test/test_simplex_tree.py | 12 ++--- 2 files changed, 47 insertions(+), 39 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 7be14bce..02f2c7e9 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1354,6 +1354,7 @@ class Simplex_tree { // Replacing if(f=max)) would mean that if f is NaN, we replace it with the max of the children. // That seems more useful than keeping NaN. if (!(simplex.second.filtration() >= max_filt_border_value)) { + // Store the filtration modification information modified = true; simplex.second.assign_filtration(max_filt_border_value); @@ -1473,15 +1474,21 @@ class Simplex_tree { /** \brief Retrieve good values for extended persistence, and separate the * diagrams into the ordinary, relative, extended+ and extended- subdiagrams. - * Need extend_filtration to be called first! + * \post This function should be called only if extend_filtration has been called first! + * \post The coordinates of the persistence diagram points might be a little different than the + * original filtration values due to the internal transformation (scaling to [-2,-1]) that is + * performed on these values during the computation of extended persistence. * @param[in] dgm Persistence diagram obtained after calling this->extend_filtration * and this->get_persistence. * @return A vector of four persistence diagrams. The first one is Ordinary, the * second one is Relative, the third one is Extended+ and the fourth one is Extended-. + * See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. */ std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm){ std::vector>>> new_dgm(4); double x, y; + double minval_ = this->minval_; + double maxval_ = this->maxval_; for(unsigned int i = 0; i < dgm.size(); i++){ int h = dgm[i].first; double px = dgm[i].second.first; @@ -1516,69 +1523,70 @@ class Simplex_tree { /** \brief Extend filtration for computing extended persistence. * This function only uses the filtration values at the 0-dimensional simplices, * and computes the extended persistence diagram induced by the lower-star filtration - * computed with these values. Note that after calling this function, the filtration + * computed with these values. + * \post Note that after calling this function, the filtration * values are actually modified. The function compute_extended_persistence_subdiagrams * retrieves the original values and separates the extended persistence diagram points * w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after * computing the persistent homology of the extended simplicial complex. + * \post Note that this code creates an extra vertex internally, so you should make sure that + * the Simplex tree does not contain a vertex with the largest Vertex_handle. */ void extend_filtration() { // Compute maximum and minimum of filtration values - int maxvert = -std::numeric_limits::infinity(); - std::vector filt; - for (auto sh : this->complex_simplex_range()) { - if (this->dimension(sh) == 0){ - filt.push_back(this->filtration(sh)); - maxvert = std::max(*this->simplex_vertex_range(sh).begin(), maxvert); - } + int maxvert = std::numeric_limits::min(); + this->minval_ = std::numeric_limits::max(); + this->maxval_ = std::numeric_limits::min(); + for (auto sh : this->skeleton_simplex_range(0)) { + double f = this->filtration(sh); + this->minval_ = std::min(this->minval_, f); + this->maxval_ = std::max(this->maxval_, f); + maxvert = std::max(*this->simplex_vertex_range(sh).begin(), maxvert); } - minval_ = *std::min_element(filt.begin(), filt.end()); - maxval_ = *std::max_element(filt.begin(), filt.end()); + + assert (maxvert < std::numeric_limits::max()); maxvert += 1; - // Compute vectors of integers corresponding to the Simplex handles - std::vector > splxs; - for (auto sh : this->complex_simplex_range()) { - std::vector vr; - for (auto vh : this->simplex_vertex_range(sh)){ - vr.push_back(vh); - } - splxs.push_back(vr); - } + Simplex_tree* st_copy = new Simplex_tree(*this); // Add point for coning the simplicial complex int count = this->num_simplices(); - std::vector cone; - cone.push_back(maxvert); - auto ins = this->insert_simplex(cone, -3); - this->assign_key(ins.first, count); + this->insert_simplex({maxvert}, -3); count++; // For each simplex - for (auto vr : splxs){ + for (auto sh_copy : st_copy->complex_simplex_range()){ + + // Locate simplex + std::vector vr; + for (auto vh : st_copy->simplex_vertex_range(sh_copy)){ + vr.push_back(vh); + } + auto sh = this->find(vr); + // Create cone on simplex - auto sh = this->find(vr); vr.push_back(maxvert); + vr.push_back(maxvert); if (this->dimension(sh) == 0){ // Assign ascending value between -2 and -1 to vertex double v = this->filtration(sh); - this->assign_filtration(sh, -2 + (v-minval_)/(maxval_-minval_)); + this->assign_filtration(sh, -2 + (v-this->minval_)/(this->maxval_-this->minval_)); // Assign descending value between 1 and 2 to cone on vertex - auto ins = this->insert_simplex(vr, 2 - (v-minval_)/(maxval_-minval_)); - this->assign_key(ins.first, count); + this->insert_simplex(vr, 2 - (v-this->minval_)/(this->maxval_-this->minval_)); } else{ // Assign value -3 to simplex and cone on simplex this->assign_filtration(sh, -3); - auto ins = this->insert_simplex(vr, -3); - this->assign_key(ins.first, count); + this->insert_simplex(vr, -3); } count++; } - this->make_filtration_non_decreasing(); - this->initialize_filtration(); + // Deallocate memory + delete st_copy; + // Automatically assign good values for simplices + this->make_filtration_non_decreasing(); } diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index caefeb9c..96ec4707 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -245,6 +245,10 @@ def test_make_filtration_non_decreasing(): assert st.filtration([0, 1, 6]) == 1.0 assert st.filtration([0, 1]) == 1.0 assert st.filtration([0]) == 1.0 + assert st.filtration([1]) == 1.0 + assert st.filtration([3, 4, 5]) == 2.0 + assert st.filtration([3, 4]) == 2.0 + assert st.filtration([4, 5]) == 2.0 def test_extend_filtration(): @@ -271,7 +275,7 @@ def test_extend_filtration(): st.assign_filtration([4], 5.) st.assign_filtration([5], 6.) - assert st.get_filtration() == [ + assert list(st.get_filtration()) == [ ([0, 2], 0.0), ([1, 2], 0.0), ([0, 3], 0.0), @@ -289,7 +293,7 @@ def test_extend_filtration(): st.extend_filtration() - assert st.get_filtration() == [ + assert list(st.get_filtration()) == [ ([6], -3.0), ([0], -2.0), ([1], -1.8), @@ -327,10 +331,6 @@ def test_extend_filtration(): [(1, (6.0, 1.0))] ] - assert st.filtration([1]) == 1.0 - assert st.filtration([3, 4, 5]) == 2.0 - assert st.filtration([3, 4]) == 2.0 - assert st.filtration([4, 5]) == 2.0 def test_simplices_iterator(): st = SimplexTree() -- cgit v1.2.3 From a52e84fdcdbf66f3542416499c26245d0435a8fb Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Tue, 17 Mar 2020 00:48:54 -0400 Subject: fix test --- src/python/test/test_simplex_tree.py | 1 + 1 file changed, 1 insertion(+) (limited to 'src/python') diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index 96ec4707..63eee9a5 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -292,6 +292,7 @@ def test_extend_filtration(): st.extend_filtration() + st.initialize_filtration() assert list(st.get_filtration()) == [ ([6], -3.0), -- cgit v1.2.3 From cdc57712ca159f3044453cef41e31ebc03617a1b Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 17 Mar 2020 10:55:14 +0100 Subject: removed _optimal_matching from barycenter as it is now handled by wasserstein_distance. --- src/python/gudhi/barycenter.py | 85 +++----------------------- src/python/test/test_wasserstein_barycenter.py | 2 +- 2 files changed, 9 insertions(+), 78 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 517cdb2f..0490fdd1 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -12,8 +12,7 @@ import ot import numpy as np import scipy.spatial.distance as sc -from gudhi.wasserstein import _build_dist_matrix, _perstot - +from gudhi.wasserstein import wasserstein_distance, _perstot def _mean(x, m): @@ -32,70 +31,6 @@ def _mean(x, m): return np.array([0, 0]) -def _optimal_matching(X, Y, withcost=False): - ''' - :param X: numpy.array of size (n x 2) - :param Y: numpy.array of size (m x 2) - :param withcost: returns also the cost corresponding to the optimal matching - :returns: numpy.array of shape (k x 2) encoding the list of edges - in the optimal matching. - That is, [[i, j] ...], where (i,j) indicates - that X[i] is matched to Y[j] - if i >= len(X) or j >= len(Y), it means they - represent the diagonal. - They will be encoded by -1 afterwards. - - NOTE : this code will be removed for final merge, - and wasserstein.optimal_matching will be used instead. - ''' - - n = len(X) - m = len(Y) - # Start by handling empty diagrams. Could it be shorten? - if X.size == 0: # X is empty - if Y.size == 0: # Y is empty - res = np.array([[0,0]]) # the diagonal is matched to the diagonal - if withcost: - return res, 0 - else: - return res - else: # X is empty but not Y - res = np.array([[0, i] for i in range(m)]) - cost = _perstot(Y, order=2, internal_p=2)**2 - if withcost: - return res, cost - else: - return res - elif Y.size == 0: # X is not empty but Y is empty - res = np.array([[i,0] for i in range(n)]) - cost = _perstot(X, order=2, internal_p=2)**2 - if withcost: - return res, cost - else: - return res - - # we know X, Y are not empty diags now - M = _build_dist_matrix(X, Y, order=2, internal_p=2) - - a = np.ones(n+1) - a[-1] = m - b = np.ones(m+1) - b[-1] = n - P = ot.emd(a=a, b=b, M=M) - # Note : it seems POT returns a permutation matrix in this situation, - # ie a vertex of the constraint set (generically true). - if withcost: - cost = np.sum(np.multiply(P, M)) - P[P < 0.5] = 0 # dirty trick to avoid some numerical issues... to improve. - res = np.argwhere(P) - - # return the list of (i,j) such that P[i,j] > 0, - #i.e. x_i is matched to y_j (should it be the diag). - if withcost: - return res, cost - return res - - def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' :param pdiagset: a list of size m containing numpy.array of shape (n x 2) @@ -166,16 +101,15 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): # Step 1 : compute optimal matching (Y, X_i) for each X_i # and create new points in Y if needed for i in range(m): - indices = _optimal_matching(Y, X[i]) + _, indices = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) for y_j, x_i_j in indices: - if y_j < K: # we matched an off diagonal point to x_i_j... - # ...which is also an off-diagonal point. - if x_i_j < nb_off_diag[i]: + if y_j >= 0: # we matched an off diagonal point to x_i_j... + if x_i_j >= 0: # ...which is also an off-diagonal point. G[y_j, i] = x_i_j else: # ...which is a diagonal point G[y_j, i] = -1 # -1 stands for the diagonal (mask) else: # We matched a diagonal point to x_i_j... - if x_i_j < nb_off_diag[i]: # which is a off-diag point ! + if x_i_j >= 0: # which is a off-diag point ! # need to create new point in Y new_y = _mean(np.array([X[i][x_i_j]]), m) # Average this point with (m-1) copies of Delta @@ -209,15 +143,12 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): log = {} n_y = len(Y) for i in range(m): - edges, cost = _optimal_matching(Y, X[i], withcost=True) - n_x = len(X[i]) - G = edges[np.where(edges[:,0]= n_x) - G[idx,1] = -1 # -1 will encode the diagonal - groupings.append(G) + cost, edges = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) + groupings.append(edges) energy += cost log["groupings"] = groupings energy = energy/m + print(energy) log["energy"] = energy log["nb_iter"] = nb_iter diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index 5167cb84..4d18616b 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -38,7 +38,7 @@ def test_lagrangian_barycenter(): assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < eps Y, log = lagrangian_barycenter(pdiagset=[dg4, dg8], verbose=True) assert np.linalg.norm(Y - np.array([[1,3], [5, 7]])) < eps - assert np.abs(log["energy"] - 4) < eps + assert np.abs(log["energy"] - 2) < eps assert np.array_equal(log["groupings"][0] , np.array([[0, -1], [1, -1]])) assert np.array_equal(log["groupings"][1] , np.array([[0, 0], [1, 1]])) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg8, dg4], init=np.array([[0.2, 0.6], [0.5, 0.7]]), verbose=False) - np.array([[1, 3], [5, 7]])) < eps -- cgit v1.2.3 From 58d923b13afb9b18a2d5b028c6575baee691d182 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Tue, 17 Mar 2020 12:14:49 -0400 Subject: update python doc --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 8 +++---- src/python/gudhi/simplex_tree.pyx | 34 +++++++++++++++++++++++---- 2 files changed, 33 insertions(+), 9 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 02f2c7e9..f661f687 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1478,8 +1478,8 @@ class Simplex_tree { * \post The coordinates of the persistence diagram points might be a little different than the * original filtration values due to the internal transformation (scaling to [-2,-1]) that is * performed on these values during the computation of extended persistence. - * @param[in] dgm Persistence diagram obtained after calling this->extend_filtration - * and this->get_persistence. + * @param[in] dgm Persistence diagram obtained after calling this->extend_filtration, + * this->initialize_filtration, and this->compute_persistent_cohomology. * @return A vector of four persistence diagrams. The first one is Ordinary, the * second one is Relative, the third one is Extended+ and the fourth one is Extended-. * See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. @@ -1538,14 +1538,14 @@ class Simplex_tree { int maxvert = std::numeric_limits::min(); this->minval_ = std::numeric_limits::max(); this->maxval_ = std::numeric_limits::min(); - for (auto sh : this->skeleton_simplex_range(0)) { + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh){ double f = this->filtration(sh); this->minval_ = std::min(this->minval_, f); this->maxval_ = std::max(this->maxval_, f); maxvert = std::max(*this->simplex_vertex_range(sh).begin(), maxvert); } - assert (maxvert < std::numeric_limits::max()); + GUDHI_CHECK(maxvert < std::numeric_limits::max(), std::invalid_argument("Simplex_tree contains a vertex with the largest Vertex_handle")); maxvert += 1; Simplex_tree* st_copy = new Simplex_tree(*this); diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 733ecb97..7af44683 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -397,19 +397,43 @@ cdef class SimplexTree: return self.get_ptr().make_filtration_non_decreasing() def extend_filtration(self): - """ Extend filtration for computing extended persistence. This function only uses the filtration values at the 0-dimensional simplices, and computes the extended persistence diagram induced by the lower-star filtration computed with these values. Note that after calling this function, the filtration values are actually modified. The function :func:`compute_extended_persistence_subdiagrams()` retrieves the original values and separates the extended persistence diagram points w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after computing the persistent homology of the extended simplicial complex. + """ Extend filtration for computing extended persistence. This function only uses the + filtration values at the 0-dimensional simplices, and computes the extended persistence + diagram induced by the lower-star filtration computed with these values. + + .. note:: + + Note that after calling this function, the filtration + values are actually modified within the Simplex_tree. + The function :func:`compute_extended_persistence_subdiagrams()` + retrieves the original values. + + .. note:: + + Note that this code creates an extra vertex internally, so you should make sure that + the Simplex_tree does not contain a vertex with the largest Vertex_handle. """ return self.get_ptr().extend_filtration() def compute_extended_persistence_subdiagrams(self, dgm): - """This function retrieves good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. + """This function retrieves good values for extended persistence, and separate the diagrams + into the ordinary, relative, extended+ and extended- subdiagrams. + + :param dgm: Persistence diagram obtained after calling :func:`extend_filtration()`, :func:`initialize_filtration()`, and :func:`persistence()`. + + :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. + + .. note:: - :param dgm: Persistence diagram obtained after calling :func:`extend_filtration()` and :func:`persistence()`. - :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. + This function should be called only if :func:`extend_filtration()`, + :func:`initialize_filtration()`, + and :func:`persistence()` have been called first! .. note:: - This function should be called only after calling :func:`extend_filtration()` and :func:`persistence()`. + The coordinates of the persistence diagram points might be a little different than the + original filtration values due to the internal transformation (scaling to [-2,-1]) that is + performed on these values during the computation of extended persistence. """ return self.get_ptr().compute_extended_persistence_subdiagrams(dgm) -- cgit v1.2.3 From 61691b0081cb868645335c0b1433ddcc0bcbf9e3 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Thu, 19 Mar 2020 13:09:59 -0400 Subject: new fixes --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 45 ++++++++++++++++----------- src/python/gudhi/simplex_tree.pxd | 4 +-- src/python/gudhi/simplex_tree.pyx | 32 ++++++++++++++----- src/python/include/Simplex_tree_interface.h | 13 ++++++++ src/python/test/test_simplex_tree.py | 18 ++++++----- 5 files changed, 77 insertions(+), 35 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 697afe26..50b8e582 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -100,6 +100,12 @@ class Simplex_tree { void assign_key(Simplex_key); Simplex_key key() const; }; + struct Extended_filtration_data { + Filtration_value minval; + Filtration_value maxval; + Extended_filtration_data(){} + Extended_filtration_data(Filtration_value vmin, Filtration_value vmax){ minval = vmin; maxval = vmax; } + }; typedef typename std::conditional::type Key_simplex_base; @@ -126,8 +132,6 @@ class Simplex_tree { private: typedef typename Dictionary::iterator Dictionary_it; typedef typename Dictionary_it::value_type Dit_value_t; - Filtration_value minval_; - Filtration_value maxval_; struct return_first { Vertex_handle operator()(const Dit_value_t& p_sh) const { @@ -1490,15 +1494,16 @@ class Simplex_tree { * performed on these values during the computation of extended persistence. * @param[in] dgm Persistence diagram obtained after calling `extend_filtration()`, * `initialize_filtration()`, and `Gudhi::persistent_cohomology::Persistent_cohomology< FilteredComplex, CoefficientField >::compute_persistent_cohomology()`. + * @param[in] efd Structure containing the minimum and maximum values of the original filtration * @return A vector of four persistence diagrams. The first one is Ordinary, the * second one is Relative, the third one is Extended+ and the fourth one is Extended-. * See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. */ - std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm){ + std::vector>>> extended_persistence_subdiagrams(const std::vector>>& dgm, const Extended_filtration_data& efd){ std::vector>>> new_dgm(4); Filtration_value x, y; - Filtration_value minval_ = this->minval_; - Filtration_value maxval_ = this->maxval_; + Filtration_value minval = efd.minval; + Filtration_value maxval = efd.maxval; for(unsigned int i = 0; i < dgm.size(); i++){ int h = dgm[i].first; Filtration_value px = dgm[i].second.first; @@ -1506,18 +1511,18 @@ class Simplex_tree { if(std::isinf(py)) continue; else{ if ((px <= -1) & (py <= -1)){ - x = minval_ + (maxval_-minval_)*(px + 2); - y = minval_ + (maxval_-minval_)*(py + 2); + x = minval + (maxval-minval)*(px + 2); + y = minval + (maxval-minval)*(py + 2); new_dgm[0].push_back(std::make_pair(h, std::make_pair(x,y))); } else if ((px >= 1) & (py >= 1)){ - x = minval_ - (maxval_-minval_)*(px - 2); - y = minval_ - (maxval_-minval_)*(py - 2); + x = minval - (maxval-minval)*(px - 2); + y = minval - (maxval-minval)*(py - 2); new_dgm[1].push_back(std::make_pair(h, std::make_pair(x,y))); } else { - x = minval_ + (maxval_-minval_)*(px + 2); - y = minval_ - (maxval_-minval_)*(py - 2); + x = minval + (maxval-minval)*(px + 2); + y = minval - (maxval-minval)*(py - 2); if (x <= y){ new_dgm[2].push_back(std::make_pair(h, std::make_pair(x,y))); } @@ -1535,23 +1540,23 @@ class Simplex_tree { * and computes the extended persistence diagram induced by the lower-star filtration * computed with these values. * \post Note that after calling this function, the filtration - * values are actually modified. The function `compute_extended_persistence_subdiagrams()` + * values are actually modified. The function `extended_persistence_subdiagrams()` * retrieves the original values and separates the extended persistence diagram points * w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after * computing the persistent homology of the extended simplicial complex. * \pre Note that this code creates an extra vertex internally, so you should make sure that * the Simplex tree does not contain a vertex with the largest Vertex_handle. */ - void extend_filtration() { + Extended_filtration_data extend_filtration() { // Compute maximum and minimum of filtration values Vertex_handle maxvert = std::numeric_limits::min(); - this->minval_ = std::numeric_limits::infinity(); - this->maxval_ = -std::numeric_limits::infinity(); + Filtration_value minval = std::numeric_limits::infinity(); + Filtration_value maxval = -std::numeric_limits::infinity(); for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh){ Filtration_value f = this->filtration(sh); - this->minval_ = std::min(this->minval_, f); - this->maxval_ = std::max(this->maxval_, f); + minval = std::min(minval, f); + maxval = std::max(maxval, f); maxvert = std::max(sh->first, maxvert); } @@ -1578,7 +1583,7 @@ class Simplex_tree { vr.push_back(maxvert); if (this->dimension(sh) == 0){ Filtration_value v = this->filtration(sh); - Filtration_value scaled_v = (v-this->minval_)/(this->maxval_-this->minval_); + Filtration_value scaled_v = (v-minval)/(maxval-minval); // Assign ascending value between -2 and -1 to vertex this->assign_filtration(sh, -2 + scaled_v); // Assign descending value between 1 and 2 to cone on vertex @@ -1593,6 +1598,10 @@ class Simplex_tree { // Automatically assign good values for simplices this->make_filtration_non_decreasing(); + + // Return the filtration data + Extended_filtration_data efd(minval, maxval); + return efd; } /** \brief Returns a vertex of `sh` that has the same filtration value as `sh` if it exists, and `null_vertex()` otherwise. diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index ae32eb82..b6284af4 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -57,8 +57,8 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": void remove_maximal_simplex(vector[int] simplex) bool prune_above_filtration(double filtration) bool make_filtration_non_decreasing() - void extend_filtration() - vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]]) + void compute_extended_filtration() + vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]] dgm) # Iterators over Simplex tree pair[vector[int], double] get_simplex_and_filtration(Simplex_tree_simplex_handle f_simplex) Simplex_tree_simplices_iterator get_simplices_iterator_begin() diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 7af44683..3502000a 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -405,7 +405,7 @@ cdef class SimplexTree: Note that after calling this function, the filtration values are actually modified within the Simplex_tree. - The function :func:`compute_extended_persistence_subdiagrams()` + The function :func:`extended_persistence()` retrieves the original values. .. note:: @@ -413,21 +413,31 @@ cdef class SimplexTree: Note that this code creates an extra vertex internally, so you should make sure that the Simplex_tree does not contain a vertex with the largest Vertex_handle. """ - return self.get_ptr().extend_filtration() + return self.get_ptr().compute_extended_filtration() - def compute_extended_persistence_subdiagrams(self, dgm): + def extended_persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): """This function retrieves good values for extended persistence, and separate the diagrams into the ordinary, relative, extended+ and extended- subdiagrams. - :param dgm: Persistence diagram obtained after calling :func:`extend_filtration()`, :func:`initialize_filtration()`, and :func:`persistence()`. - + :param homology_coeff_field: The homology coefficient field. Must be a + prime number. Default value is 11. + :type homology_coeff_field: int. + :param min_persistence: The minimum persistence value to take into + account (strictly greater than min_persistence). Default value is + 0.0. + Sets min_persistence to -1.0 to see all values. + :type min_persistence: float. + :param persistence_dim_max: If true, the persistent homology for the + maximal dimension in the complex is computed. If false, it is + ignored. Default is false. + :type persistence_dim_max: bool :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. .. note:: This function should be called only if :func:`extend_filtration()`, :func:`initialize_filtration()`, - and :func:`persistence()` have been called first! + and (optionally) :func:`persistence()` have been called first! .. note:: @@ -435,7 +445,15 @@ cdef class SimplexTree: original filtration values due to the internal transformation (scaling to [-2,-1]) that is performed on these values during the computation of extended persistence. """ - return self.get_ptr().compute_extended_persistence_subdiagrams(dgm) + cdef vector[pair[int, pair[double, double]]] persistence_result + if self.pcohptr == NULL: + self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), persistence_dim_max) + if self.pcohptr != NULL: + self.pcohptr.get_persistence(homology_coeff_field, min_persistence) + if self.pcohptr != NULL: + pairs = self.pcohptr.persistence_pairs() + persistence_result = [(len(splx1)-1, [self.filtration(splx1), self.filtration(splx2)]) for [splx1, splx2] in pairs] + return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result) def persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index 4a7062d6..50ed58d0 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -37,8 +37,12 @@ class Simplex_tree_interface : public Simplex_tree { using Filtered_simplices = std::vector; using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator; using Complex_simplex_iterator = typename Base::Complex_simplex_iterator; + using Extended_filtration_data = typename Base::Extended_filtration_data; public: + + Extended_filtration_data efd; + bool find_simplex(const Simplex& vh) { return (Base::find(vh) != Base::null_simplex()); } @@ -117,6 +121,15 @@ class Simplex_tree_interface : public Simplex_tree { return cofaces; } + void compute_extended_filtration() { + this->efd = this->extend_filtration(); + return; + } + + std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm){ + return this->extended_persistence_subdiagrams(dgm, this->efd); + } + void create_persistence(Gudhi::Persistent_cohomology_interface* pcoh) { Base::initialize_filtration(); pcoh = new Gudhi::Persistent_cohomology_interface(*this); diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index 63eee9a5..20f6aabf 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -9,6 +9,7 @@ """ from gudhi import SimplexTree +import pytest __author__ = "Vincent Rouvreau" __copyright__ = "Copyright (C) 2016 Inria" @@ -322,15 +323,16 @@ def test_extend_filtration(): ([0, 3, 6], 2.0) ] + dgms = st.extended_persistence() - dgm = st.persistence() - L = st.compute_extended_persistence_subdiagrams(dgm) - assert L == [ - [(0, (1.9999999999999998, 2.9999999999999996))], - [(1, (5.0, 4.0))], - [(0, (1.0, 6.0))], - [(1, (6.0, 1.0))] - ] + assert dgms[0][0][1][0] == pytest.approx(2.) + assert dgms[0][0][1][1] == pytest.approx(3.) + assert dgms[1][0][1][0] == pytest.approx(5.) + assert dgms[1][0][1][1] == pytest.approx(4.) + assert dgms[2][0][1][0] == pytest.approx(1.) + assert dgms[2][0][1][1] == pytest.approx(6.) + assert dgms[3][0][1][0] == pytest.approx(6.) + assert dgms[3][0][1][1] == pytest.approx(1.) def test_simplices_iterator(): -- cgit v1.2.3 From 361abfcfa9ec18c76837f847f8e2e3a060cf7db7 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Thu, 19 Mar 2020 17:02:55 -0400 Subject: added decoding function --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 82 +++++++++++---------------- src/python/gudhi/simplex_tree.pyx | 10 +--- src/python/include/Simplex_tree_interface.h | 27 ++++++++- 3 files changed, 63 insertions(+), 56 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 50b8e582..9008c5f2 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -87,6 +87,8 @@ class Simplex_tree { /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings Siblings; + enum Extended_simplex_type {UP, DOWN, EXTRA}; + struct Key_simplex_base_real { Key_simplex_base_real() : key_(-1) {} void assign_key(Simplex_key k) { key_ = k; } @@ -1486,66 +1488,50 @@ class Simplex_tree { } } - /** \brief Retrieve good values for extended persistence, and separate the - * diagrams into the ordinary, relative, extended+ and extended- subdiagrams. + /** \brief Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the + * computation of extended persistence requires modifying the filtration values, this function can be used + * to recover the original values. Moreover, computing extended persistence requires adding new simplices + * in the Simplex_tree. Hence, this function also outputs the type of each simplex. It can be either UP (which means + * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means + * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or + * EXTRA (which means the simplex is the cone point). Note that if the simplex type is DOWN, the original filtration value + * is set to be the original filtration value of the corresponding (not coned) original simplex. * \pre This function should be called only if `extend_filtration()` has been called first! - * \post The coordinates of the persistence diagram points might be a little different than the - * original filtration values due to the internal transformation (scaling to [-2,-1]) that is - * performed on these values during the computation of extended persistence. - * @param[in] dgm Persistence diagram obtained after calling `extend_filtration()`, - * `initialize_filtration()`, and `Gudhi::persistent_cohomology::Persistent_cohomology< FilteredComplex, CoefficientField >::compute_persistent_cohomology()`. - * @param[in] efd Structure containing the minimum and maximum values of the original filtration - * @return A vector of four persistence diagrams. The first one is Ordinary, the - * second one is Relative, the third one is Extended+ and the fourth one is Extended-. - * See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. + * \post The output filtration value is supposed to be the same, but might be a little different, than the + * original filtration value, due to the internal transformation (scaling to [-2,-1]) that is + * performed on the original filtration values during the computation of extended persistence. + * @param[in] f Filtration value of the simplex in the extended (i.e., modified) filtration. + * @param[in] efd Structure containing the minimum and maximum values of the original filtration. This the output of `extend_filtration()`. + * @return A pair containing the original filtration value of the simplex as well as the simplex type. */ - std::vector>>> extended_persistence_subdiagrams(const std::vector>>& dgm, const Extended_filtration_data& efd){ - std::vector>>> new_dgm(4); - Filtration_value x, y; + std::pair decode_extended_filtration(Filtration_value f, const Extended_filtration_data& efd){ + std::pair p; Filtration_value minval = efd.minval; Filtration_value maxval = efd.maxval; - for(unsigned int i = 0; i < dgm.size(); i++){ - int h = dgm[i].first; - Filtration_value px = dgm[i].second.first; - Filtration_value py = dgm[i].second.second; - if(std::isinf(py)) continue; - else{ - if ((px <= -1) & (py <= -1)){ - x = minval + (maxval-minval)*(px + 2); - y = minval + (maxval-minval)*(py + 2); - new_dgm[0].push_back(std::make_pair(h, std::make_pair(x,y))); - } - else if ((px >= 1) & (py >= 1)){ - x = minval - (maxval-minval)*(px - 2); - y = minval - (maxval-minval)*(py - 2); - new_dgm[1].push_back(std::make_pair(h, std::make_pair(x,y))); - } - else { - x = minval + (maxval-minval)*(px + 2); - y = minval - (maxval-minval)*(py - 2); - if (x <= y){ - new_dgm[2].push_back(std::make_pair(h, std::make_pair(x,y))); - } - else{ - new_dgm[3].push_back(std::make_pair(h, std::make_pair(x,y))); - } - } - } + if (f >= -2 && f <= -1){ + p.first = minval + (maxval-minval)*(f + 2); p.second = UP; } - return new_dgm; - } + else if (f >= 1 && f <= 2){ + p.first = minval - (maxval-minval)*(f - 2); p.second = DOWN; + } + else{ + p.first = -3; p.second = EXTRA; + } + return p; + }; /** \brief Extend filtration for computing extended persistence. * This function only uses the filtration values at the 0-dimensional simplices, * and computes the extended persistence diagram induced by the lower-star filtration * computed with these values. * \post Note that after calling this function, the filtration - * values are actually modified. The function `extended_persistence_subdiagrams()` - * retrieves the original values and separates the extended persistence diagram points - * w.r.t. their types (Ord, Rel, Ext+, Ext-) and should always be called after - * computing the persistent homology of the extended simplicial complex. + * values are actually modified. The function `decode_extended_filtration()` + * retrieves the original values and outputs the extended simplex type. * \pre Note that this code creates an extra vertex internally, so you should make sure that - * the Simplex tree does not contain a vertex with the largest Vertex_handle. + * the Simplex tree does not contain a vertex with the largest Vertex_handle. + * @return A data structure containing the maximum and minimum values of the original filtration. + * It is meant to be provided as input to `decode_extended_filtration()` in order to retrieve + * the original filtration values for each simplex. */ Extended_filtration_data extend_filtration() { diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 3502000a..2cd81c14 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -415,9 +415,9 @@ cdef class SimplexTree: """ return self.get_ptr().compute_extended_filtration() - def extended_persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): + def extended_persistence(self, homology_coeff_field=11, min_persistence=0): """This function retrieves good values for extended persistence, and separate the diagrams - into the ordinary, relative, extended+ and extended- subdiagrams. + into the Ordinary, Relative, Extended+ and Extended- subdiagrams. :param homology_coeff_field: The homology coefficient field. Must be a prime number. Default value is 11. @@ -427,10 +427,6 @@ cdef class SimplexTree: 0.0. Sets min_persistence to -1.0 to see all values. :type min_persistence: float. - :param persistence_dim_max: If true, the persistent homology for the - maximal dimension in the complex is computed. If false, it is - ignored. Default is false. - :type persistence_dim_max: bool :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. .. note:: @@ -447,7 +443,7 @@ cdef class SimplexTree: """ cdef vector[pair[int, pair[double, double]]] persistence_result if self.pcohptr == NULL: - self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), persistence_dim_max) + self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), True) if self.pcohptr != NULL: self.pcohptr.get_persistence(homology_coeff_field, min_persistence) if self.pcohptr != NULL: diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index 50ed58d0..a6b1a06e 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -38,6 +38,7 @@ class Simplex_tree_interface : public Simplex_tree { using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator; using Complex_simplex_iterator = typename Base::Complex_simplex_iterator; using Extended_filtration_data = typename Base::Extended_filtration_data; + using Extended_simplex_type = typename Base::Extended_simplex_type; public: @@ -127,7 +128,31 @@ class Simplex_tree_interface : public Simplex_tree { } std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm){ - return this->extended_persistence_subdiagrams(dgm, this->efd); + std::vector>>> new_dgm(4); + for (unsigned int i = 0; i < dgm.size(); i++){ + std::pair px = this->decode_extended_filtration(dgm[i].second.first, this->efd); + std::pair py = this->decode_extended_filtration(dgm[i].second.second, this->efd); + std::pair> pd_point = std::make_pair(dgm[i].first, std::make_pair(px.first, py.first)); + //Ordinary + if (px.second == Base::UP && py.second == Base::UP){ + new_dgm[0].push_back(pd_point); + } + // Relative + else if (px.second == Base::DOWN && py.second == Base::DOWN){ + new_dgm[1].push_back(pd_point); + } + else{ + // Extended+ + if (px.first < py.first){ + new_dgm[2].push_back(pd_point); + } + //Extended- + else{ + new_dgm[3].push_back(pd_point); + } + } + } + return new_dgm; } void create_persistence(Gudhi::Persistent_cohomology_interface* pcoh) { -- cgit v1.2.3 From 1e0e378ab442672ef569e93c4114b0e99ea70f6e Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Fri, 20 Mar 2020 12:47:13 -0400 Subject: small fix --- src/python/gudhi/simplex_tree.pyx | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 2cd81c14..5b850462 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -443,7 +443,7 @@ cdef class SimplexTree: """ cdef vector[pair[int, pair[double, double]]] persistence_result if self.pcohptr == NULL: - self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), True) + self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), False) if self.pcohptr != NULL: self.pcohptr.get_persistence(homology_coeff_field, min_persistence) if self.pcohptr != NULL: -- cgit v1.2.3 From bc223c3cc7cb9e9c0bb3573af720fce9c5380b94 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Mon, 23 Mar 2020 21:22:16 -0400 Subject: new fixes --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 25 +++++++++++++++----- src/python/gudhi/simplex_tree.pxd | 2 +- src/python/gudhi/simplex_tree.pyx | 21 +++++++---------- src/python/include/Simplex_tree_interface.h | 34 ++++++++++++++------------- src/python/test/test_simplex_tree.py | 7 ++---- 5 files changed, 48 insertions(+), 41 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 9008c5f2..de97d6f2 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -42,6 +42,20 @@ namespace Gudhi { +/** + * \class Extended_simplex_type Simplex_tree.h gudhi/Simplex_tree.h + * \brief Extended simplex type data structure for representing the type of simplices in an extended filtration. + * + * \details The extended simplex type can be either UP (which means + * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means + * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or + * EXTRA (which means the simplex is the cone point). + * + * Details may be found in section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z. + * + */ +enum class Extended_simplex_type {UP, DOWN, EXTRA}; + struct Simplex_tree_options_full_featured; /** @@ -87,7 +101,7 @@ class Simplex_tree { /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings Siblings; - enum Extended_simplex_type {UP, DOWN, EXTRA}; + struct Key_simplex_base_real { Key_simplex_base_real() : key_(-1) {} @@ -106,7 +120,7 @@ class Simplex_tree { Filtration_value minval; Filtration_value maxval; Extended_filtration_data(){} - Extended_filtration_data(Filtration_value vmin, Filtration_value vmax){ minval = vmin; maxval = vmax; } + Extended_filtration_data(Filtration_value vmin, Filtration_value vmax): minval(vmin), maxval(vmax) {} }; typedef typename std::conditional::type Key_simplex_base; @@ -1370,7 +1384,6 @@ class Simplex_tree { // Replacing if(f=max)) would mean that if f is NaN, we replace it with the max of the children. // That seems more useful than keeping NaN. if (!(simplex.second.filtration() >= max_filt_border_value)) { - // Store the filtration modification information modified = true; simplex.second.assign_filtration(max_filt_border_value); @@ -1509,13 +1522,13 @@ class Simplex_tree { Filtration_value minval = efd.minval; Filtration_value maxval = efd.maxval; if (f >= -2 && f <= -1){ - p.first = minval + (maxval-minval)*(f + 2); p.second = UP; + p.first = minval + (maxval-minval)*(f + 2); p.second = Extended_simplex_type::UP; } else if (f >= 1 && f <= 2){ - p.first = minval - (maxval-minval)*(f - 2); p.second = DOWN; + p.first = minval - (maxval-minval)*(f - 2); p.second = Extended_simplex_type::DOWN; } else{ - p.first = -3; p.second = EXTRA; + p.first = std::numeric_limits::quiet_NaN(); p.second = Extended_simplex_type::EXTRA; } return p; }; diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index b6284af4..595f22bb 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -58,7 +58,7 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": bool prune_above_filtration(double filtration) bool make_filtration_non_decreasing() void compute_extended_filtration() - vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]] dgm) + vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]] dgm, double min_persistence) # Iterators over Simplex tree pair[vector[int], double] get_simplex_and_filtration(Simplex_tree_simplex_handle f_simplex) Simplex_tree_simplices_iterator get_simplices_iterator_begin() diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 5b850462..bcb1578d 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -411,7 +411,7 @@ cdef class SimplexTree: .. note:: Note that this code creates an extra vertex internally, so you should make sure that - the Simplex_tree does not contain a vertex with the largest Vertex_handle. + the Simplex_tree does not contain a vertex with the largest possible value (i.e., 4294967295). """ return self.get_ptr().compute_extended_filtration() @@ -422,18 +422,16 @@ cdef class SimplexTree: :param homology_coeff_field: The homology coefficient field. Must be a prime number. Default value is 11. :type homology_coeff_field: int. - :param min_persistence: The minimum persistence value to take into + :param min_persistence: The minimum persistence value (i.e., the absolute value of the difference between the persistence diagram point coordinates) to take into account (strictly greater than min_persistence). Default value is 0.0. Sets min_persistence to -1.0 to see all values. :type min_persistence: float. - :returns: A vector of four persistence diagrams. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. + :returns: A list of four persistence diagrams in the format described in :func:`persistence()`. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. .. note:: - This function should be called only if :func:`extend_filtration()`, - :func:`initialize_filtration()`, - and (optionally) :func:`persistence()` have been called first! + This function should be called only if :func:`extend_filtration()` has been called first! .. note:: @@ -442,14 +440,11 @@ cdef class SimplexTree: performed on these values during the computation of extended persistence. """ cdef vector[pair[int, pair[double, double]]] persistence_result - if self.pcohptr == NULL: - self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), False) - if self.pcohptr != NULL: - self.pcohptr.get_persistence(homology_coeff_field, min_persistence) if self.pcohptr != NULL: - pairs = self.pcohptr.persistence_pairs() - persistence_result = [(len(splx1)-1, [self.filtration(splx1), self.filtration(splx2)]) for [splx1, splx2] in pairs] - return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result) + del self.pcohptr + self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), False) + persistence_result = self.pcohptr.get_persistence(homology_coeff_field, -1.) + return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result, min_persistence) def persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index a6b1a06e..1a18aed6 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -38,7 +38,6 @@ class Simplex_tree_interface : public Simplex_tree { using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator; using Complex_simplex_iterator = typename Base::Complex_simplex_iterator; using Extended_filtration_data = typename Base::Extended_filtration_data; - using Extended_simplex_type = typename Base::Extended_simplex_type; public: @@ -124,31 +123,34 @@ class Simplex_tree_interface : public Simplex_tree { void compute_extended_filtration() { this->efd = this->extend_filtration(); + this->initialize_filtration(); return; } - std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm){ + std::vector>>> compute_extended_persistence_subdiagrams(const std::vector>>& dgm, Filtration_value min_persistence){ std::vector>>> new_dgm(4); for (unsigned int i = 0; i < dgm.size(); i++){ std::pair px = this->decode_extended_filtration(dgm[i].second.first, this->efd); std::pair py = this->decode_extended_filtration(dgm[i].second.second, this->efd); std::pair> pd_point = std::make_pair(dgm[i].first, std::make_pair(px.first, py.first)); - //Ordinary - if (px.second == Base::UP && py.second == Base::UP){ - new_dgm[0].push_back(pd_point); - } - // Relative - else if (px.second == Base::DOWN && py.second == Base::DOWN){ - new_dgm[1].push_back(pd_point); - } - else{ - // Extended+ - if (px.first < py.first){ - new_dgm[2].push_back(pd_point); + if(std::abs(px.first - py.first) > min_persistence){ + //Ordinary + if (px.second == Extended_simplex_type::UP && py.second == Extended_simplex_type::UP){ + new_dgm[0].push_back(pd_point); + } + // Relative + else if (px.second == Extended_simplex_type::DOWN && py.second == Extended_simplex_type::DOWN){ + new_dgm[1].push_back(pd_point); } - //Extended- else{ - new_dgm[3].push_back(pd_point); + // Extended+ + if (px.first < py.first){ + new_dgm[2].push_back(pd_point); + } + //Extended- + else{ + new_dgm[3].push_back(pd_point); + } } } } diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index 20f6aabf..70b26e97 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -291,10 +291,8 @@ def test_extend_filtration(): ([5], 6.0) ] - st.extend_filtration() - st.initialize_filtration() - + assert list(st.get_filtration()) == [ ([6], -3.0), ([0], -2.0), @@ -323,7 +321,7 @@ def test_extend_filtration(): ([0, 3, 6], 2.0) ] - dgms = st.extended_persistence() + dgms = st.extended_persistence(min_persistence=-1.) assert dgms[0][0][1][0] == pytest.approx(2.) assert dgms[0][0][1][1] == pytest.approx(3.) @@ -334,7 +332,6 @@ def test_extend_filtration(): assert dgms[3][0][1][0] == pytest.approx(6.) assert dgms[3][0][1][1] == pytest.approx(1.) - def test_simplices_iterator(): st = SimplexTree() -- cgit v1.2.3 From 20ba972d2a7fd14e564ce4adb3921f3f8190fc71 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Wed, 25 Mar 2020 13:00:58 -0400 Subject: update biblio --- biblio/bibliography.bib | 36 +++++++++++++++++++-------- src/Simplex_tree/include/gudhi/Simplex_tree.h | 4 +-- src/python/gudhi/simplex_tree.pyx | 2 +- 3 files changed, 29 insertions(+), 13 deletions(-) (limited to 'src/python') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 3bbe7960..b017a07e 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -7,11 +7,13 @@ } @article{Carriere17c, - author = {Carri\`ere, Mathieu and Michel, Bertrand and Oudot, Steve}, - title = {{Statistical Analysis and Parameter Selection for Mapper}}, - journal = {CoRR}, - volume = {abs/1706.00204}, - year = {2017} +author = {Carri{\`{e}}re, Mathieu and Michel, Bertrand and Oudot, Steve}, +journal = {Journal of Machine Learning Research}, +pages = {1--39}, +publisher = {JMLR.org}, +title = {{Statistical analysis and parameter selection for Mapper}}, +volume = {19}, +year = {2018} } @inproceedings{Dey13, @@ -23,11 +25,14 @@ } @article{Carriere16, - title={{Structure and Stability of the 1-Dimensional Mapper}}, - author={Carri\`ere, Mathieu and Oudot, Steve}, - journal={CoRR}, - volume= {abs/1511.05823}, - year={2015} +author = {Carri{\`{e}}re, Mathieu and Oudot, Steve}, +journal = {Foundations of Computational Mathematics}, +number = {6}, +pages = {1333--1396}, +publisher = {Springer-Verlag}, +title = {{Structure and stability of the one-dimensional Mapper}}, +volume = {18}, +year = {2017} } @inproceedings{zigzag_reflection, @@ -36,6 +41,17 @@ year = {2014 $\ \ \ \ \ \ \ \ \ \ \ $ \emph{In Preparation}}, } +@article{Cohen-Steiner2009, +author = {Cohen-Steiner, David and Edelsbrunner, Herbert and Harer, John}, +journal = {Foundations of Computational Mathematics}, +number = {1}, +pages = {79--103}, +publisher = {Springer-Verlag}, +title = {{Extending persistence using Poincar{\'{e}} and Lefschetz duality}}, +volume = {9}, +year = {2009} +} + @misc{gudhi_stpcoh, author = {Cl\'ement Maria}, title = "\textsc{Gudhi}, Simplex Tree and Persistent Cohomology Packages", diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index de97d6f2..60720567 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -51,7 +51,7 @@ namespace Gudhi { * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or * EXTRA (which means the simplex is the cone point). * - * Details may be found in section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z. + * Details may be found in \cite Cohen-Steiner2009 and section 2.2 in \cite Carriere16. * */ enum class Extended_simplex_type {UP, DOWN, EXTRA}; @@ -1507,7 +1507,7 @@ class Simplex_tree { * in the Simplex_tree. Hence, this function also outputs the type of each simplex. It can be either UP (which means * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or - * EXTRA (which means the simplex is the cone point). Note that if the simplex type is DOWN, the original filtration value + * EXTRA (which means the simplex is the cone point). See the definition of Extended_simplex_type. Note that if the simplex type is DOWN, the original filtration value * is set to be the original filtration value of the corresponding (not coned) original simplex. * \pre This function should be called only if `extend_filtration()` has been called first! * \post The output filtration value is supposed to be the same, but might be a little different, than the diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index bcb1578d..6bb22171 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -427,7 +427,7 @@ cdef class SimplexTree: 0.0. Sets min_persistence to -1.0 to see all values. :type min_persistence: float. - :returns: A list of four persistence diagrams in the format described in :func:`persistence()`. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. + :returns: A list of four persistence diagrams in the format described in :func:`persistence()`. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See and https://link.springer.com/article/10.1007/s10208-008-9027-z and section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. .. note:: -- cgit v1.2.3 From b2a549c055c2796fe4eb1e4e4265cdd718753416 Mon Sep 17 00:00:00 2001 From: MathieuCarriere Date: Wed, 25 Mar 2020 15:10:35 -0400 Subject: fix biblio --- src/python/gudhi/simplex_tree.pyx | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 6bb22171..cc3753e1 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -427,7 +427,7 @@ cdef class SimplexTree: 0.0. Sets min_persistence to -1.0 to see all values. :type min_persistence: float. - :returns: A list of four persistence diagrams in the format described in :func:`persistence()`. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See and https://link.springer.com/article/10.1007/s10208-008-9027-z and section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. + :returns: A list of four persistence diagrams in the format described in :func:`persistence()`. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See https://link.springer.com/article/10.1007/s10208-008-9027-z and/or section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. .. note:: -- cgit v1.2.3 From 4cdc7f03fb5917134ba8886b026c8990f56bcfeb Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 11:21:27 +0200 Subject: merged doc from barycenters to wasserstein distance --- src/python/doc/wasserstein_distance_sum.inc | 10 +-- src/python/doc/wasserstein_distance_user.rst | 91 ++++++++++++++++++++++++++-- 2 files changed, 92 insertions(+), 9 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_sum.inc b/src/python/doc/wasserstein_distance_sum.inc index a97f428d..09424de2 100644 --- a/src/python/doc/wasserstein_distance_sum.inc +++ b/src/python/doc/wasserstein_distance_sum.inc @@ -3,11 +3,11 @@ +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ | .. figure:: | The q-Wasserstein distance measures the similarity between two | :Author: Theo Lacombe | - | ../../doc/Bottleneck_distance/perturb_pd.png | persistence diagrams. It's the minimum value c that can be achieved | | - | :figclass: align-center | by a perfect matching between the points of the two diagrams (+ all | :Introduced in: GUDHI 3.1.0 | - | | diagonal points), where the value of a matching is defined as the | | - | Wasserstein distance is the q-th root of the sum of the | q-th root of the sum of all edge lengths to the power q. Edge lengths| :Copyright: MIT | - | edge lengths to the power q. | are measured in norm p, for :math:`1 \leq p \leq \infty`. | | + | ../../doc/Bottleneck_distance/perturb_pd.png | persistence diagrams using the sum of all edges lengths (instead of | | + | :figclass: align-center | the maximum). It allows to define sophisticated objects such as | :Introduced in: GUDHI 3.1.0 | + | | barycenters of a family of persistence diagrams. | | + | Wasserstein distance is the q-th root of the sum of the | | :Copyright: MIT | + | edge lengths to the power q. | | | | | | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ | * :doc:`wasserstein_distance_user` | | diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index a9b21fa5..6de05afc 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -9,10 +9,16 @@ Definition .. include:: wasserstein_distance_sum.inc -Functions ---------- -This implementation uses the Python Optimal Transport library and is based on -ideas from "Large Scale Computation of Means and Cluster for Persistence +The q-Wasserstein distance is defined as the minimal value +by a perfect matching between the points of the two diagrams (+ all +diagonal points), where the value of a matching is defined as the +q-th root of the sum of all edge lengths to the power q. Edge lengths +are measured in norm p, for :math:`1 \leq p \leq \infty`. + +Distance Functions +------------------ +This first implementation uses the Python Optimal Transport library and is based +on ideas from "Large Scale Computation of Means and Cluster for Persistence Diagrams via Optimal Transport" :cite:`10.5555/3327546.3327645`. .. autofunction:: gudhi.wasserstein.wasserstein_distance @@ -84,3 +90,80 @@ The output is: 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 + + +Barycenters +----------- + +A Frechet mean (or barycenter) is a generalization of the arithmetic +mean in a non linear space such as the one of persistence diagrams. +Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is +defined as a minimizer of the variance functional, that is of +:math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. +where :math:`d_2` denotes the Wasserstein-2 distance between +persistence diagrams. +It is known to exist and is generically unique. However, an exact +computation is in general untractable. Current implementation +available is based on (Turner et al., 2014), +:cite:`turner2014frechet` +and uses an EM-scheme to +provide a local minimum of the variance functional (somewhat similar +to the Lloyd algorithm to estimate a solution to the k-means +problem). The local minimum returned depends on the initialization of +the barycenter. +The combinatorial structure of the algorithm limits its +scaling on large scale problems (thousands of diagrams and of points +per diagram). + +.. figure:: + ./img/barycenter.png + :figclass: align-center + + Illustration of Frechet mean between persistence + diagrams. + + +.. autofunction:: gudhi.barycenter.lagrangian_barycenter + +Basic example +------------- + +This example computes the Frechet mean (aka Wasserstein barycenter) between +four persistence diagrams. +It is initialized on the 4th diagram. +As the algorithm is not convex, its output depends on the initialization and +is only a local minimum of the objective function. +Initialization can be either given as an integer (in which case the i-th +diagram of the list is used as initial estimate) or as a diagram. +If None, it will randomly select one of the diagram of the list +as initial estimate. +Note that persistence diagrams must be submitted as +(n x 2) numpy arrays and must not contain inf values. + + +.. testcode:: + + import gudhi.barycenter + import numpy as np + + dg1 = np.array([[0.2, 0.5]]) + dg2 = np.array([[0.2, 0.7]]) + dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + dg4 = np.array([]) + pdiagset = [dg1, dg2, dg3, dg4] + bary = gudhi.wasserstein.barycenter.lagrangian_barycenter(pdiagset=pdiagset,init=3) + + message = "Wasserstein barycenter estimated:" + print(message) + print(bary) + +The output is: + +.. testoutput:: + + Wasserstein barycenter estimated: + [[0.27916667 0.55416667] + [0.7375 0.7625 ] + [0.2375 0.2625 ]] + + -- cgit v1.2.3 From 4adbdcf16f311b0b5151311f77cfead5bf065bf4 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 11:22:50 +0200 Subject: removed barycenters specific doc files as those are included in wasserstein distance now --- src/python/doc/barycenter_sum.inc | 24 --------------- src/python/doc/barycenter_user.rst | 60 -------------------------------------- 2 files changed, 84 deletions(-) delete mode 100644 src/python/doc/barycenter_sum.inc delete mode 100644 src/python/doc/barycenter_user.rst (limited to 'src/python') diff --git a/src/python/doc/barycenter_sum.inc b/src/python/doc/barycenter_sum.inc deleted file mode 100644 index da2bdd84..00000000 --- a/src/python/doc/barycenter_sum.inc +++ /dev/null @@ -1,24 +0,0 @@ -.. table:: - :widths: 30 50 20 - - +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ - | .. figure:: | A Frechet mean (or barycenter) is a generalization of the arithmetic | :Author: Theo Lacombe | - | ./img/barycenter.png | mean in a non linear space such as the one of persistence diagrams. | | - | :figclass: align-center | Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is | :Introduced in: GUDHI 3.1.0 | - | | defined as a minimizer of the variance functional, that is of | | - | Illustration of Frechet mean between persistence | :math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. | :Copyright: MIT | - | diagrams. | where :math:`d_2` denotes the Wasserstein-2 distance between | | - | | persistence diagrams. | | - | | It is known to exist and is generically unique. However, an exact | | - | | computation is in general untractable. Current implementation | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | - | | available is based on [Turner et al, 2014], and uses an EM-scheme to | | - | | provide a local minimum of the variance functional (somewhat similar | | - | | to the Lloyd algorithm to estimate a solution to the k-means | | - | | problem). The local minimum returned depends on the initialization of| | - | | the barycenter. | | - | | The combinatorial structure of the algorithm limits its | | - | | scaling on large scale problems (thousands of diagrams and of points | | - | | per diagram). | | - +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ - | * :doc:`barycenter_user` | | - +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/barycenter_user.rst b/src/python/doc/barycenter_user.rst deleted file mode 100644 index 83e9bebb..00000000 --- a/src/python/doc/barycenter_user.rst +++ /dev/null @@ -1,60 +0,0 @@ -:orphan: - -.. To get rid of WARNING: document isn't included in any toctree - -Barycenter user manual -================================ -Definition ----------- - -.. include:: barycenter_sum.inc - -This implementation is based on ideas from "Frechet means for distribution of -persistence diagrams", Turner et al. 2014. - -Function --------- -.. autofunction:: gudhi.barycenter.lagrangian_barycenter - - -Basic example -------------- - -This example computes the Frechet mean (aka Wasserstein barycenter) between -four persistence diagrams. -It is initialized on the 4th diagram. -As the algorithm is not convex, its output depends on the initialization and -is only a local minimum of the objective function. -Initialization can be either given as an integer (in which case the i-th -diagram of the list is used as initial estimate) or as a diagram. -If None, it will randomly select one of the diagram of the list -as initial estimate. -Note that persistence diagrams must be submitted as -(n x 2) numpy arrays and must not contain inf values. - -.. testcode:: - - import gudhi.barycenter - import numpy as np - - dg1 = np.array([[0.2, 0.5]]) - dg2 = np.array([[0.2, 0.7]]) - dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) - dg4 = np.array([]) - pdiagset = [dg1, dg2, dg3, dg4] - bary = gudhi.barycenter.lagrangian_barycenter(pdiagset=pdiagset,init=3) - - message = "Wasserstein barycenter estimated:" - print(message) - print(bary) - -The output is: - -.. testoutput:: - - Wasserstein barycenter estimated: - [[0.27916667 0.55416667] - [0.7375 0.7625 ] - [0.2375 0.2625 ]] - - -- cgit v1.2.3 From 9f55afbb17494c67709d9be58bf8bb876f704524 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 11:24:21 +0200 Subject: added import barycenter on top of the file so that we can call for gudhi.wasserstein.barycenter --- src/python/gudhi/wasserstein.py | 1 + 1 file changed, 1 insertion(+) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 3dd993f9..8f03039b 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -9,6 +9,7 @@ import numpy as np import scipy.spatial.distance as sc +import barycenter try: import ot except ImportError: -- cgit v1.2.3 From 7721ac6181fc394ae0136ee176d63210e727f06f Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 11:40:46 +0200 Subject: modified import in test to get consistent with gudhi.wasserstein.barycenter --- src/python/test/test_wasserstein_barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index 4d18616b..f686aef5 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -1,4 +1,4 @@ -from gudhi.barycenter import lagrangian_barycenter +from gudhi.wasserstein.barycenter import lagrangian_barycenter import numpy as np """ This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. -- cgit v1.2.3 From eeeac06a05ee99ae5780b3f37f107680a680985a Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 11:54:06 +0200 Subject: removed unused import --- src/python/gudhi/barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py index 0490fdd1..079bcc57 100644 --- a/src/python/gudhi/barycenter.py +++ b/src/python/gudhi/barycenter.py @@ -12,7 +12,7 @@ import ot import numpy as np import scipy.spatial.distance as sc -from gudhi.wasserstein import wasserstein_distance, _perstot +from gudhi.wasserstein import wasserstein_distance def _mean(x, m): -- cgit v1.2.3 From dae83f0907a5bd94cb483ad0f54755da2d49fb75 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 12:49:22 +0200 Subject: changed into import .barycenter for local import in wasserstein, and modified index to remove barycenter doc --- src/python/doc/index.rst | 4 ---- src/python/gudhi/wasserstein.py | 2 +- 2 files changed, 1 insertion(+), 5 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst index 96cd3513..0e484483 100644 --- a/src/python/doc/index.rst +++ b/src/python/doc/index.rst @@ -71,10 +71,6 @@ Wasserstein distance .. include:: wasserstein_distance_sum.inc -Barycenter -============ - -.. include:: barycenter_sum.inc Persistence representations =========================== diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py index 8f03039b..760eea8c 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -9,7 +9,7 @@ import numpy as np import scipy.spatial.distance as sc -import barycenter +import .barycenter try: import ot except ImportError: -- cgit v1.2.3 From a924e71d2f1a649ca389cfeceb678cc45aaf9fa7 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 12:55:51 +0200 Subject: micro modif changed a word to avoid repetition --- src/python/doc/wasserstein_distance_user.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 6de05afc..a077f9a4 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -112,7 +112,7 @@ to the Lloyd algorithm to estimate a solution to the k-means problem). The local minimum returned depends on the initialization of the barycenter. The combinatorial structure of the algorithm limits its -scaling on large scale problems (thousands of diagrams and of points +performances on large scale problems (thousands of diagrams and of points per diagram). .. figure:: -- cgit v1.2.3 From 1aaffd2e1fab45988d92f5e51a9d294696ff5492 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 13:18:42 +0200 Subject: changed import to import gudhi.barycenter as barycenter --- 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 760eea8c..51d1d83c 100644 --- a/src/python/gudhi/wasserstein.py +++ b/src/python/gudhi/wasserstein.py @@ -9,7 +9,7 @@ import numpy as np import scipy.spatial.distance as sc -import .barycenter +import gudhi.barycenter as barycenter try: import ot except ImportError: -- cgit v1.2.3 From 842475615841f864b4ce41a2a4b69f1e189a2946 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 15:02:32 +0200 Subject: created wasserstein repo --- src/python/gudhi/barycenter.py | 158 ---------------------------- src/python/gudhi/wasserstein.py | 125 ---------------------- src/python/gudhi/wasserstein/__init__.py | 1 + src/python/gudhi/wasserstein/barycenter.py | 158 ++++++++++++++++++++++++++++ src/python/gudhi/wasserstein/wasserstein.py | 125 ++++++++++++++++++++++ 5 files changed, 284 insertions(+), 283 deletions(-) delete mode 100644 src/python/gudhi/barycenter.py delete mode 100644 src/python/gudhi/wasserstein.py create mode 100644 src/python/gudhi/wasserstein/__init__.py create mode 100644 src/python/gudhi/wasserstein/barycenter.py create mode 100644 src/python/gudhi/wasserstein/wasserstein.py (limited to 'src/python') diff --git a/src/python/gudhi/barycenter.py b/src/python/gudhi/barycenter.py deleted file mode 100644 index 079bcc57..00000000 --- a/src/python/gudhi/barycenter.py +++ /dev/null @@ -1,158 +0,0 @@ -# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. -# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. -# Author(s): Theo Lacombe -# -# Copyright (C) 2019 Inria -# -# Modification(s): -# - YYYY/MM Author: Description of the modification - - -import ot -import numpy as np -import scipy.spatial.distance as sc - -from gudhi.wasserstein import wasserstein_distance - - -def _mean(x, m): - ''' - :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} - :param m: total amount of points taken into account, - that is we have (m-k) copies of diagonal - :returns: the weighted mean of x with (m-k) copies of the diagonal - ''' - k = len(x) - if k > 0: - w = np.mean(x, axis=0) - w_delta = (w[0] + w[1]) / 2 * np.ones(2) - return (k * w + (m-k) * w_delta) / m - else: - return np.array([0, 0]) - - -def lagrangian_barycenter(pdiagset, init=None, verbose=False): - ''' - :param pdiagset: a list of size m containing numpy.array of shape (n x 2) - (n can variate), encoding a set of - persistence diagrams with only finite coordinates. - :param init: The initial value for barycenter estimate. - If None, init is made on a random diagram from the dataset. - Otherwise, it must be an int - (then we init with diagset[init]) - or a (n x 2) numpy.array enconding - a persistence diagram with n points. - :param verbose: if True, returns additional information about the - barycenter. - :returns: If not verbose (default), a numpy.array encoding - the barycenter estimate of pdiagset - (local minima of the energy function). - If pdiagset is empty, returns None. - If verbose, returns a couple (Y, log) - where Y is the barycenter estimate, - and log is a dict that contains additional informations: - - groupings, a list of list of pairs (i,j), - That is, G[k] = [(i, j) ...], where (i,j) indicates - that X[i] is matched to Y[j] - if i = -1 or j = -1, it means they - represent the diagonal. - - energy, a float representing the Frechet - energy value obtained, - that is the mean of squared distances - of observations to the output. - - nb_iter, integer representing the number of iterations - performed before convergence of the algorithm. - ''' - X = pdiagset # to shorten notations, not a copy - m = len(X) # number of diagrams we are averaging - if m == 0: - print("Warning: computing barycenter of empty diag set. Returns None") - return None - - # store the number of off-diagonal point for each of the X_i - nb_off_diag = np.array([len(X_i) for X_i in X]) - # Initialisation of barycenter - if init is None: - i0 = np.random.randint(m) # Index of first state for the barycenter - Y = X[i0].copy() - else: - if type(init)==int: - Y = X[init].copy() - else: - Y = init.copy() - - nb_iter = 0 - - converged = False # stoping criterion - while not converged: - nb_iter += 1 - K = len(Y) # current nb of points in Y (some might be on diagonal) - G = np.full((K, m), -1, dtype=int) # will store for each j, the (index) - # point matched in each other diagram - #(might be the diagonal). - # that is G[j, i] = k <=> y_j is matched to - # x_k in the diagram i-th diagram X[i] - updated_points = np.zeros((K, 2)) # will store the new positions of - # the points of Y. - # If points disappear, there thrown - # on [0,0] by default. - new_created_points = [] # will store potential new points. - - # Step 1 : compute optimal matching (Y, X_i) for each X_i - # and create new points in Y if needed - for i in range(m): - _, indices = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) - for y_j, x_i_j in indices: - if y_j >= 0: # we matched an off diagonal point to x_i_j... - if x_i_j >= 0: # ...which is also an off-diagonal point. - G[y_j, i] = x_i_j - else: # ...which is a diagonal point - G[y_j, i] = -1 # -1 stands for the diagonal (mask) - else: # We matched a diagonal point to x_i_j... - if x_i_j >= 0: # which is a off-diag point ! - # need to create new point in Y - new_y = _mean(np.array([X[i][x_i_j]]), m) - # Average this point with (m-1) copies of Delta - new_created_points.append(new_y) - - # Step 2 : Update current point position thanks to groupings computed - to_delete = [] - for j in range(K): - matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] - new_y_j = _mean(matched_points, m) - if not np.array_equal(new_y_j, np.array([0,0])): - updated_points[j] = new_y_j - else: # this points is no longer of any use. - to_delete.append(j) - # we remove the point to be deleted now. - updated_points = np.delete(updated_points, to_delete, axis=0) - - # we cannot converge if there have been new created points. - if new_created_points: - Y = np.concatenate((updated_points, new_created_points)) - else: - # Step 3 : we check convergence - if np.array_equal(updated_points, Y): - converged = True - Y = updated_points - - - if verbose: - groupings = [] - energy = 0 - log = {} - n_y = len(Y) - for i in range(m): - cost, edges = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) - groupings.append(edges) - energy += cost - log["groupings"] = groupings - energy = energy/m - print(energy) - log["energy"] = energy - log["nb_iter"] = nb_iter - - return Y, log - else: - return Y - diff --git a/src/python/gudhi/wasserstein.py b/src/python/gudhi/wasserstein.py deleted file mode 100644 index 51d1d83c..00000000 --- a/src/python/gudhi/wasserstein.py +++ /dev/null @@ -1,125 +0,0 @@ -# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. -# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. -# Author(s): Theo Lacombe -# -# Copyright (C) 2019 Inria -# -# Modification(s): -# - YYYY/MM Author: Description of the modification - -import numpy as np -import scipy.spatial.distance as sc -import gudhi.barycenter as barycenter -try: - import ot -except ImportError: - print("POT (Python Optimal Transport) package is not installed. Try to run $ conda install -c conda-forge pot ; or $ pip install POT") - -def _proj_on_diag(X): - ''' - :param X: (n x 2) array encoding the points of a persistent diagram. - :returns: (n x 2) array encoding the (respective orthogonal) projections of the points onto the diagonal - ''' - Z = (X[:,0] + X[:,1]) / 2. - return np.array([Z , Z]).T - - -def _build_dist_matrix(X, Y, order=2., internal_p=2.): - ''' - :param X: (n x 2) numpy.array encoding the (points of the) first diagram. - :param Y: (m x 2) numpy.array encoding the second diagram. - :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 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 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) - Ydiag = _proj_on_diag(Y) - if np.isinf(internal_p): - C = sc.cdist(X,Y, metric='chebyshev')**order - Cxd = np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order - Cdy = np.linalg.norm(Y - Ydiag, ord=internal_p, axis=1)**order - else: - C = sc.cdist(X,Y, metric='minkowski', p=internal_p)**order - Cxd = np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order - Cdy = np.linalg.norm(Y - Ydiag, ord=internal_p, axis=1)**order - Cf = np.hstack((C, Cxd[:,None])) - Cdy = np.append(Cdy, 0) - - Cf = np.vstack((Cf, Cdy[None,:])) - - return Cf - - -def _perstot(X, order, internal_p): - ''' - :param X: (n x 2) numpy.array (points of a given diagram). - :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: float, the total persistence of the diagram (that is, its distance to the empty diagram). - ''' - Xdiag = _proj_on_diag(X) - return (np.sum(np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order))**(1./order) - - -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 (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). - :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) - - # handle empty diagrams - if X.size == 0: - if Y.size == 0: - if not matching: - return 0. - else: - return 0., np.array([]) - else: - if not matching: - return _perstot(Y, order, internal_p) - else: - 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), 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. - 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[-1, -1] = 0 # Remove matching corresponding to the diagonal - match = np.argwhere(P) - # Now we turn to -1 points encoding the diagonal - 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. - # 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 = ot.emd2(a, b, M, numItermax=2000000) - - return ot_cost ** (1./order) diff --git a/src/python/gudhi/wasserstein/__init__.py b/src/python/gudhi/wasserstein/__init__.py new file mode 100644 index 00000000..ed225ba4 --- /dev/null +++ b/src/python/gudhi/wasserstein/__init__.py @@ -0,0 +1 @@ +from .wasserstein import wasserstein_distance diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py new file mode 100644 index 00000000..079bcc57 --- /dev/null +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -0,0 +1,158 @@ +# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. +# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. +# Author(s): Theo Lacombe +# +# Copyright (C) 2019 Inria +# +# Modification(s): +# - YYYY/MM Author: Description of the modification + + +import ot +import numpy as np +import scipy.spatial.distance as sc + +from gudhi.wasserstein import wasserstein_distance + + +def _mean(x, m): + ''' + :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} + :param m: total amount of points taken into account, + that is we have (m-k) copies of diagonal + :returns: the weighted mean of x with (m-k) copies of the diagonal + ''' + k = len(x) + if k > 0: + w = np.mean(x, axis=0) + w_delta = (w[0] + w[1]) / 2 * np.ones(2) + return (k * w + (m-k) * w_delta) / m + else: + return np.array([0, 0]) + + +def lagrangian_barycenter(pdiagset, init=None, verbose=False): + ''' + :param pdiagset: a list of size m containing numpy.array of shape (n x 2) + (n can variate), encoding a set of + persistence diagrams with only finite coordinates. + :param init: The initial value for barycenter estimate. + If None, init is made on a random diagram from the dataset. + Otherwise, it must be an int + (then we init with diagset[init]) + or a (n x 2) numpy.array enconding + a persistence diagram with n points. + :param verbose: if True, returns additional information about the + barycenter. + :returns: If not verbose (default), a numpy.array encoding + the barycenter estimate of pdiagset + (local minima of the energy function). + If pdiagset is empty, returns None. + If verbose, returns a couple (Y, log) + where Y is the barycenter estimate, + and log is a dict that contains additional informations: + - groupings, a list of list of pairs (i,j), + That is, G[k] = [(i, j) ...], where (i,j) indicates + that X[i] is matched to Y[j] + if i = -1 or j = -1, it means they + represent the diagonal. + - energy, a float representing the Frechet + energy value obtained, + that is the mean of squared distances + of observations to the output. + - nb_iter, integer representing the number of iterations + performed before convergence of the algorithm. + ''' + X = pdiagset # to shorten notations, not a copy + m = len(X) # number of diagrams we are averaging + if m == 0: + print("Warning: computing barycenter of empty diag set. Returns None") + return None + + # store the number of off-diagonal point for each of the X_i + nb_off_diag = np.array([len(X_i) for X_i in X]) + # Initialisation of barycenter + if init is None: + i0 = np.random.randint(m) # Index of first state for the barycenter + Y = X[i0].copy() + else: + if type(init)==int: + Y = X[init].copy() + else: + Y = init.copy() + + nb_iter = 0 + + converged = False # stoping criterion + while not converged: + nb_iter += 1 + K = len(Y) # current nb of points in Y (some might be on diagonal) + G = np.full((K, m), -1, dtype=int) # will store for each j, the (index) + # point matched in each other diagram + #(might be the diagonal). + # that is G[j, i] = k <=> y_j is matched to + # x_k in the diagram i-th diagram X[i] + updated_points = np.zeros((K, 2)) # will store the new positions of + # the points of Y. + # If points disappear, there thrown + # on [0,0] by default. + new_created_points = [] # will store potential new points. + + # Step 1 : compute optimal matching (Y, X_i) for each X_i + # and create new points in Y if needed + for i in range(m): + _, indices = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) + for y_j, x_i_j in indices: + if y_j >= 0: # we matched an off diagonal point to x_i_j... + if x_i_j >= 0: # ...which is also an off-diagonal point. + G[y_j, i] = x_i_j + else: # ...which is a diagonal point + G[y_j, i] = -1 # -1 stands for the diagonal (mask) + else: # We matched a diagonal point to x_i_j... + if x_i_j >= 0: # which is a off-diag point ! + # need to create new point in Y + new_y = _mean(np.array([X[i][x_i_j]]), m) + # Average this point with (m-1) copies of Delta + new_created_points.append(new_y) + + # Step 2 : Update current point position thanks to groupings computed + to_delete = [] + for j in range(K): + matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] + new_y_j = _mean(matched_points, m) + if not np.array_equal(new_y_j, np.array([0,0])): + updated_points[j] = new_y_j + else: # this points is no longer of any use. + to_delete.append(j) + # we remove the point to be deleted now. + updated_points = np.delete(updated_points, to_delete, axis=0) + + # we cannot converge if there have been new created points. + if new_created_points: + Y = np.concatenate((updated_points, new_created_points)) + else: + # Step 3 : we check convergence + if np.array_equal(updated_points, Y): + converged = True + Y = updated_points + + + if verbose: + groupings = [] + energy = 0 + log = {} + n_y = len(Y) + for i in range(m): + cost, edges = wasserstein_distance(Y, X[i], matching=True, order=2., internal_p=2.) + groupings.append(edges) + energy += cost + log["groupings"] = groupings + energy = energy/m + print(energy) + log["energy"] = energy + log["nb_iter"] = nb_iter + + return Y, log + else: + return Y + diff --git a/src/python/gudhi/wasserstein/wasserstein.py b/src/python/gudhi/wasserstein/wasserstein.py new file mode 100644 index 00000000..e1233eec --- /dev/null +++ b/src/python/gudhi/wasserstein/wasserstein.py @@ -0,0 +1,125 @@ +# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. +# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. +# Author(s): Theo Lacombe +# +# Copyright (C) 2019 Inria +# +# Modification(s): +# - YYYY/MM Author: Description of the modification + +import numpy as np +import scipy.spatial.distance as sc + +try: + import ot +except ImportError: + print("POT (Python Optimal Transport) package is not installed. Try to run $ conda install -c conda-forge pot ; or $ pip install POT") + +def _proj_on_diag(X): + ''' + :param X: (n x 2) array encoding the points of a persistent diagram. + :returns: (n x 2) array encoding the (respective orthogonal) projections of the points onto the diagonal + ''' + Z = (X[:,0] + X[:,1]) / 2. + return np.array([Z , Z]).T + + +def _build_dist_matrix(X, Y, order=2., internal_p=2.): + ''' + :param X: (n x 2) numpy.array encoding the (points of the) first diagram. + :param Y: (m x 2) numpy.array encoding the second diagram. + :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 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 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) + Ydiag = _proj_on_diag(Y) + if np.isinf(internal_p): + C = sc.cdist(X,Y, metric='chebyshev')**order + Cxd = np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order + Cdy = np.linalg.norm(Y - Ydiag, ord=internal_p, axis=1)**order + else: + C = sc.cdist(X,Y, metric='minkowski', p=internal_p)**order + Cxd = np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order + Cdy = np.linalg.norm(Y - Ydiag, ord=internal_p, axis=1)**order + Cf = np.hstack((C, Cxd[:,None])) + Cdy = np.append(Cdy, 0) + + Cf = np.vstack((Cf, Cdy[None,:])) + + return Cf + + +def _perstot(X, order, internal_p): + ''' + :param X: (n x 2) numpy.array (points of a given diagram). + :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: float, the total persistence of the diagram (that is, its distance to the empty diagram). + ''' + Xdiag = _proj_on_diag(X) + return (np.sum(np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order))**(1./order) + + +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 (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). + :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) + + # handle empty diagrams + if X.size == 0: + if Y.size == 0: + if not matching: + return 0. + else: + return 0., np.array([]) + else: + if not matching: + return _perstot(Y, order, internal_p) + else: + 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), 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. + 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[-1, -1] = 0 # Remove matching corresponding to the diagonal + match = np.argwhere(P) + # Now we turn to -1 points encoding the diagonal + 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. + # 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 = ot.emd2(a, b, M, numItermax=2000000) + + return ot_cost ** (1./order) -- cgit v1.2.3 From 266f1eb706ecf31733acbcdded3b04d8d270fb60 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 17:43:53 +0200 Subject: update CMakeLists to make things compatible with wasserstein/ repo --- src/python/CMakeLists.txt | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'src/python') diff --git a/src/python/CMakeLists.txt b/src/python/CMakeLists.txt index b7d43bea..a91ca30a 100644 --- a/src/python/CMakeLists.txt +++ b/src/python/CMakeLists.txt @@ -56,7 +56,6 @@ if(PYTHONINTERP_FOUND) # Modules that should not be auto-imported in __init__.py set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'representations', ") set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'wasserstein', ") - set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'barycenter', ") set(GUDHI_PYTHON_MODULES_EXTRA "${GUDHI_PYTHON_MODULES_EXTRA}'point_cloud', ") add_gudhi_debug_info("Python version ${PYTHON_VERSION_STRING}") @@ -217,8 +216,7 @@ if(PYTHONINTERP_FOUND) # Other .py files file(COPY "gudhi/persistence_graphical_tools.py" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") file(COPY "gudhi/representations" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi/") - file(COPY "gudhi/wasserstein.py" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") - file(COPY "gudhi/barycenter.py" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") + file(COPY "gudhi/wasserstein" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") file(COPY "gudhi/point_cloud" DESTINATION "${CMAKE_CURRENT_BINARY_DIR}/gudhi") add_custom_command( -- cgit v1.2.3 From af76331b5b4c709f46a3d705320bfedcf3a60924 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Tue, 31 Mar 2020 18:08:05 +0200 Subject: correction typo user.rst --- src/python/doc/wasserstein_distance_user.rst | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index a077f9a4..c6d49db1 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -128,7 +128,7 @@ per diagram). Basic example ------------- -This example computes the Frechet mean (aka Wasserstein barycenter) between +This example estimates the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. It is initialized on the 4th diagram. As the algorithm is not convex, its output depends on the initialization and @@ -143,7 +143,7 @@ Note that persistence diagrams must be submitted as .. testcode:: - import gudhi.barycenter + from gudhi.wasserstein.barycenter import lagrangian_barycenter import numpy as np dg1 = np.array([[0.2, 0.5]]) @@ -151,7 +151,7 @@ Note that persistence diagrams must be submitted as dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) dg4 = np.array([]) pdiagset = [dg1, dg2, dg3, dg4] - bary = gudhi.wasserstein.barycenter.lagrangian_barycenter(pdiagset=pdiagset,init=3) + bary = lagrangian_barycenter(pdiagset=pdiagset,init=3) message = "Wasserstein barycenter estimated:" print(message) -- cgit v1.2.3 From cfcbe923f132a770363e6a240df8f6911cdd39e9 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Wed, 1 Apr 2020 10:34:48 +0200 Subject: improved doc, turns Basic examples as subsections using * --- src/python/doc/wasserstein_distance_sum.inc | 6 +++--- src/python/doc/wasserstein_distance_user.rst | 10 +++++----- 2 files changed, 8 insertions(+), 8 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_sum.inc b/src/python/doc/wasserstein_distance_sum.inc index f10472bc..f9308e5e 100644 --- a/src/python/doc/wasserstein_distance_sum.inc +++ b/src/python/doc/wasserstein_distance_sum.inc @@ -4,10 +4,10 @@ +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ | .. figure:: | The q-Wasserstein distance measures the similarity between two | :Author: Theo Lacombe | | ../../doc/Bottleneck_distance/perturb_pd.png | persistence diagrams using the sum of all edges lengths (instead of | | - | :figclass: align-center | the maximum). It allows to define sophisticated objects such as | :Introduced in: GUDHI 3.1.0 | + | :figclass: align-center | the maximum). It allows to define sophisticated objects such as | :Since: GUDHI 3.1.0 | | | barycenters of a family of persistence diagrams. | | - | Wasserstein distance is the q-th root of the sum of the | | :Copyright: MIT | - | edge lengths to the power q. | | | + | | | :License: MIT | + | | | | | | | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ | * :doc:`wasserstein_distance_user` | | diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index c6d49db1..c5c250b5 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -9,7 +9,7 @@ Definition .. include:: wasserstein_distance_sum.inc -The q-Wasserstein distance is defined as the minimal value +The q-Wasserstein distance is defined as the minimal value achieved by a perfect matching between the points of the two diagrams (+ all diagonal points), where the value of a matching is defined as the q-th root of the sum of all edge lengths to the power q. Edge lengths @@ -32,7 +32,7 @@ Morozov, and Arnur Nigmetov. .. autofunction:: gudhi.hera.wasserstein_distance Basic example -------------- +************* This example computes the 1-Wasserstein distance from 2 persistence diagrams with Euclidean ground metric. Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. @@ -123,10 +123,10 @@ per diagram). diagrams. -.. autofunction:: gudhi.barycenter.lagrangian_barycenter +.. autofunction:: gudhi.wasserstein.barycenter.lagrangian_barycenter Basic example -------------- +************* This example estimates the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. @@ -135,7 +135,7 @@ As the algorithm is not convex, its output depends on the initialization and is only a local minimum of the objective function. Initialization can be either given as an integer (in which case the i-th diagram of the list is used as initial estimate) or as a diagram. -If None, it will randomly select one of the diagram of the list +If None, it will randomly select one of the diagrams of the list as initial estimate. Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. -- cgit v1.2.3 From c36080ab9e478cd0d44bfd8d5bb8f4726a8aa937 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Wed, 1 Apr 2020 20:24:01 +0200 Subject: improved doc readability --- src/python/gudhi/wasserstein/barycenter.py | 54 ++++++++++++++++-------------- 1 file changed, 28 insertions(+), 26 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index 079bcc57..fae6b68f 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -33,35 +33,37 @@ def _mean(x, m): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' - :param pdiagset: a list of size m containing numpy.array of shape (n x 2) - (n can variate), encoding a set of + :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` + (`n` can variate), encoding a set of persistence diagrams with only finite coordinates. :param init: The initial value for barycenter estimate. - If None, init is made on a random diagram from the dataset. - Otherwise, it must be an int - (then we init with diagset[init]) - or a (n x 2) numpy.array enconding - a persistence diagram with n points. - :param verbose: if True, returns additional information about the + If ``None``, init is made on a random diagram from the dataset. + Otherwise, it can be an ``int`` + (then initialization is made on ``pdiagset[init]``) + or a `(n x 2)` ``numpy.array`` enconding + a persistence diagram with `n` points. + :type init: int, (n x 2) np.array + :param verbose: if ``True``, returns additional information about the barycenter. - :returns: If not verbose (default), a numpy.array encoding - the barycenter estimate of pdiagset - (local minima of the energy function). - If pdiagset is empty, returns None. - If verbose, returns a couple (Y, log) - where Y is the barycenter estimate, - and log is a dict that contains additional informations: - - groupings, a list of list of pairs (i,j), - That is, G[k] = [(i, j) ...], where (i,j) indicates - that X[i] is matched to Y[j] - if i = -1 or j = -1, it means they - represent the diagonal. - - energy, a float representing the Frechet - energy value obtained, - that is the mean of squared distances - of observations to the output. - - nb_iter, integer representing the number of iterations - performed before convergence of the algorithm. + :type verbose: boolean + :returns: If not verbose (default), a ``numpy.array`` encoding + the barycenter estimate of pdiagset + (local minimum of the energy function). + If ``pdiagset`` is empty, returns ``None``. + If verbose, returns a couple ``(Y, log)`` + where ``Y`` is the barycenter estimate, + and ``log`` is a ``dict`` that contains additional informations: + + - `"groupings"`, a list of list of pairs ``(i,j)``. + Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates + that ``pdiagset[k][i]`` is matched to ``Y[j]`` + if ``i = -1`` or ``j = -1``, it means they + represent the diagonal. + + - `"energy"`, ``float`` representing the Frechet energy value obtained. + It is the mean of squared distances of observations to the output. + + - `"nb_iter"`, ``int`` number of iterations performed before convergence of the algorithm. ''' X = pdiagset # to shorten notations, not a copy m = len(X) # number of diagrams we are averaging -- cgit v1.2.3 From 731358cbfe3880b02a58c70923b5a990ddff7644 Mon Sep 17 00:00:00 2001 From: tlacombe Date: Wed, 1 Apr 2020 20:27:27 +0200 Subject: improved doc, adding double quot for init --- src/python/gudhi/wasserstein/barycenter.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index fae6b68f..e879b7dd 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -42,7 +42,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): (then initialization is made on ``pdiagset[init]``) or a `(n x 2)` ``numpy.array`` enconding a persistence diagram with `n` points. - :type init: int, (n x 2) np.array + :type init: ``int``, or (n x 2) ``np.array`` :param verbose: if ``True``, returns additional information about the barycenter. :type verbose: boolean -- cgit v1.2.3 From 4cfe8411f808f52bee0ba37e28fa9f6cc3519abb Mon Sep 17 00:00:00 2001 From: tlacombe Date: Fri, 3 Apr 2020 17:27:47 +0200 Subject: removed the print of energy in verbose mode, added by error --- src/python/gudhi/wasserstein/barycenter.py | 1 - 1 file changed, 1 deletion(-) (limited to 'src/python') diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index e879b7dd..99f29a1e 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -150,7 +150,6 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): energy += cost log["groupings"] = groupings energy = energy/m - print(energy) log["energy"] = energy log["nb_iter"] = nb_iter -- cgit v1.2.3 From f0224ea1c97c7dcb32debeda176139ba10bd21e7 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 4 Apr 2020 05:39:19 +0200 Subject: Local bibliographies in sphinx --- src/python/doc/alpha_complex_user.rst | 2 +- src/python/doc/bottleneck_distance_user.rst | 7 +++++++ src/python/doc/cubical_complex_user.rst | 2 +- src/python/doc/index.rst | 2 +- src/python/doc/nerve_gic_complex_user.rst | 7 +++++++ src/python/doc/persistent_cohomology_user.rst | 2 +- src/python/doc/rips_complex_user.rst | 7 +++++++ src/python/doc/simplex_tree_user.rst | 7 +++++++ src/python/doc/tangential_complex_user.rst | 2 +- src/python/doc/wasserstein_distance_user.rst | 7 +++++++ src/python/doc/witness_complex_user.rst | 2 +- 11 files changed, 41 insertions(+), 6 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index 60319e84..6e926fc8 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -207,5 +207,5 @@ CGAL citations ============== .. bibliography:: ../../biblio/how_to_cite_cgal.bib - :filter: docnames + :filter: docname in docnames :style: unsrt diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 9435c7f1..95c4e575 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -65,3 +65,10 @@ The output is: Bottleneck distance approximation = 0.81 Bottleneck distance value = 0.75 + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docname in docnames + :style: unsrt diff --git a/src/python/doc/cubical_complex_user.rst b/src/python/doc/cubical_complex_user.rst index 93ca6b24..94f59954 100644 --- a/src/python/doc/cubical_complex_user.rst +++ b/src/python/doc/cubical_complex_user.rst @@ -163,5 +163,5 @@ Bibliography ============ .. bibliography:: ../../biblio/bibliography.bib - :filter: docnames + :filter: docname in docnames :style: unsrt diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst index 3387a64f..df1dff68 100644 --- a/src/python/doc/index.rst +++ b/src/python/doc/index.rst @@ -90,5 +90,5 @@ Bibliography ************ .. bibliography:: ../../biblio/bibliography.bib - :filter: docnames + :filter: docname in docnames :style: unsrt diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst index 9101f45d..208031fb 100644 --- a/src/python/doc/nerve_gic_complex_user.rst +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -313,3 +313,10 @@ the program outputs again SC.dot which gives the following visualization after u :alt: Visualization with neato Visualization with neato + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docname in docnames + :style: unsrt diff --git a/src/python/doc/persistent_cohomology_user.rst b/src/python/doc/persistent_cohomology_user.rst index 5f931b3a..0a5be3a9 100644 --- a/src/python/doc/persistent_cohomology_user.rst +++ b/src/python/doc/persistent_cohomology_user.rst @@ -116,5 +116,5 @@ Bibliography ============ .. bibliography:: ../../biblio/bibliography.bib - :filter: docnames + :filter: docname in docnames :style: unsrt diff --git a/src/python/doc/rips_complex_user.rst b/src/python/doc/rips_complex_user.rst index 8efb12e6..325added 100644 --- a/src/python/doc/rips_complex_user.rst +++ b/src/python/doc/rips_complex_user.rst @@ -347,3 +347,10 @@ until dimension 1 - one skeleton graph in other words), the output is: points in the persistence diagram will be under the diagonal, and bottleneck distance and persistence graphical tool will not work properly, this is a known issue. + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docname in docnames + :style: unsrt diff --git a/src/python/doc/simplex_tree_user.rst b/src/python/doc/simplex_tree_user.rst index 3df7617f..b0b7153e 100644 --- a/src/python/doc/simplex_tree_user.rst +++ b/src/python/doc/simplex_tree_user.rst @@ -66,3 +66,10 @@ The output is: ([1, 2], 4.0) ([1], 0.0) ([2], 4.0) + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docname in docnames + :style: unsrt diff --git a/src/python/doc/tangential_complex_user.rst b/src/python/doc/tangential_complex_user.rst index 852cf5b6..0bcbc848 100644 --- a/src/python/doc/tangential_complex_user.rst +++ b/src/python/doc/tangential_complex_user.rst @@ -200,5 +200,5 @@ Bibliography ============ .. bibliography:: ../../biblio/bibliography.bib - :filter: docnames + :filter: docname in docnames :style: unsrt diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index a9b21fa5..9b94573e 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -84,3 +84,10 @@ The output is: 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 + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docname in docnames + :style: unsrt diff --git a/src/python/doc/witness_complex_user.rst b/src/python/doc/witness_complex_user.rst index 7087fa98..b932ed0d 100644 --- a/src/python/doc/witness_complex_user.rst +++ b/src/python/doc/witness_complex_user.rst @@ -131,5 +131,5 @@ Bibliography ============ .. bibliography:: ../../biblio/bibliography.bib - :filter: docnames + :filter: docname in docnames :style: unsrt -- cgit v1.2.3 From d9e6b4f51bc8517453653be2904ab6db9aaab85e Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 4 Apr 2020 06:01:59 +0200 Subject: sphinx label warnings --- src/python/doc/alpha_complex_user.rst | 1 + src/python/doc/bottleneck_distance_user.rst | 1 + src/python/doc/cubical_complex_user.rst | 1 + src/python/doc/index.rst | 1 + src/python/doc/nerve_gic_complex_user.rst | 1 + src/python/doc/persistent_cohomology_user.rst | 1 + src/python/doc/rips_complex_user.rst | 1 + src/python/doc/simplex_tree_user.rst | 1 + src/python/doc/tangential_complex_user.rst | 1 + src/python/doc/wasserstein_distance_user.rst | 1 + src/python/doc/witness_complex_user.rst | 1 + 11 files changed, 11 insertions(+) (limited to 'src/python') diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index 6e926fc8..e1903688 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -209,3 +209,4 @@ CGAL citations .. bibliography:: ../../biblio/how_to_cite_cgal.bib :filter: docname in docnames :style: unsrt + :labelprefix: A diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 95c4e575..23a87c19 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -72,3 +72,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: B diff --git a/src/python/doc/cubical_complex_user.rst b/src/python/doc/cubical_complex_user.rst index 94f59954..cdc5b5dc 100644 --- a/src/python/doc/cubical_complex_user.rst +++ b/src/python/doc/cubical_complex_user.rst @@ -165,3 +165,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: CC diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst index df1dff68..089efe23 100644 --- a/src/python/doc/index.rst +++ b/src/python/doc/index.rst @@ -92,3 +92,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: I diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst index 208031fb..b022dca7 100644 --- a/src/python/doc/nerve_gic_complex_user.rst +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -320,3 +320,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: N diff --git a/src/python/doc/persistent_cohomology_user.rst b/src/python/doc/persistent_cohomology_user.rst index 0a5be3a9..f97fc759 100644 --- a/src/python/doc/persistent_cohomology_user.rst +++ b/src/python/doc/persistent_cohomology_user.rst @@ -118,3 +118,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: PC diff --git a/src/python/doc/rips_complex_user.rst b/src/python/doc/rips_complex_user.rst index 325added..fb6e4b1b 100644 --- a/src/python/doc/rips_complex_user.rst +++ b/src/python/doc/rips_complex_user.rst @@ -354,3 +354,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: R diff --git a/src/python/doc/simplex_tree_user.rst b/src/python/doc/simplex_tree_user.rst index b0b7153e..5a97b3d7 100644 --- a/src/python/doc/simplex_tree_user.rst +++ b/src/python/doc/simplex_tree_user.rst @@ -73,3 +73,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: ST diff --git a/src/python/doc/tangential_complex_user.rst b/src/python/doc/tangential_complex_user.rst index 0bcbc848..6cdd6125 100644 --- a/src/python/doc/tangential_complex_user.rst +++ b/src/python/doc/tangential_complex_user.rst @@ -202,3 +202,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: TA diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 9b94573e..817e6981 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -91,3 +91,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: WA diff --git a/src/python/doc/witness_complex_user.rst b/src/python/doc/witness_complex_user.rst index b932ed0d..c258ad38 100644 --- a/src/python/doc/witness_complex_user.rst +++ b/src/python/doc/witness_complex_user.rst @@ -133,3 +133,4 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt + :labelprefix: WI -- cgit v1.2.3 From dc80ab48359521dac415292f4d2b1f496f326263 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 4 Apr 2020 06:05:57 +0200 Subject: Revert "sphinx label warnings" This reverts commit d9e6b4f51bc8517453653be2904ab6db9aaab85e. It was able to remove the warnings about duplicate labels, but then it shows [WA1] instead of [1] in the generated doc. And for things cited on multiple pages, it uses the same everywhere, so on a single page, you can have a mix of [I1], [WI2], etc. Not very pretty. --- src/python/doc/alpha_complex_user.rst | 1 - src/python/doc/bottleneck_distance_user.rst | 1 - src/python/doc/cubical_complex_user.rst | 1 - src/python/doc/index.rst | 1 - src/python/doc/nerve_gic_complex_user.rst | 1 - src/python/doc/persistent_cohomology_user.rst | 1 - src/python/doc/rips_complex_user.rst | 1 - src/python/doc/simplex_tree_user.rst | 1 - src/python/doc/tangential_complex_user.rst | 1 - src/python/doc/wasserstein_distance_user.rst | 1 - src/python/doc/witness_complex_user.rst | 1 - 11 files changed, 11 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index e1903688..6e926fc8 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -209,4 +209,3 @@ CGAL citations .. bibliography:: ../../biblio/how_to_cite_cgal.bib :filter: docname in docnames :style: unsrt - :labelprefix: A diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 23a87c19..95c4e575 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -72,4 +72,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: B diff --git a/src/python/doc/cubical_complex_user.rst b/src/python/doc/cubical_complex_user.rst index cdc5b5dc..94f59954 100644 --- a/src/python/doc/cubical_complex_user.rst +++ b/src/python/doc/cubical_complex_user.rst @@ -165,4 +165,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: CC diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst index 089efe23..df1dff68 100644 --- a/src/python/doc/index.rst +++ b/src/python/doc/index.rst @@ -92,4 +92,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: I diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst index b022dca7..208031fb 100644 --- a/src/python/doc/nerve_gic_complex_user.rst +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -320,4 +320,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: N diff --git a/src/python/doc/persistent_cohomology_user.rst b/src/python/doc/persistent_cohomology_user.rst index f97fc759..0a5be3a9 100644 --- a/src/python/doc/persistent_cohomology_user.rst +++ b/src/python/doc/persistent_cohomology_user.rst @@ -118,4 +118,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: PC diff --git a/src/python/doc/rips_complex_user.rst b/src/python/doc/rips_complex_user.rst index fb6e4b1b..325added 100644 --- a/src/python/doc/rips_complex_user.rst +++ b/src/python/doc/rips_complex_user.rst @@ -354,4 +354,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: R diff --git a/src/python/doc/simplex_tree_user.rst b/src/python/doc/simplex_tree_user.rst index 5a97b3d7..b0b7153e 100644 --- a/src/python/doc/simplex_tree_user.rst +++ b/src/python/doc/simplex_tree_user.rst @@ -73,4 +73,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: ST diff --git a/src/python/doc/tangential_complex_user.rst b/src/python/doc/tangential_complex_user.rst index 6cdd6125..0bcbc848 100644 --- a/src/python/doc/tangential_complex_user.rst +++ b/src/python/doc/tangential_complex_user.rst @@ -202,4 +202,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: TA diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 817e6981..9b94573e 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -91,4 +91,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: WA diff --git a/src/python/doc/witness_complex_user.rst b/src/python/doc/witness_complex_user.rst index c258ad38..b932ed0d 100644 --- a/src/python/doc/witness_complex_user.rst +++ b/src/python/doc/witness_complex_user.rst @@ -133,4 +133,3 @@ Bibliography .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames :style: unsrt - :labelprefix: WI -- cgit v1.2.3 From da3b4a79ca40d08ae5597341f4db2418f20fe3d2 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 4 Apr 2020 12:52:52 +0200 Subject: Missing biblio in one file, change title level --- src/python/doc/alpha_complex_user.rst | 2 +- src/python/doc/bottleneck_distance_user.rst | 2 +- src/python/doc/cubical_complex_user.rst | 2 +- src/python/doc/nerve_gic_complex_ref.rst | 7 +++++++ src/python/doc/nerve_gic_complex_user.rst | 2 +- src/python/doc/persistent_cohomology_user.rst | 2 +- src/python/doc/rips_complex_user.rst | 2 +- src/python/doc/simplex_tree_user.rst | 2 +- src/python/doc/tangential_complex_user.rst | 2 +- src/python/doc/wasserstein_distance_user.rst | 2 +- src/python/doc/witness_complex_user.rst | 2 +- 11 files changed, 17 insertions(+), 10 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index 6e926fc8..265a82d2 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -204,7 +204,7 @@ the program output is: [3, 6] -> 30.25 CGAL citations -============== +-------------- .. bibliography:: ../../biblio/how_to_cite_cgal.bib :filter: docname in docnames diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 95c4e575..206fcb63 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -67,7 +67,7 @@ The output is: Bottleneck distance value = 0.75 Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/cubical_complex_user.rst b/src/python/doc/cubical_complex_user.rst index 94f59954..e8c94bf6 100644 --- a/src/python/doc/cubical_complex_user.rst +++ b/src/python/doc/cubical_complex_user.rst @@ -160,7 +160,7 @@ Examples. End user programs are available in python/example/ folder. Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/nerve_gic_complex_ref.rst b/src/python/doc/nerve_gic_complex_ref.rst index abde2e8c..6a81b7af 100644 --- a/src/python/doc/nerve_gic_complex_ref.rst +++ b/src/python/doc/nerve_gic_complex_ref.rst @@ -12,3 +12,10 @@ Cover complexes reference manual :show-inheritance: .. automethod:: gudhi.CoverComplex.__init__ + +Bibliography +------------ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docname in docnames + :style: unsrt diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst index 208031fb..f709ce91 100644 --- a/src/python/doc/nerve_gic_complex_user.rst +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -315,7 +315,7 @@ the program outputs again SC.dot which gives the following visualization after u Visualization with neato Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/persistent_cohomology_user.rst b/src/python/doc/persistent_cohomology_user.rst index 0a5be3a9..506fa3a7 100644 --- a/src/python/doc/persistent_cohomology_user.rst +++ b/src/python/doc/persistent_cohomology_user.rst @@ -113,7 +113,7 @@ We provide several example files: run these examples with -h for details on thei * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.py>` Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/rips_complex_user.rst b/src/python/doc/rips_complex_user.rst index 325added..c4bbcfb6 100644 --- a/src/python/doc/rips_complex_user.rst +++ b/src/python/doc/rips_complex_user.rst @@ -349,7 +349,7 @@ until dimension 1 - one skeleton graph in other words), the output is: this is a known issue. Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/simplex_tree_user.rst b/src/python/doc/simplex_tree_user.rst index b0b7153e..1b272c35 100644 --- a/src/python/doc/simplex_tree_user.rst +++ b/src/python/doc/simplex_tree_user.rst @@ -68,7 +68,7 @@ The output is: ([2], 4.0) Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/tangential_complex_user.rst b/src/python/doc/tangential_complex_user.rst index 0bcbc848..cf8199cc 100644 --- a/src/python/doc/tangential_complex_user.rst +++ b/src/python/doc/tangential_complex_user.rst @@ -197,7 +197,7 @@ The output is: Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 9b94573e..2ae72351 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -86,7 +86,7 @@ The output is: point 1 in dgm2 is matched to the diagonal Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames diff --git a/src/python/doc/witness_complex_user.rst b/src/python/doc/witness_complex_user.rst index b932ed0d..799f5444 100644 --- a/src/python/doc/witness_complex_user.rst +++ b/src/python/doc/witness_complex_user.rst @@ -128,7 +128,7 @@ Here is an example of constructing a strong witness complex filtration and compu * :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>` Bibliography -============ +------------ .. bibliography:: ../../biblio/bibliography.bib :filter: docname in docnames -- cgit v1.2.3 From dd96965e521313b6210391f511c82cced9b2a950 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 6 Apr 2020 19:37:58 +0200 Subject: Remove trailing whitespace --- src/python/doc/wasserstein_distance_user.rst | 72 +++++++++++++------------- src/python/gudhi/wasserstein/barycenter.py | 42 +++++++-------- src/python/gudhi/wasserstein/wasserstein.py | 14 ++--- src/python/test/test_wasserstein_barycenter.py | 6 +-- src/python/test/test_wasserstein_distance.py | 2 +- 5 files changed, 68 insertions(+), 68 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index b821b6fa..c24da74d 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -10,10 +10,10 @@ Definition .. include:: wasserstein_distance_sum.inc The q-Wasserstein distance is defined as the minimal value achieved -by a perfect matching between the points of the two diagrams (+ all -diagonal points), where the value of a matching is defined as the +by a perfect matching between the points of the two diagrams (+ all +diagonal points), where the value of a matching is defined as the q-th root of the sum of all edge lengths to the power q. Edge lengths -are measured in norm p, for :math:`1 \leq p \leq \infty`. +are measured in norm p, for :math:`1 \leq p \leq \infty`. Distance Functions ------------------ @@ -54,9 +54,9 @@ The output is: Wasserstein distance value = 1.45 -We can also have access to the optimal matching by letting `matching=True`. +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. +is mapped to the j-th point in Y. An index of -1 represents the diagonal. .. testcode:: @@ -84,7 +84,7 @@ An index of -1 represents the diagonal. The output is: .. testoutput:: - + 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 @@ -94,32 +94,32 @@ The output is: Barycenters ----------- -A Frechet mean (or barycenter) is a generalization of the arithmetic -mean in a non linear space such as the one of persistence diagrams. -Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is -defined as a minimizer of the variance functional, that is of -:math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. -where :math:`d_2` denotes the Wasserstein-2 distance between -persistence diagrams. -It is known to exist and is generically unique. However, an exact -computation is in general untractable. Current implementation -available is based on (Turner et al., 2014), +A Frechet mean (or barycenter) is a generalization of the arithmetic +mean in a non linear space such as the one of persistence diagrams. +Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is +defined as a minimizer of the variance functional, that is of +:math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. +where :math:`d_2` denotes the Wasserstein-2 distance between +persistence diagrams. +It is known to exist and is generically unique. However, an exact +computation is in general untractable. Current implementation +available is based on (Turner et al., 2014), :cite:`turner2014frechet` -and uses an EM-scheme to -provide a local minimum of the variance functional (somewhat similar -to the Lloyd algorithm to estimate a solution to the k-means +and uses an EM-scheme to +provide a local minimum of the variance functional (somewhat similar +to the Lloyd algorithm to estimate a solution to the k-means problem). The local minimum returned depends on the initialization of -the barycenter. -The combinatorial structure of the algorithm limits its -performances on large scale problems (thousands of diagrams and of points -per diagram). +the barycenter. +The combinatorial structure of the algorithm limits its +performances on large scale problems (thousands of diagrams and of points +per diagram). + +.. figure:: + ./img/barycenter.png + :figclass: align-center -.. figure:: - ./img/barycenter.png - :figclass: align-center - - Illustration of Frechet mean between persistence - diagrams. + Illustration of Frechet mean between persistence + diagrams. .. autofunction:: gudhi.wasserstein.barycenter.lagrangian_barycenter @@ -127,16 +127,16 @@ per diagram). Basic example ************* -This example estimates the Frechet mean (aka Wasserstein barycenter) between +This example estimates the Frechet mean (aka Wasserstein barycenter) between four persistence diagrams. It is initialized on the 4th diagram. -As the algorithm is not convex, its output depends on the initialization and +As the algorithm is not convex, its output depends on the initialization and is only a local minimum of the objective function. -Initialization can be either given as an integer (in which case the i-th -diagram of the list is used as initial estimate) or as a diagram. -If None, it will randomly select one of the diagrams of the list +Initialization can be either given as an integer (in which case the i-th +diagram of the list is used as initial estimate) or as a diagram. +If None, it will randomly select one of the diagrams of the list as initial estimate. -Note that persistence diagrams must be submitted as +Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. @@ -152,7 +152,7 @@ Note that persistence diagrams must be submitted as pdiagset = [dg1, dg2, dg3, dg4] bary = lagrangian_barycenter(pdiagset=pdiagset,init=3) - message = "Wasserstein barycenter estimated:" + message = "Wasserstein barycenter estimated:" print(message) print(bary) diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index 99f29a1e..de7aea81 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -18,7 +18,7 @@ from gudhi.wasserstein import wasserstein_distance def _mean(x, m): ''' :param x: a list of 2D-points, off diagonal, x_0... x_{k-1} - :param m: total amount of points taken into account, + :param m: total amount of points taken into account, that is we have (m-k) copies of diagonal :returns: the weighted mean of x with (m-k) copies of the diagonal ''' @@ -33,14 +33,14 @@ def _mean(x, m): def lagrangian_barycenter(pdiagset, init=None, verbose=False): ''' - :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` - (`n` can variate), encoding a set of - persistence diagrams with only finite coordinates. - :param init: The initial value for barycenter estimate. - If ``None``, init is made on a random diagram from the dataset. - Otherwise, it can be an ``int`` + :param pdiagset: a list of ``numpy.array`` of shape `(n x 2)` + (`n` can variate), encoding a set of + persistence diagrams with only finite coordinates. + :param init: The initial value for barycenter estimate. + If ``None``, init is made on a random diagram from the dataset. + Otherwise, it can be an ``int`` (then initialization is made on ``pdiagset[init]``) - or a `(n x 2)` ``numpy.array`` enconding + or a `(n x 2)` ``numpy.array`` enconding a persistence diagram with `n` points. :type init: ``int``, or (n x 2) ``np.array`` :param verbose: if ``True``, returns additional information about the @@ -48,16 +48,16 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): :type verbose: boolean :returns: If not verbose (default), a ``numpy.array`` encoding the barycenter estimate of pdiagset - (local minimum of the energy function). + (local minimum of the energy function). If ``pdiagset`` is empty, returns ``None``. If verbose, returns a couple ``(Y, log)`` where ``Y`` is the barycenter estimate, and ``log`` is a ``dict`` that contains additional informations: - `"groupings"`, a list of list of pairs ``(i,j)``. - Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates + Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that ``pdiagset[k][i]`` is matched to ``Y[j]`` - if ``i = -1`` or ``j = -1``, it means they + if ``i = -1`` or ``j = -1``, it means they represent the diagonal. - `"energy"`, ``float`` representing the Frechet energy value obtained. @@ -70,13 +70,13 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): if m == 0: print("Warning: computing barycenter of empty diag set. Returns None") return None - + # store the number of off-diagonal point for each of the X_i - nb_off_diag = np.array([len(X_i) for X_i in X]) + nb_off_diag = np.array([len(X_i) for X_i in X]) # Initialisation of barycenter if init is None: i0 = np.random.randint(m) # Index of first state for the barycenter - Y = X[i0].copy() + Y = X[i0].copy() else: if type(init)==int: Y = X[init].copy() @@ -90,8 +90,8 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): nb_iter += 1 K = len(Y) # current nb of points in Y (some might be on diagonal) G = np.full((K, m), -1, dtype=int) # will store for each j, the (index) - # point matched in each other diagram - #(might be the diagonal). + # point matched in each other diagram + #(might be the diagonal). # that is G[j, i] = k <=> y_j is matched to # x_k in the diagram i-th diagram X[i] updated_points = np.zeros((K, 2)) # will store the new positions of @@ -111,7 +111,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): else: # ...which is a diagonal point G[y_j, i] = -1 # -1 stands for the diagonal (mask) else: # We matched a diagonal point to x_i_j... - if x_i_j >= 0: # which is a off-diag point ! + if x_i_j >= 0: # which is a off-diag point ! # need to create new point in Y new_y = _mean(np.array([X[i][x_i_j]]), m) # Average this point with (m-1) copies of Delta @@ -123,19 +123,19 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): matched_points = [X[i][G[j, i]] for i in range(m) if G[j, i] > -1] new_y_j = _mean(matched_points, m) if not np.array_equal(new_y_j, np.array([0,0])): - updated_points[j] = new_y_j + updated_points[j] = new_y_j else: # this points is no longer of any use. to_delete.append(j) # we remove the point to be deleted now. - updated_points = np.delete(updated_points, to_delete, axis=0) + updated_points = np.delete(updated_points, to_delete, axis=0) # we cannot converge if there have been new created points. - if new_created_points: + if new_created_points: Y = np.concatenate((updated_points, new_created_points)) else: # Step 3 : we check convergence if np.array_equal(updated_points, Y): - converged = True + converged = True Y = updated_points diff --git a/src/python/gudhi/wasserstein/wasserstein.py b/src/python/gudhi/wasserstein/wasserstein.py index e1233eec..35315939 100644 --- a/src/python/gudhi/wasserstein/wasserstein.py +++ b/src/python/gudhi/wasserstein/wasserstein.py @@ -30,9 +30,9 @@ def _build_dist_matrix(X, Y, order=2., internal_p=2.): :param Y: (m x 2) numpy.array encoding the second diagram. :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 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]) + :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 projection onto the diagonal. note also that C[n, m] = 0 (it costs nothing to move from the diagonal to the diagonal). ''' @@ -59,7 +59,7 @@ def _perstot(X, order, internal_p): :param X: (n x 2) numpy.array (points of a given diagram). :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: float, the total persistence of the diagram (that is, its distance to the empty diagram). + :returns: float, the total persistence of the diagram (that is, its distance to the empty diagram). ''' Xdiag = _proj_on_diag(X) return (np.sum(np.linalg.norm(X - Xdiag, ord=internal_p, axis=1)**order))**(1./order) @@ -67,16 +67,16 @@ def _perstot(X, order, internal_p): 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 + :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 (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); + :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 + :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. ''' diff --git a/src/python/test/test_wasserstein_barycenter.py b/src/python/test/test_wasserstein_barycenter.py index f686aef5..f68c748e 100755 --- a/src/python/test/test_wasserstein_barycenter.py +++ b/src/python/test/test_wasserstein_barycenter.py @@ -17,7 +17,7 @@ __license__ = "MIT" def test_lagrangian_barycenter(): - + dg1 = np.array([[0.2, 0.5]]) dg2 = np.array([[0.2, 0.7]]) dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) @@ -28,12 +28,12 @@ def test_lagrangian_barycenter(): dg7 = np.array([[0.1, 0.15], [0.1, 0.7], [0.2, 0.22], [0.55, 0.84], [0.11, 0.91], [0.61, 0.75], [0.33, 0.46], [0.12, 0.41], [0.32, 0.48]]) dg8 = np.array([[0., 4.], [4, 8]]) - + # error crit. eps = 1e-7 - assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < eps + assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg1, dg2, dg3, dg4],init=3, verbose=False) - res) < eps assert np.array_equal(lagrangian_barycenter(pdiagset=[dg4, dg5, dg6], verbose=False), np.empty(shape=(0,2))) assert np.linalg.norm(lagrangian_barycenter(pdiagset=[dg7], verbose=False) - dg7) < eps Y, log = lagrangian_barycenter(pdiagset=[dg4, dg8], verbose=True) diff --git a/src/python/test/test_wasserstein_distance.py b/src/python/test/test_wasserstein_distance.py index 0d70e11a..7e0d0f5f 100755 --- a/src/python/test/test_wasserstein_distance.py +++ b/src/python/test/test_wasserstein_distance.py @@ -70,7 +70,7 @@ def _basic_wasserstein(wasserstein_distance, delta, test_infinity=True, test_mat 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, [[0, 0], [1, 1], [2, -1]]) - + def hera_wrap(delta): -- cgit v1.2.3 From 82dd4481fa0ecb8c1f696ee33e26d9be1e371e88 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 6 Apr 2020 22:46:32 +0200 Subject: Document dependencies for building the doc --- src/python/doc/installation.rst | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/python') diff --git a/src/python/doc/installation.rst b/src/python/doc/installation.rst index d459145b..48425d5e 100644 --- a/src/python/doc/installation.rst +++ b/src/python/doc/installation.rst @@ -175,8 +175,8 @@ Documentation To build the documentation, `sphinx-doc `_ and `sphinxcontrib-bibtex `_ are required. As the documentation is auto-tested, `CGAL`_, `Eigen`_, -`Matplotlib`_, `NumPy`_ and `SciPy`_ are also mandatory to build the -documentation. +`Matplotlib`_, `NumPy`_, `POT`_, `Scikit-learn`_ and `SciPy`_ are +also mandatory to build the documentation. Run the following commands in a terminal: @@ -192,8 +192,8 @@ CGAL ==== Some GUDHI modules (cf. :doc:`modules list `), and few examples -require CGAL, a C++ library that provides easy access to efficient and -reliable geometric algorithms. +require `CGAL `_, a C++ library that provides easy +access to efficient and reliable geometric algorithms. The procedure to install this library -- cgit v1.2.3