Merge GudhUI, a UI for gudhi based on Qt

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@427 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 17fedd974f14a8225b27d94361e835964eeb5cba

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
new file mode 100755
index 00000000..12227502
--- /dev/null
+++ b/src/GudhUI/utils/homsimpl