11 #ifndef SPARSE_RIPS_COMPLEX_H_
12 #define SPARSE_RIPS_COMPLEX_H_
14 #include <gudhi/Debug_utils.h>
15 #include <gudhi/graph_simplicial_complex.h>
16 #include <gudhi/choose_n_farthest_points.h>
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/range/metafunctions.hpp>
25 namespace rips_complex {
44 template <
typename Filtration_value>
48 typedef typename boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
49 boost::property<vertex_filtration_t, Filtration_value>,
50 boost::property<edge_filtration_t, Filtration_value>>
53 typedef int Vertex_handle;
65 template <
typename RandomAccessPo
intRange,
typename Distance>
68 GUDHI_CHECK(epsilon > 0,
"epsilon must be positive");
69 auto dist_fun = [&](Vertex_handle i, Vertex_handle j) {
return distance(points[i], points[j]); };
70 Ker<decltype(dist_fun)> kernel(dist_fun);
72 std::back_inserter(sorted_points), std::back_inserter(params));
73 compute_sparse_graph(dist_fun, epsilon, mini, maxi);
86 template <
typename DistanceMatrix>
89 [&](Vertex_handle i, Vertex_handle j) {
return (i==j) ? 0 : (i<j) ? distance_matrix[j][i] : distance_matrix[i][j]; },
90 epsilon, mini, maxi) {}
102 template <
typename SimplicialComplexForRips>
105 std::invalid_argument(
"Sparse_rips_complex::create_complex - simplicial complex is not empty"));
112 const int n = boost::size(params);
113 std::vector<Filtration_value> lambda(n);
116 lambda[sorted_points[i]] = params[i];
117 double cst = epsilon_ * (1 - epsilon_) / 2;
119 auto filt = complex.filtration(sh);
120 auto mini = filt * cst;
121 for(
auto v : complex.simplex_vertex_range(sh)){
127 complex.expansion_with_blockers(dim_max, block);
132 template <
class Distance>
134 typedef std::size_t Point_d;
135 Ker(Distance& d) : dist(d) {}
137 typedef Distance Squared_distance_d;
138 Squared_distance_d& squared_distance_d_object()
const {
return dist; }
143 template <
typename Distance>
145 const auto& points = sorted_points;
146 const int n = boost::size(points);
147 double cst = epsilon * (1 - epsilon) / 2;
149 new (&graph_) Graph(n);
151 typename boost::graph_traits<Graph>::vertex_iterator v_i, v_e;
152 for (std::tie(v_i, v_e) = vertices(graph_); v_i != v_e; ++v_i) {
155 put(vertex_filtration_t(), graph_, v, 0);
161 for (
int i = 0; i < n; ++i) {
162 auto&& pi = points[i];
164 if (li < mini)
break;
165 for (
int j = i + 1; j < n; ++j) {
166 auto&& pj = points[j];
167 auto d = dist(pi, pj);
169 if (lj < mini)
break;
170 GUDHI_CHECK(lj <= li,
"Bad furthest point sorting");
174 if (d * epsilon <= 2 * lj)
176 else if (d * epsilon > li + lj)
179 alpha = (d - lj / epsilon) * 2;
181 if (epsilon < 1 && alpha * cst > lj)
186 add_edge(pi, pj, alpha, graph_);
195 std::vector<Vertex_handle> sorted_points;
197 std::vector<Filtration_value> params;
204 #endif // SPARSE_RIPS_COMPLEX_H_