Vertex_collapsor.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): David Salinas
4  *
5  * Copyright (C) 2014 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef UTILS_VERTEX_COLLAPSOR_H_
12 #define UTILS_VERTEX_COLLAPSOR_H_
13 
14 #include <list>
15 
16 #include "utils/Edge_contractor.h"
17 #include "utils/Furthest_point_epsilon_net.h"
18 #include "utils/UI_utils.h"
19 
23 template<typename SkBlComplex> class Vertex_collapsor {
24  private:
25  SkBlComplex& complex_;
26  size_t num_collapses_;
27 
28  public:
29  typedef typename SkBlComplex::Vertex_handle Vertex_handle;
30  typedef typename SkBlComplex::Edge_handle Edge_handle;
31 
36  Vertex_collapsor(SkBlComplex& complex, size_t num_collapses) :
37  complex_(complex), num_collapses_(num_collapses) {
38  // std::list<Vertex_handle> vertices;
39  // vertices.insert(vertices.begin(),complex_.vertex_range().begin(),complex_.vertex_range().end());
40  // UIDBG("Collapse vertices");
41  // collapse_vertices(vertices);
42 
43  std::list<Vertex_handle> vertices;
44 
45  UIDBG("Compute eps net");
46  Furthest_point_epsilon_net<Complex> eps_net(complex_);
47 
48  for (auto vh : eps_net.net_filtration_)
49  vertices.push_back(vh.vertex_handle);
50 
51  UIDBG("Collapse vertices");
52  collapse_vertices(vertices);
53  }
54 
55  private:
56  void collapse_vertices(std::list<Vertex_handle>& vertices) {
57  while (!vertices.empty() && num_collapses_--) {
58  Vertex_handle current_vertex = vertices.front();
59  vertices.pop_front();
60  if (is_link_reducible(current_vertex))
61  complex_.remove_vertex(current_vertex);
62  }
63  }
64 
65  bool is_link_reducible(Vertex_handle v) {
66  auto link = complex_.link(v);
67  if (link.empty()) return false;
68  if (link.is_cone()) return true;
69  if (link.num_connected_components() > 1) return false;
70  Edge_contractor<Complex> contractor(link, link.num_vertices() - 1);
71  (void)contractor;
72  return (link.num_vertices() == 1);
73  }
74 };
75 
76 #endif // UTILS_VERTEX_COLLAPSOR_H_
Definition: Edge_contractor.h:24
Definition: Furthest_point_epsilon_net.h:22
Definition: Vertex_collapsor.h:23
Vertex_collapsor(SkBlComplex &complex, size_t num_collapses)
Modify complex to be the expansion of the k-nearest neighbor symetric graph.
Definition: Vertex_collapsor.h:36
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Jan 14 2022 18:28:42 for GUDHIdev by Doxygen 1.9.1