diff options
Diffstat (limited to 'src/Persistence_representations/include/gudhi')
10 files changed, 575 insertions, 176 deletions
diff --git a/src/Persistence_representations/include/gudhi/PSSK.h b/src/Persistence_representations/include/gudhi/PSSK.h index e2d4225e..630f5623 100644 --- a/src/Persistence_representations/include/gudhi/PSSK.h +++ b/src/Persistence_representations/include/gudhi/PSSK.h @@ -121,10 +121,10 @@ void PSSK::construct(const std::vector<std::pair<double, double> >& intervals_, for (size_t pt_nr = 0; pt_nr != intervals_.size(); ++pt_nr) { // compute the value of intervals_[pt_nr] in the grid: - int x_grid = static_cast<int>((intervals_[pt_nr].first - this->min_) / - (this->max_ - this->min_) * number_of_pixels); - int y_grid = static_cast<int>((intervals_[pt_nr].second - this->min_) / - (this->max_ - this->min_) * number_of_pixels); + int x_grid = + static_cast<int>((intervals_[pt_nr].first - this->min_) / (this->max_ - this->min_) * number_of_pixels); + int y_grid = + static_cast<int>((intervals_[pt_nr].second - this->min_) / (this->max_ - this->min_) * number_of_pixels); if (dbg) { std::cerr << "point : " << intervals_[pt_nr].first << " , " << intervals_[pt_nr].second << std::endl; diff --git a/src/Persistence_representations/include/gudhi/Persistence_heat_maps.h b/src/Persistence_representations/include/gudhi/Persistence_heat_maps.h index 04dd78ad..a80c3c40 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_heat_maps.h +++ b/src/Persistence_representations/include/gudhi/Persistence_heat_maps.h @@ -582,10 +582,10 @@ void Persistence_heat_maps<Scalling_of_kernels>::construct(const std::vector<std for (size_t pt_nr = 0; pt_nr != intervals_.size(); ++pt_nr) { // compute the value of intervals_[pt_nr] in the grid: - int x_grid = static_cast<int>((intervals_[pt_nr].first - this->min_) / - (this->max_ - this->min_) * number_of_pixels); - int y_grid = static_cast<int>((intervals_[pt_nr].second - this->min_) / - (this->max_ - this->min_) * number_of_pixels); + int x_grid = + static_cast<int>((intervals_[pt_nr].first - this->min_) / (this->max_ - this->min_) * number_of_pixels); + int y_grid = + static_cast<int>((intervals_[pt_nr].second - this->min_) / (this->max_ - this->min_) * number_of_pixels); if (dbg) { std::cerr << "point : " << intervals_[pt_nr].first << " , " << intervals_[pt_nr].second << std::endl; @@ -743,10 +743,10 @@ void Persistence_heat_maps<Scalling_of_kernels>::compute_percentage_of_active( template <typename Scalling_of_kernels> void Persistence_heat_maps<Scalling_of_kernels>::plot(const char* filename) const { std::ofstream out; - std::stringstream ss; - ss << filename << "_GnuplotScript"; + std::stringstream gnuplot_script; + gnuplot_script << filename << "_GnuplotScript"; - out.open(ss.str().c_str()); + out.open(gnuplot_script.str().c_str()); out << "plot '-' matrix with image" << std::endl; for (size_t i = 0; i != this->heat_map.size(); ++i) { for (size_t j = 0; j != this->heat_map[i].size(); ++j) { @@ -755,8 +755,8 @@ void Persistence_heat_maps<Scalling_of_kernels>::plot(const char* filename) cons out << std::endl; } out.close(); - std::cout << "Gnuplot script have been created. Open gnuplot and type load \'" << ss.str().c_str() - << "\' to see the picture." << std::endl; + std::cout << "To visualize, install gnuplot and type the command: gnuplot -persist -e \"load \'" + << gnuplot_script.str().c_str() << "\'\"" << std::endl; } template <typename Scalling_of_kernels> @@ -797,8 +797,7 @@ void Persistence_heat_maps<Scalling_of_kernels>::load_from_file(const char* file std::string temp; std::getline(in, temp); - - while (!in.eof()) { + while (in.good()) { std::getline(in, temp); std::stringstream lineSS; lineSS << temp; diff --git a/src/Persistence_representations/include/gudhi/Persistence_intervals.h b/src/Persistence_representations/include/gudhi/Persistence_intervals.h index 525d58a3..3d04d8b7 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_intervals.h +++ b/src/Persistence_representations/include/gudhi/Persistence_intervals.h @@ -167,10 +167,10 @@ class Persistence_intervals { // this program create a gnuplot script file that allows to plot persistence diagram. std::ofstream out; - std::ostringstream nameSS; - nameSS << filename << "_GnuplotScript"; - std::string nameStr = nameSS.str(); - out.open(nameStr); + std::stringstream gnuplot_script; + gnuplot_script << filename << "_GnuplotScript"; + + out.open(gnuplot_script.str().c_str()); std::pair<double, double> min_max_values = this->get_x_range(); if (min_x == max_x) { @@ -195,8 +195,8 @@ class Persistence_intervals { out.close(); - std::cout << "Gnuplot script to visualize persistence diagram written to the file: " << nameStr << ". Type load '" - << nameStr << "' in gnuplot to visualize." << std::endl; + std::cout << "To visualize, install gnuplot and type the command: gnuplot -persist -e \"load \'" + << gnuplot_script.str().c_str() << "\'\"" << std::endl; } /** @@ -402,9 +402,8 @@ std::vector<double> Persistence_intervals::characteristic_function_of_diagram(do } for (size_t pos = beginIt; pos != endIt; ++pos) { - result[pos] += - ((x_max - x_min) / static_cast<double>(number_of_bins)) * - (this->intervals[i].second - this->intervals[i].first); + result[pos] += ((x_max - x_min) / static_cast<double>(number_of_bins)) * + (this->intervals[i].second - this->intervals[i].first); } if (dbg) { std::cerr << "Result at this stage \n"; diff --git a/src/Persistence_representations/include/gudhi/Persistence_intervals_with_distances.h b/src/Persistence_representations/include/gudhi/Persistence_intervals_with_distances.h index d5ab04b4..79908883 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_intervals_with_distances.h +++ b/src/Persistence_representations/include/gudhi/Persistence_intervals_with_distances.h @@ -26,7 +26,6 @@ #include <gudhi/Persistence_intervals.h> #include <gudhi/Bottleneck.h> - #include <limits> namespace Gudhi { @@ -47,7 +46,7 @@ class Persistence_intervals_with_distances : public Persistence_intervals { * The last parameter, tolerance, it is an additiv error of the approimation, set by default to zero. **/ double distance(const Persistence_intervals_with_distances& second, double power = std::numeric_limits<double>::max(), - double tolerance = 0) const { + double tolerance = (std::numeric_limits<double>::min)()) const { if (power >= std::numeric_limits<double>::max()) { return Gudhi::persistence_diagram::bottleneck_distance(this->intervals, second.intervals, tolerance); } else { diff --git a/src/Persistence_representations/include/gudhi/Persistence_landscape.h b/src/Persistence_representations/include/gudhi/Persistence_landscape.h index 5c300112..c5aa7867 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_landscape.h +++ b/src/Persistence_representations/include/gudhi/Persistence_landscape.h @@ -79,14 +79,16 @@ class Persistence_landscape { /** * Constructor that takes as an input a vector of birth-death pairs. **/ - Persistence_landscape(const std::vector<std::pair<double, double> >& p, size_t number_of_levels = std::numeric_limits<size_t>::max() ); + Persistence_landscape(const std::vector<std::pair<double, double> >& p, + size_t number_of_levels = std::numeric_limits<size_t>::max()); /** * Constructor that reads persistence intervals from file and creates persistence landscape. The format of the *input file is the following: in each line we put birth-death pair. Last line is assumed * to be empty. Even if the points within a line are not ordered, they will be ordered while the input is read. **/ - Persistence_landscape(const char* filename, size_t dimension = std::numeric_limits<unsigned>::max() , size_t number_of_levels = std::numeric_limits<size_t>::max() ); + Persistence_landscape(const char* filename, size_t dimension = std::numeric_limits<unsigned>::max(), + size_t number_of_levels = std::numeric_limits<size_t>::max()); /** * This procedure loads a landscape from file. It erase all the data that was previously stored in this landscape. @@ -285,7 +287,7 @@ class Persistence_landscape { *distance, we need to take its absolute value. This is the purpose of this procedure. **/ Persistence_landscape abs(); - + Persistence_landscape* new_abs(); /** @@ -453,7 +455,8 @@ class Persistence_landscape { size_t number_of_functions_for_vectorization; size_t number_of_functions_for_projections_to_reals; - void construct_persistence_landscape_from_barcode(const std::vector<std::pair<double, double> >& p , size_t number_of_levels = std::numeric_limits<size_t>::max()); + void construct_persistence_landscape_from_barcode(const std::vector<std::pair<double, double> >& p, + size_t number_of_levels = std::numeric_limits<size_t>::max()); Persistence_landscape multiply_lanscape_by_real_number_not_overwrite(double x) const; void multiply_lanscape_by_real_number_overwrite(double x); friend double compute_maximal_distance_non_symmetric(const Persistence_landscape& pl1, @@ -473,7 +476,7 @@ Persistence_landscape::Persistence_landscape(const char* filename, size_t dimens } else { barcode = read_persistence_intervals_in_one_dimension_from_file(filename); } - this->construct_persistence_landscape_from_barcode(barcode,number_of_levels); + this->construct_persistence_landscape_from_barcode(barcode, number_of_levels); this->set_up_numbers_of_functions_for_vectorization_and_projections_to_reals(); } @@ -506,14 +509,14 @@ bool Persistence_landscape::operator==(const Persistence_landscape& rhs) const { return true; } -Persistence_landscape::Persistence_landscape(const std::vector<std::pair<double, double> >& p,size_t number_of_levels) { - this->construct_persistence_landscape_from_barcode(p,number_of_levels); +Persistence_landscape::Persistence_landscape(const std::vector<std::pair<double, double> >& p, + size_t number_of_levels) { + this->construct_persistence_landscape_from_barcode(p, number_of_levels); this->set_up_numbers_of_functions_for_vectorization_and_projections_to_reals(); } void Persistence_landscape::construct_persistence_landscape_from_barcode( - const std::vector<std::pair<double, double> >& p, size_t number_of_levels) - { + const std::vector<std::pair<double, double> >& p, size_t number_of_levels) { bool dbg = false; if (dbg) { std::cerr << "Persistence_landscape::Persistence_landscape( const std::vector< std::pair< double , double > >& p )" @@ -648,12 +651,11 @@ void Persistence_landscape::construct_persistence_landscape_from_barcode( lambda_n.erase(std::unique(lambda_n.begin(), lambda_n.end()), lambda_n.end()); this->land.push_back(lambda_n); - + ++number_of_levels_in_the_landscape; - if ( number_of_levels == number_of_levels_in_the_landscape ) - { - break; - } + if (number_of_levels == number_of_levels_in_the_landscape) { + break; + } } } @@ -857,58 +859,47 @@ Persistence_landscape Persistence_landscape::abs() { return result; } +Persistence_landscape* Persistence_landscape::new_abs() { + Persistence_landscape* result = new Persistence_landscape(*this); + for (size_t level = 0; level != this->land.size(); ++level) { + if (AbsDbg) { + std::cout << "level: " << level << std::endl; + } + std::vector<std::pair<double, double> > lambda_n; + lambda_n.push_back(std::make_pair(-std::numeric_limits<int>::max(), 0)); + for (size_t i = 1; i != this->land[level].size(); ++i) { + if (AbsDbg) { + std::cout << "this->land[" << level << "][" << i << "] : " << this->land[level][i].first << " " + << this->land[level][i].second << std::endl; + } + // if a line segment between this->land[level][i-1] and this->land[level][i] crosses the x-axis, then we have to + // add one landscape point t o result + if ((this->land[level][i - 1].second) * (this->land[level][i].second) < 0) { + double zero = + find_zero_of_a_line_segment_between_those_two_points(this->land[level][i - 1], this->land[level][i]); -Persistence_landscape* Persistence_landscape::new_abs() -{ - Persistence_landscape* result = new Persistence_landscape(*this); - for (size_t level = 0; level != this->land.size(); ++level) - { - if (AbsDbg) - { - std::cout << "level: " << level << std::endl; - } - std::vector<std::pair<double, double> > lambda_n; - lambda_n.push_back(std::make_pair(-std::numeric_limits<int>::max(), 0)); - for (size_t i = 1; i != this->land[level].size(); ++i) - { - if (AbsDbg) - { - std::cout << "this->land[" << level << "][" << i << "] : " << this->land[level][i].first << " " - << this->land[level][i].second << std::endl; - } - // if a line segment between this->land[level][i-1] and this->land[level][i] crosses the x-axis, then we have to - // add one landscape point t o result - if ((this->land[level][i - 1].second) * (this->land[level][i].second) < 0) { - double zero = - find_zero_of_a_line_segment_between_those_two_points(this->land[level][i - 1], this->land[level][i]); - - lambda_n.push_back(std::make_pair(zero, 0)); - lambda_n.push_back(std::make_pair(this->land[level][i].first, fabs(this->land[level][i].second))); - if (AbsDbg) - { - std::cout << "Adding pair : (" << zero << ",0)" << std::endl; - std::cout << "In the same step adding pair : (" << this->land[level][i].first << "," - << fabs(this->land[level][i].second) << ") " << std::endl; - std::cin.ignore(); - } - } - else - { - lambda_n.push_back(std::make_pair(this->land[level][i].first, fabs(this->land[level][i].second))); - if (AbsDbg) - { - std::cout << "Adding pair : (" << this->land[level][i].first << "," << fabs(this->land[level][i].second) - << ") " << std::endl; - std::cin.ignore(); - } - } - } - result->land.push_back(lambda_n); - } - return result; + lambda_n.push_back(std::make_pair(zero, 0)); + lambda_n.push_back(std::make_pair(this->land[level][i].first, fabs(this->land[level][i].second))); + if (AbsDbg) { + std::cout << "Adding pair : (" << zero << ",0)" << std::endl; + std::cout << "In the same step adding pair : (" << this->land[level][i].first << "," + << fabs(this->land[level][i].second) << ") " << std::endl; + std::cin.ignore(); + } + } else { + lambda_n.push_back(std::make_pair(this->land[level][i].first, fabs(this->land[level][i].second))); + if (AbsDbg) { + std::cout << "Adding pair : (" << this->land[level][i].first << "," << fabs(this->land[level][i].second) + << ") " << std::endl; + std::cin.ignore(); + } + } + } + result->land.push_back(lambda_n); + } + return result; } - Persistence_landscape Persistence_landscape::multiply_lanscape_by_real_number_not_overwrite(double x) const { std::vector<std::vector<std::pair<double, double> > > result(this->land.size()); for (size_t dim = 0; dim != this->land.size(); ++dim) { @@ -954,7 +945,7 @@ void Persistence_landscape::load_landscape_from_file(const char* filename) { std::vector<std::pair<double, double> > landscapeAtThisLevel; bool isThisAFirsLine = true; - while (!in.eof()) { + while (in.good()) { getline(in, line); if (!(line.length() == 0 || line[0] == '#')) { std::stringstream lineSS; @@ -1340,10 +1331,9 @@ void Persistence_landscape::plot(const char* filename, double xRangeBegin, doubl // this program create a gnuplot script file that allows to plot persistence diagram. std::ofstream out; - std::ostringstream nameSS; - nameSS << filename << "_GnuplotScript"; - std::string nameStr = nameSS.str(); - out.open(nameStr); + std::ostringstream gnuplot_script; + gnuplot_script << filename << "_GnuplotScript"; + out.open(gnuplot_script.str().c_str()); if ((xRangeBegin != std::numeric_limits<double>::max()) || (xRangeEnd != std::numeric_limits<double>::max()) || (yRangeBegin != std::numeric_limits<double>::max()) || (yRangeEnd != std::numeric_limits<double>::max())) { @@ -1376,8 +1366,8 @@ void Persistence_landscape::plot(const char* filename, double xRangeBegin, doubl } out << "EOF" << std::endl; } - std::cout << "Gnuplot script to visualize persistence diagram written to the file: " << nameStr << ". Type load '" - << nameStr << "' in gnuplot to visualize." << std::endl; + std::cout << "To visualize, install gnuplot and type the command: gnuplot -persist -e \"load \'" + << gnuplot_script.str().c_str() << "\'\"" << std::endl; } } // namespace Persistence_representations diff --git a/src/Persistence_representations/include/gudhi/Persistence_landscape_on_grid.h b/src/Persistence_representations/include/gudhi/Persistence_landscape_on_grid.h index 4ceb9bf6..84fd22ed 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_landscape_on_grid.h +++ b/src/Persistence_representations/include/gudhi/Persistence_landscape_on_grid.h @@ -1207,10 +1207,9 @@ void Persistence_landscape_on_grid::plot(const char* filename, double min_x, dou // this program create a gnuplot script file that allows to plot persistence diagram. std::ofstream out; - std::ostringstream nameSS; - nameSS << filename << "_GnuplotScript"; - std::string nameStr = nameSS.str(); - out.open(nameStr); + std::ostringstream gnuplot_script; + gnuplot_script << filename << "_GnuplotScript"; + out.open(gnuplot_script.str().c_str()); if (min_x == max_x) { std::pair<double, double> min_max = compute_minimum_maximum(); @@ -1241,7 +1240,6 @@ void Persistence_landscape_on_grid::plot(const char* filename, double min_x, dou out << "plot "; for (size_t lambda = from; lambda != to; ++lambda) { - // out << " '-' using 1:2 title 'l" << lambda << "' with lp"; out << " '-' using 1:2 notitle with lp"; if (lambda + 1 != to) { out << ", \\"; @@ -1261,8 +1259,8 @@ void Persistence_landscape_on_grid::plot(const char* filename, double min_x, dou } out << "EOF" << std::endl; } - std::cout << "Gnuplot script to visualize persistence diagram written to the file: " << nameStr << ". Type load '" - << nameStr << "' in gnuplot to visualize." << std::endl; + std::cout << "To visualize, install gnuplot and type the command: gnuplot -persist -e \"load \'" + << gnuplot_script.str().c_str() << "\'\"" << std::endl; } template <typename T> diff --git a/src/Persistence_representations/include/gudhi/Persistence_vectors.h b/src/Persistence_representations/include/gudhi/Persistence_vectors.h index 0fb49eee..63577e46 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_vectors.h +++ b/src/Persistence_representations/include/gudhi/Persistence_vectors.h @@ -201,7 +201,8 @@ class Vector_distances_in_diagram { } out << std::endl; out.close(); - std::cout << "To visualize, open gnuplot and type: load \'" << gnuplot_script.str().c_str() << "\'" << std::endl; + std::cout << "To visualize, install gnuplot and type the command: gnuplot -persist -e \"load \'" + << gnuplot_script.str().c_str() << "\'\"" << std::endl; } /** @@ -617,9 +618,7 @@ void Vector_distances_in_diagram<F>::load_from_file(const char* filename) { } double number; - while (true) { - in >> number; - if (in.eof()) break; + while (in >> number) { this->sorted_vector_of_distances.push_back(number); } in.close(); diff --git a/src/Persistence_representations/include/gudhi/Persistence_weighted_gaussian.h b/src/Persistence_representations/include/gudhi/Persistence_weighted_gaussian.h new file mode 100644 index 00000000..2884885c --- /dev/null +++ b/src/Persistence_representations/include/gudhi/Persistence_weighted_gaussian.h @@ -0,0 +1,143 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Mathieu Carriere + * + * Copyright (C) 2018 INRIA (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef PERSISTENCE_WEIGHTED_GAUSSIAN_H_ +#define PERSISTENCE_WEIGHTED_GAUSSIAN_H_ + +#ifdef GUDHI_USE_TBB +#include <tbb/parallel_for.h> +#endif + +// gudhi include +#include <gudhi/read_persistence_from_file.h> + +// standard include +#include <cmath> +#include <iostream> +#include <vector> +#include <limits> +#include <fstream> +#include <sstream> +#include <algorithm> +#include <string> +#include <utility> +#include <functional> +#include <boost/math/constants/constants.hpp> + +double pi = boost::math::constants::pi<double>(); +using PD = std::vector<std::pair<double,double> >; + +namespace Gudhi { +namespace Persistence_representations { + +class Persistence_weighted_gaussian{ + + protected: + PD diagram; + + public: + + Persistence_weighted_gaussian(PD _diagram){diagram = _diagram;} + PD get_diagram(){return this->diagram;} + + + // ********************************** + // Utils. + // ********************************** + + + static double pss_weight(std::pair<double,double> P){ + if(P.second > P.first) return 1; + else return -1; + } + + static double arctan_weight(std::pair<double,double> P){ + return atan(P.second - P.first); + } + + template<class Weight = std::function<double (std::pair<double,double>) > > + std::vector<std::pair<double,double> > Fourier_feat(PD D, std::vector<std::pair<double,double> > Z, Weight weight = arctan_weight){ + int m = D.size(); std::vector<std::pair<double,double> > B; int M = Z.size(); + for(int i = 0; i < M; i++){ + double d1 = 0; double d2 = 0; double zx = Z[i].first; double zy = Z[i].second; + for(int j = 0; j < m; j++){ + double x = D[j].first; double y = D[j].second; + d1 += weight(D[j])*cos(x*zx + y*zy); + d2 += weight(D[j])*sin(x*zx + y*zy); + } + B.emplace_back(d1,d2); + } + return B; + } + + std::vector<std::pair<double,double> > random_Fourier(double sigma, int M = 1000){ + std::normal_distribution<double> distrib(0,1); std::vector<std::pair<double,double> > Z; std::random_device rd; + for(int i = 0; i < M; i++){ + std::mt19937 e1(rd()); std::mt19937 e2(rd()); + double zx = distrib(e1); double zy = distrib(e2); + Z.emplace_back(zx/sigma,zy/sigma); + } + return Z; + } + + + + // ********************************** + // Scalar product + distance. + // ********************************** + + + template<class Weight = std::function<double (std::pair<double,double>) > > + double compute_scalar_product(Persistence_weighted_gaussian second, double sigma, Weight weight = arctan_weight, int m = 1000){ + + PD diagram1 = this->diagram; PD diagram2 = second.diagram; + + if(m == -1){ + int num_pts1 = diagram1.size(); int num_pts2 = diagram2.size(); double k = 0; + for(int i = 0; i < num_pts1; i++) + for(int j = 0; j < num_pts2; j++) + k += weight(diagram1[i])*weight(diagram2[j])*exp(-((diagram1[i].first - diagram2[j].first) * (diagram1[i].first - diagram2[j].first) + + (diagram1[i].second - diagram2[j].second) * (diagram1[i].second - diagram2[j].second)) + /(2*sigma*sigma)); + return k; + } + else{ + std::vector<std::pair<double,double> > z = random_Fourier(sigma, m); + std::vector<std::pair<double,double> > b1 = Fourier_feat(diagram1,z,weight); + std::vector<std::pair<double,double> > b2 = Fourier_feat(diagram2,z,weight); + double d = 0; for(int i = 0; i < m; i++) d += b1[i].first*b2[i].first + b1[i].second*b2[i].second; + return d/m; + } + } + + template<class Weight = std::function<double (std::pair<double,double>) > > + double distance(Persistence_weighted_gaussian second, double sigma, Weight weight = arctan_weight, int m = 1000, double power = 1) { + return std::pow(this->compute_scalar_product(*this, sigma, weight, m) + second.compute_scalar_product(second, sigma, weight, m)-2*this->compute_scalar_product(second, sigma, weight, m), power/2.0); + } + + +}; + +} // namespace Persistence_weighted_gaussian +} // namespace Gudhi + +#endif // PERSISTENCE_WEIGHTED_GAUSSIAN_H_ diff --git a/src/Persistence_representations/include/gudhi/Sliced_Wasserstein.h b/src/Persistence_representations/include/gudhi/Sliced_Wasserstein.h new file mode 100644 index 00000000..4fa6151f --- /dev/null +++ b/src/Persistence_representations/include/gudhi/Sliced_Wasserstein.h @@ -0,0 +1,285 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Mathieu Carriere + * + * Copyright (C) 2018 INRIA (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef SLICED_WASSERSTEIN_H_ +#define SLICED_WASSERSTEIN_H_ + +#ifdef GUDHI_USE_TBB +#include <tbb/parallel_for.h> +#endif + +// gudhi include +#include <gudhi/read_persistence_from_file.h> + +// standard include +#include <cmath> +#include <iostream> +#include <vector> +#include <limits> +#include <fstream> +#include <sstream> +#include <algorithm> +#include <string> +#include <utility> +#include <functional> +#include <boost/math/constants/constants.hpp> + +double pi = boost::math::constants::pi<double>(); +using PD = std::vector<std::pair<double,double> >; + +namespace Gudhi { +namespace Persistence_representations { + +class Sliced_Wasserstein { + + protected: + PD diagram; + + public: + + Sliced_Wasserstein(PD _diagram){diagram = _diagram;} + PD get_diagram(){return this->diagram;} + + + // ********************************** + // Utils. + // ********************************** + + // Compute the angle formed by two points of a PD + double compute_angle(PD diag, int i, int j){ + std::pair<double,double> vect; double x1,y1, x2,y2; + x1 = diag[i].first; y1 = diag[i].second; + x2 = diag[j].first; y2 = diag[j].second; + if (y1 - y2 > 0){ + vect.first = y1 - y2; + vect.second = x2 - x1;} + else{ + if(y1 - y2 < 0){ + vect.first = y2 - y1; + vect.second = x1 - x2; + } + else{ + vect.first = 0; + vect.second = abs(x1 - x2);} + } + double norm = std::sqrt(vect.first*vect.first + vect.second*vect.second); + return asin(vect.second/norm); + } + + // Compute the integral of |cos()| between alpha and beta, valid only if alpha is in [-pi,pi] and beta-alpha is in [0,pi] + double compute_int_cos(const double & alpha, const double & beta){ + double res = 0; + if (alpha >= 0 && alpha <= pi){ + if (cos(alpha) >= 0){ + if(pi/2 <= beta){res = 2-sin(alpha)-sin(beta);} + else{res = sin(beta)-sin(alpha);} + } + else{ + if(1.5*pi <= beta){res = 2+sin(alpha)+sin(beta);} + else{res = sin(alpha)-sin(beta);} + } + } + if (alpha >= -pi && alpha <= 0){ + if (cos(alpha) <= 0){ + if(-pi/2 <= beta){res = 2+sin(alpha)+sin(beta);} + else{res = sin(alpha)-sin(beta);} + } + else{ + if(pi/2 <= beta){res = 2-sin(alpha)-sin(beta);} + else{res = sin(beta)-sin(alpha);} + } + } + return res; + } + + double compute_int(const double & theta1, const double & theta2, const int & p, const int & q, const PD & PD1, const PD & PD2){ + double norm = std::sqrt( (PD1[p].first-PD2[q].first)*(PD1[p].first-PD2[q].first) + (PD1[p].second-PD2[q].second)*(PD1[p].second-PD2[q].second) ); + double angle1; + if (PD1[p].first > PD2[q].first) + angle1 = theta1 - asin( (PD1[p].second-PD2[q].second)/norm ); + else + angle1 = theta1 - asin( (PD2[q].second-PD1[p].second)/norm ); + double angle2 = angle1 + theta2 - theta1; + double integral = compute_int_cos(angle1,angle2); + return norm*integral; + } + + + + + // ********************************** + // Scalar product + distance. + // ********************************** + + double compute_sliced_wasserstein_distance(Sliced_Wasserstein second, int approx) { + + PD diagram1 = this->diagram; PD diagram2 = second.diagram; double sw = 0; + + if(approx == -1){ + + // Add projections onto diagonal. + int n1, n2; n1 = diagram1.size(); n2 = diagram2.size(); double max_ordinate = std::numeric_limits<double>::lowest(); + for (int i = 0; i < n2; i++){ + max_ordinate = std::max(max_ordinate, diagram2[i].second); + diagram1.emplace_back( (diagram2[i].first+diagram2[i].second)/2, (diagram2[i].first+diagram2[i].second)/2 ); + } + for (int i = 0; i < n1; i++){ + max_ordinate = std::max(max_ordinate, diagram1[i].second); + diagram2.emplace_back( (diagram1[i].first+diagram1[i].second)/2, (diagram1[i].first+diagram1[i].second)/2 ); + } + int num_pts_dgm = diagram1.size(); + + // Slightly perturb the points so that the PDs are in generic positions. + int mag = 0; while(max_ordinate > 10){mag++; max_ordinate/=10;} + double thresh = pow(10,-5+mag); + srand(time(NULL)); + for (int i = 0; i < num_pts_dgm; i++){ + diagram1[i].first += thresh*(1.0-2.0*rand()/RAND_MAX); diagram1[i].second += thresh*(1.0-2.0*rand()/RAND_MAX); + diagram2[i].first += thresh*(1.0-2.0*rand()/RAND_MAX); diagram2[i].second += thresh*(1.0-2.0*rand()/RAND_MAX); + } + + // Compute all angles in both PDs. + std::vector<std::pair<double, std::pair<int,int> > > angles1, angles2; + for (int i = 0; i < num_pts_dgm; i++){ + for (int j = i+1; j < num_pts_dgm; j++){ + double theta1 = compute_angle(diagram1,i,j); double theta2 = compute_angle(diagram2,i,j); + angles1.emplace_back(theta1, std::pair<int,int>(i,j)); + angles2.emplace_back(theta2, std::pair<int,int>(i,j)); + } + } + + // Sort angles. + std::sort(angles1.begin(), angles1.end(), [=](std::pair<double, std::pair<int,int> >& p1, const std::pair<double, std::pair<int,int> >& p2){return (p1.first < p2.first);}); + std::sort(angles2.begin(), angles2.end(), [=](std::pair<double, std::pair<int,int> >& p1, const std::pair<double, std::pair<int,int> >& p2){return (p1.first < p2.first);}); + + // Initialize orders of the points of both PDs (given by ordinates when theta = -pi/2). + std::vector<int> orderp1, orderp2; + for (int i = 0; i < num_pts_dgm; i++){ orderp1.push_back(i); orderp2.push_back(i); } + std::sort( orderp1.begin(), orderp1.end(), [=](int i, int j){ if(diagram1[i].second != diagram1[j].second) return (diagram1[i].second < diagram1[j].second); else return (diagram1[i].first > diagram1[j].first); } ); + std::sort( orderp2.begin(), orderp2.end(), [=](int i, int j){ if(diagram2[i].second != diagram2[j].second) return (diagram2[i].second < diagram2[j].second); else return (diagram2[i].first > diagram2[j].first); } ); + + // Find the inverses of the orders. + std::vector<int> order1(num_pts_dgm); std::vector<int> order2(num_pts_dgm); + for(int i = 0; i < num_pts_dgm; i++) for (int j = 0; j < num_pts_dgm; j++) if(orderp1[j] == i){ order1[i] = j; break; } + for(int i = 0; i < num_pts_dgm; i++) for (int j = 0; j < num_pts_dgm; j++) if(orderp2[j] == i){ order2[i] = j; break; } + + // Record all inversions of points in the orders as theta varies along the positive half-disk. + std::vector<std::vector<std::pair<int,double> > > anglePerm1(num_pts_dgm); + std::vector<std::vector<std::pair<int,double> > > anglePerm2(num_pts_dgm); + + int m1 = angles1.size(); + for (int i = 0; i < m1; i++){ + double theta = angles1[i].first; int p = angles1[i].second.first; int q = angles1[i].second.second; + anglePerm1[order1[p]].emplace_back(p,theta); + anglePerm1[order1[q]].emplace_back(q,theta); + int a = order1[p]; int b = order1[q]; order1[p] = b; order1[q] = a; + } + + int m2 = angles2.size(); + for (int i = 0; i < m2; i++){ + double theta = angles2[i].first; int p = angles2[i].second.first; int q = angles2[i].second.second; + anglePerm2[order2[p]].emplace_back(p,theta); + anglePerm2[order2[q]].emplace_back(q,theta); + int a = order2[p]; int b = order2[q]; order2[p] = b; order2[q] = a; + } + + for (int i = 0; i < num_pts_dgm; i++){ + anglePerm1[order1[i]].emplace_back(i,pi/2); + anglePerm2[order2[i]].emplace_back(i,pi/2); + } + + // Compute the SW distance with the list of inversions. + for (int i = 0; i < num_pts_dgm; i++){ + std::vector<std::pair<int,double> > u,v; u = anglePerm1[i]; v = anglePerm2[i]; + double theta1, theta2; theta1 = -pi/2; + unsigned int ku, kv; ku = 0; kv = 0; theta2 = std::min(u[ku].second,v[kv].second); + while(theta1 != pi/2){ + if(diagram1[u[ku].first].first != diagram2[v[kv].first].first || diagram1[u[ku].first].second != diagram2[v[kv].first].second) + if(theta1 != theta2) + sw += compute_int(theta1, theta2, u[ku].first, v[kv].first, diagram1, diagram2); + theta1 = theta2; + if ( (theta2 == u[ku].second) && ku < u.size()-1 ) ku++; + if ( (theta2 == v[kv].second) && kv < v.size()-1 ) kv++; + theta2 = std::min(u[ku].second, v[kv].second); + } + } + } + + + else{ + double step = pi/approx; + + // Add projections onto diagonal. + int n1, n2; n1 = diagram1.size(); n2 = diagram2.size(); + for (int i = 0; i < n2; i++) + diagram1.emplace_back( (diagram2[i].first + diagram2[i].second)/2, (diagram2[i].first + diagram2[i].second)/2 ); + for (int i = 0; i < n1; i++) + diagram2.emplace_back( (diagram1[i].first + diagram1[i].second)/2, (diagram1[i].first + diagram1[i].second)/2 ); + int n = diagram1.size(); + + // Sort and compare all projections. + #ifdef GUDHI_USE_TBB + tbb::parallel_for(0, approx, [&](int i){ + std::vector<std::pair<int,double> > l1, l2; + for (int j = 0; j < n; j++){ + l1.emplace_back( j, diagram1[j].first*cos(-pi/2+i*step) + diagram1[j].second*sin(-pi/2+i*step) ); + l2.emplace_back( j, diagram2[j].first*cos(-pi/2+i*step) + diagram2[j].second*sin(-pi/2+i*step) ); + } + std::sort(l1.begin(),l1.end(), [=](const std::pair<int,double> & p1, const std::pair<int,double> & p2){return p1.second < p2.second;}); + std::sort(l2.begin(),l2.end(), [=](const std::pair<int,double> & p1, const std::pair<int,double> & p2){return p1.second < p2.second;}); + double f = 0; for (int j = 0; j < n; j++) f += std::abs(l1[j].second - l2[j].second); + sw += f*step; + }); + #else + for (int i = 0; i < approx; i++){ + std::vector<std::pair<int,double> > l1, l2; + for (int j = 0; j < n; j++){ + l1.emplace_back( j, diagram1[j].first*cos(-pi/2+i*step) + diagram1[j].second*sin(-pi/2+i*step) ); + l2.emplace_back( j, diagram2[j].first*cos(-pi/2+i*step) + diagram2[j].second*sin(-pi/2+i*step) ); + } + std::sort(l1.begin(),l1.end(), [=](const std::pair<int,double> & p1, const std::pair<int,double> & p2){return p1.second < p2.second;}); + std::sort(l2.begin(),l2.end(), [=](const std::pair<int,double> & p1, const std::pair<int,double> & p2){return p1.second < p2.second;}); + double f = 0; for (int j = 0; j < n; j++) f += std::abs(l1[j].second - l2[j].second); + sw += f*step; + } + #endif + } + + return sw/pi; + } + + + double compute_scalar_product(Sliced_Wasserstein second, double sigma, int approx = 100) { + return std::exp(-compute_sliced_wasserstein_distance(second, approx)/(2*sigma*sigma)); + } + + double distance(Sliced_Wasserstein second, double sigma, int approx = 100, double power = 1) { + return std::pow(this->compute_scalar_product(*this, sigma, approx) + second.compute_scalar_product(second, sigma, approx)-2*this->compute_scalar_product(second, sigma, approx), power/2.0); + } + + +}; + +} // namespace Sliced_Wasserstein +} // namespace Gudhi + +#endif // SLICED_WASSERSTEIN_H_ diff --git a/src/Persistence_representations/include/gudhi/read_persistence_from_file.h b/src/Persistence_representations/include/gudhi/read_persistence_from_file.h index 770da15b..83b89d0e 100644 --- a/src/Persistence_representations/include/gudhi/read_persistence_from_file.h +++ b/src/Persistence_representations/include/gudhi/read_persistence_from_file.h @@ -23,6 +23,8 @@ #ifndef READ_PERSISTENCE_FROM_FILE_H_ #define READ_PERSISTENCE_FROM_FILE_H_ +#include <gudhi/reader_utils.h> + #include <iostream> #include <fstream> #include <sstream> @@ -30,7 +32,7 @@ #include <algorithm> #include <string> #include <utility> -#include <gudhi/reader_utils.h> +#include <limits> // for std::numeric_limits<> namespace Gudhi { namespace Persistence_representations { @@ -50,81 +52,66 @@ namespace Persistence_representations { * The procedure returns vector of persistence pairs. **/ std::vector<std::pair<double, double> > read_persistence_intervals_in_one_dimension_from_file( - std::string const& filename, int dimension = -1, double what_to_substitute_for_infinite_bar = -1) { + std::string const& filename, int dimension = -1, double what_to_substitute_for_infinite_bar = -1) { bool dbg = false; std::string line; - std::vector<std::pair<double, double> > barcode_initial = read_persistence_intervals_in_dimension(filename,(int)dimension); + std::vector<std::pair<double, double> > barcode_initial = + read_persistence_intervals_in_dimension(filename, (int)dimension); std::vector<std::pair<double, double> > final_barcode; - final_barcode.reserve( barcode_initial.size() ); - - if ( dbg ) - { - std::cerr << "Here are the intervals that we read from the file : \n"; - for ( size_t i = 0 ; i != barcode_initial.size() ; ++i ) - { - std::cout << barcode_initial[i].first << " " << barcode_initial[i].second << std::endl; - } - getchar(); + final_barcode.reserve(barcode_initial.size()); + + if (dbg) { + std::cerr << "Here are the intervals that we read from the file : \n"; + for (size_t i = 0; i != barcode_initial.size(); ++i) { + std::cout << barcode_initial[i].first << " " << barcode_initial[i].second << std::endl; + } + getchar(); } - - for ( size_t i = 0 ; i != barcode_initial.size() ; ++i ) - { - if ( dbg ) - { - std::cout << "COnsidering interval : " << barcode_initial[i].first << " " << barcode_initial[i].second << std::endl; - } - // if ( barcode_initial[i].first == barcode_initial[i].second ) - //{ - // if ( dbg )std::cout << "It has zero length \n"; - // continue;//zero length intervals are not relevant, so we skip all of them. - //} - - if ( barcode_initial[i].first > barcode_initial[i].second )//note that in this case barcode_initial[i].second != std::numeric_limits<double>::infinity() - { - if ( dbg )std::cout << "Swap and enter \n"; - //swap them to make sure that birth < death - final_barcode.push_back( std::pair<double,double>( barcode_initial[i].second , barcode_initial[i].first ) ); - continue; - } - else - { - if ( barcode_initial[i].second != std::numeric_limits<double>::infinity() ) - { - if ( dbg )std::cout << "Simply enters\n"; - //in this case, due to the previous conditions we know that barcode_initial[i].first < barcode_initial[i].second, so we put them as they are - final_barcode.push_back( std::pair<double,double>( barcode_initial[i].first , barcode_initial[i].second ) ); - } - } - - if ( (barcode_initial[i].second == std::numeric_limits<double>::infinity() ) && ( what_to_substitute_for_infinite_bar != -1 ) ) - { - if ( barcode_initial[i].first < what_to_substitute_for_infinite_bar )//if only birth < death. - { - final_barcode.push_back( std::pair<double,double>( barcode_initial[i].first , what_to_substitute_for_infinite_bar ) ); - } - } - else - { - //if the variable what_to_substitute_for_infinite_bar is not set, then we ignore all the infinite bars. - } + + for (size_t i = 0; i != barcode_initial.size(); ++i) { + if (dbg) { + std::cout << "COnsidering interval : " << barcode_initial[i].first << " " << barcode_initial[i].second + << std::endl; + } + + if (barcode_initial[i].first > barcode_initial[i].second) { + // note that in this case barcode_initial[i].second != std::numeric_limits<double>::infinity() + if (dbg) std::cout << "Swap and enter \n"; + // swap them to make sure that birth < death + final_barcode.push_back(std::pair<double, double>(barcode_initial[i].second, barcode_initial[i].first)); + continue; + } else { + if (barcode_initial[i].second != std::numeric_limits<double>::infinity()) { + if (dbg) std::cout << "Simply enters\n"; + // in this case, due to the previous conditions we know that barcode_initial[i].first < + // barcode_initial[i].second, so we put them as they are + final_barcode.push_back(std::pair<double, double>(barcode_initial[i].first, barcode_initial[i].second)); + } + } + + if ((barcode_initial[i].second == std::numeric_limits<double>::infinity()) && + (what_to_substitute_for_infinite_bar != -1)) { + if (barcode_initial[i].first < what_to_substitute_for_infinite_bar) // if only birth < death. + { + final_barcode.push_back( + std::pair<double, double>(barcode_initial[i].first, what_to_substitute_for_infinite_bar)); + } + } else { + // if the variable what_to_substitute_for_infinite_bar is not set, then we ignore all the infinite bars. + } } - - - if ( dbg ) - { - std::cerr << "Here are the final bars that we are sending further : \n"; - for ( size_t i = 0 ; i != final_barcode.size() ; ++i ) - { - std::cout << final_barcode[i].first << " " << final_barcode[i].second << std::endl; - } - std::cerr << "final_barcode.size() : " << final_barcode.size() << std::endl; - getchar(); + + if (dbg) { + std::cerr << "Here are the final bars that we are sending further : \n"; + for (size_t i = 0; i != final_barcode.size(); ++i) { + std::cout << final_barcode[i].first << " " << final_barcode[i].second << std::endl; + } + std::cerr << "final_barcode.size() : " << final_barcode.size() << std::endl; + getchar(); } - - - - return final_barcode; + + return final_barcode; } // read_persistence_intervals_in_one_dimension_from_file } // namespace Persistence_representations |