diff options
Diffstat (limited to 'src/GudhUI/utils')
-rw-r--r-- | src/GudhUI/utils/Edge_collapsor.h | 84 | ||||
-rw-r--r-- | src/GudhUI/utils/Edge_contractor.h | 68 | ||||
-rw-r--r-- | src/GudhUI/utils/Furthest_point_epsilon_net.h | 134 | ||||
-rw-r--r-- | src/GudhUI/utils/K_nearest_builder.h | 106 | ||||
-rw-r--r-- | src/GudhUI/utils/Lloyd_builder.h | 78 | ||||
-rw-r--r-- | src/GudhUI/utils/MClock.h | 57 | ||||
-rw-r--r-- | src/GudhUI/utils/Persistence_compute.h | 106 | ||||
-rw-r--r-- | src/GudhUI/utils/Rips_builder.h | 56 | ||||
-rw-r--r-- | src/GudhUI/utils/UI_utils.h | 33 | ||||
-rw-r--r-- | src/GudhUI/utils/Vertex_collapsor.h | 76 | ||||
-rwxr-xr-x | src/GudhUI/utils/homsimpl | bin | 0 -> 118624 bytes |
11 files changed, 798 insertions, 0 deletions
diff --git a/src/GudhUI/utils/Edge_collapsor.h b/src/GudhUI/utils/Edge_collapsor.h new file mode 100644 index 00000000..9cf880e0 --- /dev/null +++ b/src/GudhUI/utils/Edge_collapsor.h @@ -0,0 +1,84 @@ +/* + * Collapsor.h + * + * Created on: Sep 25, 2014 + * Author: dsalinas + */ + +#ifndef COLLAPSOR_H_ +#define COLLAPSOR_H_ + +#include <list> +#include "utils/Edge_contractor.h" + +/** + * Iteratively puts every vertex at the center of its neighbors + */ +template<typename SkBlComplex> class Edge_collapsor{ +private: + SkBlComplex& complex_; + unsigned num_collapses_; +public: + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + Edge_collapsor(SkBlComplex& complex,unsigned num_collapses): + complex_(complex),num_collapses_(num_collapses) + { + std::list<Edge_handle> edges; + edges.insert(edges.begin(),complex_.edge_range().begin(),complex_.edge_range().end()); + + edges.sort( + [&](Edge_handle e1,Edge_handle e2){ + return squared_edge_length(e1) < squared_edge_length(e2); + }); + + collapse_edges(edges); + + } + +private: + + + void collapse_edges(std::list<Edge_handle>& edges){ + while(!edges.empty() && num_collapses_--){ + Edge_handle current_edge = edges.front(); + edges.pop_front(); + if(is_link_reducible(current_edge)) + complex_.remove_edge(current_edge); + } + + } + + bool is_link_reducible(Edge_handle e){ + auto link = complex_.link(e); + + if(link.empty()) return false; + + if(link.is_cone()) return true; + + if(link.num_connected_components()>1) return false; + + Edge_contractor<Complex> contractor(link,link.num_vertices()-1); + + return (link.num_vertices()==1); + } + + + double squared_edge_length(Edge_handle e) const{ + return squared_eucl_distance(complex_.point(complex_.first_vertex(e)),complex_.point(complex_.second_vertex(e))); + } + + double squared_eucl_distance(const Point& p1,const Point& p2) const{ + return Geometry_trait::Squared_distance_d()(p1,p2); + } + +}; + + + +#endif /* COLLAPSOR_H_ */ diff --git a/src/GudhUI/utils/Edge_contractor.h b/src/GudhUI/utils/Edge_contractor.h new file mode 100644 index 00000000..c7a86e0b --- /dev/null +++ b/src/GudhUI/utils/Edge_contractor.h @@ -0,0 +1,68 @@ +/* + * Contractor.h + * + * Created on: Sep 25, 2014 + * Author: dsalinas + */ + +#ifndef EDGE_CONTRACTOR_H_ +#define EDGE_CONTRACTOR_H_ + + +#include "gudhi/Skeleton_blocker_contractor.h" + +#include "gudhi/Contraction/Edge_profile.h" +#include "gudhi/Contraction/policies/Cost_policy.h" + + +/** + * Iteratively puts every vertex at the center of its neighbors + */ +template<typename SkBlComplex> class Edge_contractor{ +private: + SkBlComplex& complex_; + unsigned num_contractions_; + + /** + * @brief return a cost corresponding to the squared length of the edge + */ + template< typename EdgeProfile> class Length_cost : public contraction::Cost_policy<EdgeProfile>{ + public: + typedef typename contraction::Cost_policy<EdgeProfile>::Cost_type Cost_type; + typedef typename EdgeProfile::Point Point; + Cost_type operator()(const EdgeProfile& profile, const boost::optional<Point>& placement) const override{ + Cost_type res; + if(!placement) return res; + return Geometry_trait::Squared_distance_d()(profile.p0(),profile.p1()); //not working?? + } + }; + + public: + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + Edge_contractor(SkBlComplex& complex,unsigned num_contractions): + complex_(complex),num_contractions_(num_contractions) + { + typedef typename contraction::Edge_profile<Complex> Profile; + num_contractions = (std::min)((int)num_contractions,(int)(complex_.num_vertices()-1)); + contraction::Skeleton_blocker_contractor<Complex> contractor( + complex_, + new Length_cost<contraction::Edge_profile<Complex>>(), + contraction::make_first_vertex_placement<Profile>(), + contraction::make_link_valid_contraction<Profile>(), + contraction::make_remove_popable_blockers_visitor<Profile>() + ); + contractor.contract_edges(num_contractions); + } + + +}; + + + +#endif /* EDGE_CONTRACTOR_H_ */ diff --git a/src/GudhUI/utils/Furthest_point_epsilon_net.h b/src/GudhUI/utils/Furthest_point_epsilon_net.h new file mode 100644 index 00000000..590b65c4 --- /dev/null +++ b/src/GudhUI/utils/Furthest_point_epsilon_net.h @@ -0,0 +1,134 @@ +/* + * Furthest_point_epsilon_net.h + * + * Created on: Sep 26, 2014 + * Author: dsalinas + */ + +#ifndef FURTHEST_POINT_EPSILON_NET_H_ +#define FURTHEST_POINT_EPSILON_NET_H_ + +#include "utils/UI_utils.h" +#include <vector> + +/** + * Computes an epsilon net with furthest point strategy. + */ +template<typename SkBlComplex> class Furthest_point_epsilon_net{ +private: + SkBlComplex& complex_; + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + + /** + * Let V be the set of vertices. + * Initially v0 is one arbitrarly vertex and the set V0 is {v0}. + * Then Vk is computed as follows. + * First we compute the vertex pk that is the furthest from Vk + * then Vk = Vk \cup pk. + * The radius of pk is its distance to Vk and its meeting vertex + * is the vertex of Vk for which this distance is achieved. + */ + struct Net_filtration_vertex{ + Vertex_handle vertex_handle; + Vertex_handle meeting_vertex; + double radius; + + + Net_filtration_vertex( + Vertex_handle vertex_handle_, + Vertex_handle meeting_vertex_, + double radius_): + vertex_handle(vertex_handle_),meeting_vertex(meeting_vertex_),radius(radius_) + {} + + bool operator<(const Net_filtration_vertex& other ) const{ + return radius < other.radius; + } + + }; + +public: + + + std::vector<Net_filtration_vertex> net_filtration_; + + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + Furthest_point_epsilon_net(SkBlComplex& complex): + complex_(complex) + { + if(!complex.empty()){ + init_filtration(); + for(int k = 2; k < net_filtration_.size(); ++k){ + update_radius_value(k); + } + } + } + + //xxx does not work if complex not full + double radius(Vertex_handle v){ + return net_filtration_[v.vertex].radius; + } + + + + +private: + + void init_filtration(){ + Vertex_handle v0 = *(complex_.vertex_range().begin()); + net_filtration_.reserve(complex_.num_vertices()); + for(auto v : complex_.vertex_range()){ + if(v != v0) + net_filtration_.push_back( + Net_filtration_vertex(v, + Vertex_handle(-1), + squared_eucl_distance(v,v0)) + ); + } + net_filtration_.push_back(Net_filtration_vertex(v0,Vertex_handle(-1),1e10)); + auto n = net_filtration_.size(); + sort_filtration(n-1); + } + + void update_radius_value(int k){ + int n = net_filtration_.size(); + int index_to_update = n-k; + for(int i = 0; i< index_to_update; ++i){ + net_filtration_[i].radius = (std::min)(net_filtration_[i].radius , + squared_eucl_distance( + net_filtration_[i].vertex_handle, + net_filtration_[index_to_update].vertex_handle + ) + ); + } + sort_filtration(n-k); + } + + /** + * sort all i first elements. + */ + void sort_filtration(int i){ + std::sort(net_filtration_.begin(),net_filtration_.begin()+ i); + } + + double squared_eucl_distance(Vertex_handle v1,Vertex_handle v2) const{ + return std::sqrt(Geometry_trait::Squared_distance_d()( + complex_.point(v1),complex_.point(v2)) + ); + } + + void print_filtration() const{ + for(auto v : net_filtration_){ + std::cerr <<"v="<<v.vertex_handle<<"-> d="<<v.radius<<std::endl; + } + } + +}; + + + +#endif /* FURTHEST_POINT_EPSILON_NET_H_ */ diff --git a/src/GudhUI/utils/K_nearest_builder.h b/src/GudhUI/utils/K_nearest_builder.h new file mode 100644 index 00000000..4acc0fbf --- /dev/null +++ b/src/GudhUI/utils/K_nearest_builder.h @@ -0,0 +1,106 @@ +/* + * K_nearest_builder.h + * + * Created on: Sep 10, 2014 + * Author: dsalinas + */ + +#ifndef K_NEAREST_BUILDER_H_ +#define K_NEAREST_BUILDER_H_ + +#include <unordered_map> +#include <boost/iterator/iterator_facade.hpp> +#include <CGAL/Euclidean_distance.h> +#include <CGAL/Orthogonal_k_neighbor_search.h> +#include <CGAL/Search_traits_d.h> + +#include "utils/UI_utils.h" +#include "model/Complex_typedefs.h" + +template<typename SkBlComplex> class K_nearest_builder{ +private: + + //todo uggh no virtual delete operator in Point + // so do a composition asap + class Point_d_with_id : public Point{ + typedef Point Base; + public: + Complex::Vertex_handle vertex_handle; + Point_d_with_id(int d=0) : Point(d) {} +// Point_d_with_id(int d, const Origin &o) : Base(d,o) {} + + Point_d_with_id(int a, int b, int c = 1) : + Base(RT(a),RT(b),RT(c)) {} + Point_d_with_id(int a, int b, int c, int d) : + Base(RT(a),RT(b),RT(c),RT(d)) {} + + template <class InputIterator> + Point_d_with_id (int d, InputIterator first, InputIterator last) + : Base (d, first, last) {} + template <class InputIterator> + + Point_d_with_id(const Point_d_with_id &p) : Base(p) {} + Point_d_with_id(const Base& p) : Base(p) {} + Point_d_with_id(const Base& p,Complex::Vertex_handle v) : Base(p),vertex_handle(v) {} + + }; + + struct Kernel_with_id : public Geometry_trait{ + typedef Point_d_with_id Point_d; + }; + + + /** + * TODO wrap vertex handle in class passed to tree + */ + typedef Kernel_with_id K; + typedef typename K::Point_d Point_d; + typedef typename CGAL::Search_traits_d<K> TreeTraits; + typedef typename CGAL::Orthogonal_k_neighbor_search<TreeTraits> Neighbor_search; + typedef typename Neighbor_search::Tree Tree; + + SkBlComplex& complex_; +public: + + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + K_nearest_builder(SkBlComplex& complex,unsigned k):complex_(complex){ + complex.keep_only_vertices(); + compute_edges(k); + } + +private: + + + + double squared_eucl_distance(const Point& p1,const Point& p2) const{ + return Geometry_trait::Squared_distance_d()(p1,p2); + } + + void compute_edges(unsigned k){ + + std::list<Point_d_with_id> points_with_id; + for(auto v: complex_.vertex_range()){ + Point_d_with_id point_v(complex_.point(v),v); + points_with_id.push_back(point_v); + } + + Tree tree(points_with_id.begin(),points_with_id.end()); + + + for (auto p : complex_.vertex_range()){ + Neighbor_search search(tree, complex_.point(p),k+1); + for(auto it = ++search.begin(); it != search.end(); ++it){ + auto q = it->first.vertex_handle; + if (p != q && complex_.contains_vertex(p) && complex_.contains_vertex(q)) + complex_.add_edge(p,q); + } + } + } + + +}; + +#endif /* K_NEAREST_BUILDER_H_ */ diff --git a/src/GudhUI/utils/Lloyd_builder.h b/src/GudhUI/utils/Lloyd_builder.h new file mode 100644 index 00000000..db2a7973 --- /dev/null +++ b/src/GudhUI/utils/Lloyd_builder.h @@ -0,0 +1,78 @@ +/* + * Lloyd.h + * + * Created on: Sep 25, 2014 + * Author: dsalinas + */ + +#ifndef LLOYD_H_ +#define LLOYD_H_ + + +#include <vector> + +/** + * Iteratively puts every vertex at the center of its neighbors + */ +template<typename SkBlComplex> class Lloyd_builder{ +private: + SkBlComplex& complex_; + int dim; +public: + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + Lloyd_builder(SkBlComplex& complex,unsigned num_iterations):complex_(complex),dim(-1){ + if(!complex_.empty()){ + dim = get_dimension(); + while(num_iterations--){ + std::list<Point> new_points; + for(auto v : complex.vertex_range()) + new_points.push_back(barycenter_neighbors(v)); + + auto new_points_it = new_points.begin(); + for(auto v : complex.vertex_range()) + complex_.point(v) = *(new_points_it++); + } + } + } + +private: + + int get_dimension(){ + assert(!complex_.empty()); + for(auto v : complex_.vertex_range()) + return complex_.point(v).dimension(); + return -1; + } + + Point barycenter_neighbors(Vertex_handle v) const{ + if(complex_.degree(v)==0) + return complex_.point(v); + + std::vector<double> res(dim,0); + unsigned num_points = 0; + for(auto nv : complex_.vertex_range(v)){ + ++num_points; + const Point& point = complex_.point(nv); + assert(point.dimension() == dim); + for(int i = 0; i < point.dimension() ; ++i) + res[i] += point[i]; + } + for(auto& x : res) + x/= num_points; + return Point(dim,res.begin(),res.end()); + } + + + + double squared_eucl_distance(const Point& p1,const Point& p2) const{ + return Geometry_trait::Squared_distance_d()(p1,p2); + } + +}; + + +#endif /* LLOYD_H_ */ diff --git a/src/GudhUI/utils/MClock.h b/src/GudhUI/utils/MClock.h new file mode 100644 index 00000000..b5c7d191 --- /dev/null +++ b/src/GudhUI/utils/MClock.h @@ -0,0 +1,57 @@ +/* + * Clock.h + * + * Created on: Jun 17, 2014 + * Author: dsalinas + */ + +#ifndef CLOCK_H_ +#define CLOCK_H_ + +#include <sys/time.h> + + +class MClock{ + +public: + MClock(){ + end_called = false; + begin(); + } + + void begin() const{ + end_called = false; + gettimeofday(&startTime, NULL); + } + + void end() const{ + end_called = true; + gettimeofday(&endTime, NULL); + } + + friend std::ostream& operator<< (std::ostream& stream,const MClock& clock){ + // if(!clock.end_called) clock.end(); + if(!clock.end_called) stream << "end not called"; + else{ + long totalTime = (clock.endTime.tv_sec - clock.startTime.tv_sec) * 1000000L; + totalTime += (clock.endTime.tv_usec - clock.startTime.tv_usec); + stream << clock.num_seconds() <<"s"; + } + return stream; + + } + + double num_seconds() const{ + if(!end_called) end(); + long totalTime = (endTime.tv_sec - startTime.tv_sec) * 1000000L; + totalTime += (endTime.tv_usec - startTime.tv_usec); + return (totalTime / 1000L)/(double) 1000; + } + +private: + mutable struct timeval startTime, endTime; + mutable bool end_called; +}; + + +#endif /* CLOCK_H_ */ diff --git a/src/GudhUI/utils/Persistence_compute.h b/src/GudhUI/utils/Persistence_compute.h new file mode 100644 index 00000000..f7974287 --- /dev/null +++ b/src/GudhUI/utils/Persistence_compute.h @@ -0,0 +1,106 @@ +/* + * Persistence_compute.h + * Created on: Jan 26, 2015 + * 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (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_COMPUTE_H_ +#define PERSISTENCE_COMPUTE_H_ + + +#include "gudhi/graph_simplicial_complex.h" +#include "gudhi/Simplex_tree.h" +#include "gudhi/distance_functions.h" +#include "gudhi/Persistent_cohomology.h" +#include "gudhi/Persistent_cohomology/Multi_field.h" + + +struct Persistence_params{ + int p; + double threshold; + int max_dim; + double min_pers; + + Persistence_params(int p_,double th_,int max_dim_=10,double min_pers_=0) + :p(p_),threshold(th_),max_dim(max_dim_),min_pers(min_pers_){} +}; + + +/** + * Show persistence into output stream + */ +template<typename SkBlComplex> class Persistence_compute{ +private: + SkBlComplex& complex_; + std::ostream& stream_; +public: + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + + /** + * @brief Compute persistence + * parameters : + * unsigned dim_max + * double threshold + * int p for Z_p + */ + Persistence_compute(SkBlComplex& complex,std::ostream& stream,const Persistence_params& params): +// +// double threshold = 0.5,unsigned dim_max = 8): + complex_(complex),stream_(stream){ + + //for now everything is copied, todo boost adapt iterators to points of SkBlComplex instead of copying to an intial vector + typedef std::vector<double> Point_t; + std::vector< Point_t > points; + points.reserve(complex.num_vertices()); + for(auto v : complex.vertex_range()){ + const auto & pt = complex.point(v); + Point_t pt_to_add(pt.cartesian_begin(),pt.cartesian_end()); + points.emplace_back(std::move(pt_to_add)); + } + + + Graph_t prox_graph = compute_proximity_graph( points, params.threshold, euclidean_distance<Point_t> ); + Gudhi::Simplex_tree<> st; + st.insert_graph(prox_graph); + st.expansion( params.max_dim ); + + Gudhi::persistent_cohomology::Persistent_cohomology< Gudhi::Simplex_tree<>,Gudhi::persistent_cohomology::Field_Zp > pcoh (st); + pcoh.init_coefficients( params.p ); //initilizes the coefficient field for homology + pcoh.compute_persistent_cohomology( INFINITY ); //put params.min_persistence + stream_<<"persistence: \n"; + pcoh.output_diagram(stream_); + } + +private: + + +}; + + + + + + +#endif /* PERSISTENCE_COMPUTE_H_ */ diff --git a/src/GudhUI/utils/Rips_builder.h b/src/GudhUI/utils/Rips_builder.h new file mode 100644 index 00000000..9484f9ab --- /dev/null +++ b/src/GudhUI/utils/Rips_builder.h @@ -0,0 +1,56 @@ +/* + * Rips_builder.h + * + * Created on: Sep 10, 2014 + * Author: dsalinas + */ + +#ifndef RIPS_BUILDER_H_ +#define RIPS_BUILDER_H_ + +#include <boost/iterator/iterator_facade.hpp> + +#include "utils/UI_utils.h" +#include "model/Complex_typedefs.h" +#include <CGAL/Euclidean_distance.h> + +#include <CGAL/Orthogonal_k_neighbor_search.h> +#include <CGAL/Search_traits_d.h> + +template<typename SkBlComplex> class Rips_builder{ +private: + SkBlComplex& complex_; +public: + + /** + * @brief Modify complex to be the Rips complex + * of its points with offset alpha. + */ + Rips_builder(SkBlComplex& complex,double alpha):complex_(complex){ + complex.keep_only_vertices(); + if (alpha<=0) return; + compute_edges(alpha); + } + +private: + + + double squared_eucl_distance(const Point& p1,const Point& p2) const{ + return Geometry_trait::Squared_distance_d()(p1,p2); + } + + void compute_edges(double alpha){ + auto vertices = complex_.vertex_range(); + for(auto p = vertices.begin(); p!= vertices.end(); ++p){ + std::cout << *p << " "; std::cout.flush(); + for (auto q = p; ++q != vertices.end(); /**/) + if (squared_eucl_distance(complex_.point(*p),complex_.point(*q)) < 4*alpha*alpha) + complex_.add_edge(*p,*q); + } + std::cout << std::endl; + } + +}; + + +#endif /* RIPS_BUILDER_H_ */ diff --git a/src/GudhUI/utils/UI_utils.h b/src/GudhUI/utils/UI_utils.h new file mode 100644 index 00000000..a7c0689f --- /dev/null +++ b/src/GudhUI/utils/UI_utils.h @@ -0,0 +1,33 @@ +/* + * UI_utils.h + * + * Created on: Aug 25, 2014 + * Author: david + */ + +#ifndef UI_UTILS_H_ +#define UI_UTILS_H_ + +#define PRINT(a) std::cerr << #a << ": " << (a) << " (DISP)"<<std::endl + +#define UIDBG_VERBOSE + + +#ifdef UIDBG_VERBOSE +#define UIDBG(a) std::cerr << "UIDBG: " << (a)<<std::endl +#define UIDBGMSG(a,b) std::cerr << "UIDBG: " << a<<b<<std::endl +#define UIDBGVALUE(a) std::cerr << "UIDBG: " << #a << ": " << a<<std::endl +#define UIDBGCONT(a) std::cerr << "UIDBG: container "<< #a<<" -> "; for(auto x:a) std::cerr<< x << ","; std::cerr<<std::endl +#else +//#define DBG(a) a +//#define DBGMSG(a,b) b +//#define DBGVALUE(a) a +//#define DBGCONT(a) a +#define UIDBG(a) +#define UIDBGMSG(a,b) +#define UIDBGVALUE(a) +#define UIDBGCONT(a) +#endif + + +#endif /* UI_UTILS_H_ */ diff --git a/src/GudhUI/utils/Vertex_collapsor.h b/src/GudhUI/utils/Vertex_collapsor.h new file mode 100644 index 00000000..d4911a35 --- /dev/null +++ b/src/GudhUI/utils/Vertex_collapsor.h @@ -0,0 +1,76 @@ +/* + * Vertex_collapsor.h + * + * Created on: Sep 25, 2014 + * Author: dsalinas + */ + +#ifndef VERTEX_COLLAPSOR_H_ +#define VERTEX_COLLAPSOR_H_ + +#include "utils/Edge_contractor.h" +#include "utils/Furthest_point_epsilon_net.h" +#include "utils/UI_utils.h" +/** + * Iteratively puts every vertex at the center of its neighbors + */ +template<typename SkBlComplex> class Vertex_collapsor{ +private: + SkBlComplex& complex_; + size_t num_collapses_; +public: + typedef typename SkBlComplex::Vertex_handle Vertex_handle; + typedef typename SkBlComplex::Edge_handle Edge_handle; + + /** + * @brief Modify complex to be the expansion of the k-nearest neighbor + * symetric graph. + */ + Vertex_collapsor(SkBlComplex& complex, size_t num_collapses) : + complex_(complex),num_collapses_(num_collapses) + { +// std::list<Vertex_handle> vertices; +// vertices.insert(vertices.begin(),complex_.vertex_range().begin(),complex_.vertex_range().end()); +// UIDBG("Collapse vertices"); +// collapse_vertices(vertices); + + std::list<Vertex_handle> vertices; + + UIDBG("Compute eps net"); + Furthest_point_epsilon_net<Complex> eps_net(complex_); + + for(auto vh : eps_net.net_filtration_) + vertices.push_back(vh.vertex_handle); + + UIDBG("Collapse vertices"); + collapse_vertices(vertices); + + + + } + +private: + + + void collapse_vertices(std::list<Vertex_handle>& vertices){ + while(!vertices.empty() && num_collapses_--){ + Vertex_handle current_vertex = vertices.front(); + vertices.pop_front(); + if(is_link_reducible(current_vertex)) + complex_.remove_vertex(current_vertex); + } + } + + bool is_link_reducible(Vertex_handle v){ + auto link = complex_.link(v); + if(link.empty()) return false; + if(link.is_cone()) return true; + if(link.num_connected_components()>1) return false; + Edge_contractor<Complex> contractor(link,link.num_vertices()-1); + return (link.num_vertices()==1); + } + +}; + + +#endif /* VERTEX_COLLAPSOR_H_ */ diff --git a/src/GudhUI/utils/homsimpl b/src/GudhUI/utils/homsimpl Binary files differnew file mode 100755 index 00000000..12227502 --- /dev/null +++ b/src/GudhUI/utils/homsimpl |