diff options
Diffstat (limited to 'src/Contraction')
16 files changed, 1323 insertions, 1343 deletions
diff --git a/src/Contraction/example/Garland_heckbert.cpp b/src/Contraction/example/Garland_heckbert.cpp index a41f65aa..70f29b6a 100644 --- a/src/Contraction/example/Garland_heckbert.cpp +++ b/src/Contraction/example/Garland_heckbert.cpp @@ -1,7 +1,4 @@ -/* - * Garland_heckbert.h - * Created on: Feb 10, 2015 - * This file is part of the Gudhi Library. The Gudhi library +/* This file is part of the Gudhi Library. The Gudhi library * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * @@ -28,12 +25,13 @@ #ifndef GARLAND_HECKBERT_H_ #define GARLAND_HECKBERT_H_ +#include <gudhi/Point.h> +#include <gudhi/Edge_contraction.h> +#include <gudhi/Skeleton_blocker.h> +#include <gudhi/Off_reader.h> + #include <boost/timer/timer.hpp> #include <iostream> -#include "gudhi/Point.h" -#include "gudhi/Edge_contraction.h" -#include "gudhi/Skeleton_blocker.h" -#include "gudhi/Off_reader.h" #include "Garland_heckbert/Error_quadric.h" @@ -51,7 +49,6 @@ struct Geometry_trait { */ struct Garland_heckbert_traits : public Skeleton_blocker_simple_geometric_traits<Geometry_trait> { public: - struct Garland_heckbert_vertex : public Simple_geometric_vertex { Error_quadric<Geometry_trait::Point> quadric; }; @@ -68,6 +65,7 @@ typedef Skeleton_blocker_contractor<Complex> Complex_contractor; */ class GH_placement : public Gudhi::contraction::Placement_policy<EdgeProfile> { Complex& complex_; + public: typedef Gudhi::contraction::Placement_policy<EdgeProfile>::Placement_type Placement_type; @@ -91,8 +89,8 @@ class GH_placement : public Gudhi::contraction::Placement_policy<EdgeProfile> { */ class GH_cost : public Gudhi::contraction::Cost_policy<EdgeProfile> { Complex& complex_; - public: + public: typedef Gudhi::contraction::Cost_policy<EdgeProfile>::Cost_type Cost_type; GH_cost(Complex& complex) : complex_(complex) { } @@ -115,13 +113,13 @@ class GH_cost : public Gudhi::contraction::Cost_policy<EdgeProfile> { */ class GH_visitor : public Gudhi::contraction::Contraction_visitor<EdgeProfile> { Complex& complex_; - public: + public: GH_visitor(Complex& complex) : complex_(complex) { } - //Compute quadrics for every vertex v - //The quadric of v consists in the sum of quadric - //of every triangles passing through v weighted by its area + // Compute quadrics for every vertex v + // The quadric of v consists in the sum of quadric + // of every triangles passing through v weighted by its area void on_started(Complex & complex) override { for (auto v : complex.vertex_range()) { @@ -147,7 +145,8 @@ class GH_visitor : public Gudhi::contraction::Contraction_visitor<EdgeProfile> { int main(int argc, char *argv[]) { if (argc != 4) { - std::cerr << "Usage " << argv[0] << " input.off output.off N to load the file input.off, contract N edges and save the result to output.off.\n"; + std::cerr << "Usage " << argv[0] << " input.off output.off N to load the file input.off, contract N edges and save " + << "the result to output.off.\n"; return EXIT_FAILURE; } @@ -172,8 +171,7 @@ int main(int argc, char *argv[]) { new GH_cost(complex), new GH_placement(complex), contraction::make_link_valid_contraction<EdgeProfile>(), - new GH_visitor(complex) - ); + new GH_visitor(complex)); std::cout << "Contract " << num_contractions << " edges" << std::endl; contractor.contract_edges(num_contractions); @@ -183,7 +181,7 @@ int main(int argc, char *argv[]) { complex.num_edges() << " edges and" << complex.num_triangles() << " triangles." << std::endl; - //write simplified complex + // write simplified complex Skeleton_blocker_off_writer<Complex> off_writer(argv[2], complex); return EXIT_SUCCESS; @@ -191,4 +189,4 @@ int main(int argc, char *argv[]) { -#endif /* GARLAND_HECKBERT_H_ */ +#endif // GARLAND_HECKBERT_H_ diff --git a/src/Contraction/example/Garland_heckbert/Error_quadric.h b/src/Contraction/example/Garland_heckbert/Error_quadric.h index 72134c9d..a033aa00 100644 --- a/src/Contraction/example/Garland_heckbert/Error_quadric.h +++ b/src/Contraction/example/Garland_heckbert/Error_quadric.h @@ -1,164 +1,182 @@ -/*
- * Error_quadric.h
+/* This file is part of the Gudhi Library. The Gudhi library
+ * (Geometric Understanding in Higher Dimensions) is a generic C++
+ * library for computational topology.
*
- * Created on: 24 janv. 2014
- * Author: dsalinas
+ * 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 ERROR_QUADRIC_H_
#define ERROR_QUADRIC_H_
-#include <vector>
-#include <utility>
#include <boost/optional/optional.hpp>
+#include <vector>
+#include <utility>
-template <typename Point> class Error_quadric{
-private :
- double coeff[10];
-
-public :
- Error_quadric(){
- clear();
- }
-
- /**
- * Quadric corresponding to the L2 distance to the plane.
- *
- * According to the notation of Garland Heckbert, they
- * denote a quadric symetric matrix as :
- * Q = [ q11 q12 q13 q14]
- * [ q12 q22 q23 q24]
- * [ q13 q23 q33 q34]
- * [ q14 q24 q34 q44]
- *
- * which is represented by a vector with 10 elts that
- * are denoted ci for clarity with :
- * Q = [ c0 c1 c2 c3 ]
- * [ c1 c4 c5 c6 ]
- * [ c2 c5 c7 c8 ]
- * [ c3 c6 c8 c9 ]
- *
- * The constructor return the quadrics that represents
- * the squared distance to the plane defined by triangle p0,p1,p2
- * times the area of triangle p0,p1,p2.
- */
- Error_quadric(const Point & p0,const Point & p1,const Point & p2){
-
- Point normal(unit_normal(p0,p1,p2));
- double a=normal[0];
- double b=normal[1];
- double c=normal[2];
- double d= -a*p0[0]-b*p0[1]-c*p0[2];
- coeff[0] = a*a ;
- coeff[1] = a*b ;
- coeff[2] = a*c ;
- coeff[3] = a*d ;
- coeff[4] = b*b ;
- coeff[5] = b*c ;
- coeff[6] = b*d ;
- coeff[7] = c*c ;
- coeff[8] = c*d ;
- coeff[9] = d*d ;
-
- double area_p0p1p2 = std::sqrt(squared_area(p0,p1,p2));
- for(auto& x : coeff)
- x*= area_p0p1p2;
- }
-
-
- inline double squared_area(const Point& p0,const Point& p1,const Point& p2) {
- //if (x1,x2,x3) = p1-p0 and (y1,y2,y3) = p2-p0
- //then the squared area is = (u^2+v^2+w^2)/4
- //with: u = x2 * y3 - x3 * y2;
- // v = x3 * y1 - x1 * y3;
- // w = x1 * y2 - x2 * y1;
- Point p0p1(p1-p0);
- Point p0p2(p2-p0);
- double A = p0p1[1] * p0p2[2] - p0p1[2] * p0p2[1];
- double B = p0p1[2] * p0p2[0] - p0p1[0] * p0p2[2];
- double C = p0p1[0] * p0p2[1] - p0p1[1] * p0p2[0];
- return 1./4. * (A*A+B*B+C*C);
- }
-
-
- void clear(){
- for(auto& x:coeff)
- x=0;
- }
-
- Error_quadric& operator+=(const Error_quadric& other){
- if(this!=&other)
- for(int i = 0 ; i < 10; ++i)
- coeff[i] += other.coeff[i];
- return *this;
- }
-
- /**
- * @return The quadric quost defined by the scalar product v^T Q v where Q is the quadratic form of Garland/Heckbert
- */
- inline double cost(const Point& point) const{
- double cost =
- coeff[0]*point.x()*point.x()+coeff[4]*point.y()*point.y()+coeff[7]*point.z()*point.z()
- +2*(coeff[1]*point.x()*point.y()+coeff[5]*point.y()*point.z()+coeff[2]*point.z()*point.x())
- +2*(coeff[3]*point.x()+coeff[6]*point.y()+coeff[8]*point.z())
- +coeff[9];
- if(cost<0) return 0;
- else {
- return cost;
- }
- }
-
- inline double grad_determinant() const{
- return
- coeff[0] * coeff[4] * coeff[7]
- - coeff[0] * coeff[5] * coeff[5]
- - coeff[1] * coeff[1] * coeff[7]
- +2*coeff[1] * coeff[5] * coeff[2]
- - coeff[4] * coeff[2] * coeff[2];
- }
-
- /**
- * Return the point such that it minimizes the gradient of the quadric.
- * Det must be passed with the determinant value of the gradient (should be non zero).
- */
- inline Point solve_linear_gradient(double det) const{
- return Point({
- (-coeff[1]*coeff[5]*coeff[8]+coeff[1]*coeff[7]*coeff[6]+coeff[2]*coeff[8]*coeff[4]-coeff[2]*coeff[5]*coeff[6]-coeff[3]*coeff[4]*coeff[7]+coeff[3]*coeff[5]*coeff[5])/ det,
- (coeff[0]*coeff[5]*coeff[8]-coeff[0]*coeff[7]*coeff[6]-coeff[5]*coeff[2]*coeff[3]-coeff[1]*coeff[2]*coeff[8]+coeff[6]*coeff[2]*coeff[2]+coeff[1]*coeff[3]*coeff[7])/det,
- (-coeff[8]*coeff[0]*coeff[4]+coeff[8]*coeff[1]*coeff[1]+coeff[2]*coeff[3]*coeff[4]+coeff[5]*coeff[0]*coeff[6]-coeff[5]*coeff[1]*coeff[3]-coeff[1]*coeff[2]*coeff[6])/det
- });
- }
-
-
- /**
- * returns the point that minimizes the quadric.
- * It inverses the quadric if its determinant is higher that a given threshold .
- * If the determinant is lower than this value the returned value is uninitialized.
- */
- boost::optional<Point> min_cost(double scale=1) const{
- // const double min_determinant = 1e-4 * scale*scale;
- const double min_determinant = 1e-5;
- boost::optional<Point> pt_res;
- double det = grad_determinant();
- if (std::abs(det)>min_determinant)
- pt_res = solve_linear_gradient(det);
- return pt_res;
- }
-
- friend std::ostream& operator<< (std::ostream& stream, const Error_quadric& quadric) {
- stream << "\n[ "<<quadric.coeff[0]<<","<<quadric.coeff[1]<<","<<quadric.coeff[2]<<","<<quadric.coeff[3]<<";\n";
- stream << " "<<quadric.coeff[1]<<","<<quadric.coeff[4]<<","<<quadric.coeff[5]<<","<<quadric.coeff[6]<<";\n";
- stream << " "<<quadric.coeff[2]<<","<<quadric.coeff[5]<<","<<quadric.coeff[7]<<","<<quadric.coeff[8]<<";\n";
- stream << " "<<quadric.coeff[3]<<","<<quadric.coeff[6]<<","<<quadric.coeff[8]<<","<<quadric.coeff[9]<<"]";
- return stream;
- }
-
-
+template <typename Point> class Error_quadric {
+ private:
+ double coeff[10];
+
+ public:
+ Error_quadric() {
+ clear();
+ }
+
+ /**
+ * Quadric corresponding to the L2 distance to the plane.
+ *
+ * According to the notation of Garland Heckbert, they
+ * denote a quadric symetric matrix as :
+ * Q = [ q11 q12 q13 q14]
+ * [ q12 q22 q23 q24]
+ * [ q13 q23 q33 q34]
+ * [ q14 q24 q34 q44]
+ *
+ * which is represented by a vector with 10 elts that
+ * are denoted ci for clarity with :
+ * Q = [ c0 c1 c2 c3 ]
+ * [ c1 c4 c5 c6 ]
+ * [ c2 c5 c7 c8 ]
+ * [ c3 c6 c8 c9 ]
+ *
+ * The constructor return the quadrics that represents
+ * the squared distance to the plane defined by triangle p0,p1,p2
+ * times the area of triangle p0,p1,p2.
+ */
+ Error_quadric(const Point & p0, const Point & p1, const Point & p2) {
+ Point normal(unit_normal(p0, p1, p2));
+ double a = normal[0];
+ double b = normal[1];
+ double c = normal[2];
+ double d = -a * p0[0] - b * p0[1] - c * p0[2];
+ coeff[0] = a*a;
+ coeff[1] = a*b;
+ coeff[2] = a*c;
+ coeff[3] = a*d;
+ coeff[4] = b*b;
+ coeff[5] = b*c;
+ coeff[6] = b*d;
+ coeff[7] = c*c;
+ coeff[8] = c*d;
+ coeff[9] = d*d;
+
+ double area_p0p1p2 = std::sqrt(squared_area(p0, p1, p2));
+ for (auto& x : coeff)
+ x *= area_p0p1p2;
+ }
+
+ inline double squared_area(const Point& p0, const Point& p1, const Point& p2) {
+ // if (x1,x2,x3) = p1-p0 and (y1,y2,y3) = p2-p0
+ // then the squared area is = (u^2+v^2+w^2)/4
+ // with: u = x2 * y3 - x3 * y2;
+ // v = x3 * y1 - x1 * y3;
+ // w = x1 * y2 - x2 * y1;
+ Point p0p1(p1 - p0);
+ Point p0p2(p2 - p0);
+ double A = p0p1[1] * p0p2[2] - p0p1[2] * p0p2[1];
+ double B = p0p1[2] * p0p2[0] - p0p1[0] * p0p2[2];
+ double C = p0p1[0] * p0p2[1] - p0p1[1] * p0p2[0];
+ return 1. / 4. * (A * A + B * B + C * C);
+ }
+
+ void clear() {
+ for (auto& x : coeff)
+ x = 0;
+ }
+
+ Error_quadric& operator+=(const Error_quadric& other) {
+ if (this != &other) {
+ for (int i = 0; i < 10; ++i)
+ coeff[i] += other.coeff[i];
+ }
+ return *this;
+ }
+
+ /**
+ * @return The quadric quost defined by the scalar product v^T Q v where Q is the quadratic form of Garland/Heckbert
+ */
+ inline double cost(const Point& point) const {
+ double cost =
+ coeff[0] * point.x() * point.x() + coeff[4] * point.y() * point.y() + coeff[7] * point.z() * point.z()
+ + 2 * (coeff[1] * point.x() * point.y() + coeff[5] * point.y() * point.z() + coeff[2] * point.z() * point.x())
+ + 2 * (coeff[3] * point.x() + coeff[6] * point.y() + coeff[8] * point.z())
+ + coeff[9];
+ if (cost < 0) {
+ return 0;
+ } else {
+ return cost;
+ }
+ }
+
+ inline double grad_determinant() const {
+ return
+ coeff[0] * coeff[4] * coeff[7]
+ - coeff[0] * coeff[5] * coeff[5]
+ - coeff[1] * coeff[1] * coeff[7]
+ + 2 * coeff[1] * coeff[5] * coeff[2]
+ - coeff[4] * coeff[2] * coeff[2];
+ }
+
+ /**
+ * Return the point such that it minimizes the gradient of the quadric.
+ * Det must be passed with the determinant value of the gradient (should be non zero).
+ */
+ inline Point solve_linear_gradient(double det) const {
+ return Point({
+ (-coeff[1] * coeff[5] * coeff[8] + coeff[1] * coeff[7] * coeff[6] + coeff[2] * coeff[8] * coeff[4] -
+ coeff[2] * coeff[5] * coeff[6] - coeff[3] * coeff[4] * coeff[7] + coeff[3] * coeff[5] * coeff[5])
+ / det,
+ (coeff[0] * coeff[5] * coeff[8] - coeff[0] * coeff[7] * coeff[6] - coeff[5] * coeff[2] * coeff[3] -
+ coeff[1] * coeff[2] * coeff[8] + coeff[6] * coeff[2] * coeff[2] + coeff[1] * coeff[3] * coeff[7])
+ / det,
+ (-coeff[8] * coeff[0] * coeff[4] + coeff[8] * coeff[1] * coeff[1] + coeff[2] * coeff[3] * coeff[4] +
+ coeff[5] * coeff[0] * coeff[6] - coeff[5] * coeff[1] * coeff[3] - coeff[1] * coeff[2] * coeff[6])
+ / det
+ });
+ }
+
+ /**
+ * returns the point that minimizes the quadric.
+ * It inverses the quadric if its determinant is higher that a given threshold .
+ * If the determinant is lower than this value the returned value is uninitialized.
+ */
+ boost::optional<Point> min_cost(double scale = 1) const {
+ // const double min_determinant = 1e-4 * scale*scale;
+ const double min_determinant = 1e-5;
+ boost::optional<Point> pt_res;
+ double det = grad_determinant();
+ if (std::abs(det) > min_determinant)
+ pt_res = solve_linear_gradient(det);
+ return pt_res;
+ }
+
+ friend std::ostream& operator<<(std::ostream& stream, const Error_quadric& quadric) {
+ stream << "\n[ " << quadric.coeff[0] << "," << quadric.coeff[1] << "," << quadric.coeff[2] << "," <<
+ quadric.coeff[3] << ";\n";
+ stream << " " << quadric.coeff[1] << "," << quadric.coeff[4] << "," << quadric.coeff[5] << "," <<
+ quadric.coeff[6] << ";\n";
+ stream << " " << quadric.coeff[2] << "," << quadric.coeff[5] << "," << quadric.coeff[7] << "," <<
+ quadric.coeff[8] << ";\n";
+ stream << " " << quadric.coeff[3] << "," << quadric.coeff[6] << "," << quadric.coeff[8] << "," <<
+ quadric.coeff[9] << "]";
+ return stream;
+ }
};
-
-
-
-#endif /* ERROR_QUADRIC_H_ */
-
+#endif // ERROR_QUADRIC_H_
diff --git a/src/Contraction/example/Rips_contraction.cpp b/src/Contraction/example/Rips_contraction.cpp index bd0a8b8c..d21246ed 100644 --- a/src/Contraction/example/Rips_contraction.cpp +++ b/src/Contraction/example/Rips_contraction.cpp @@ -19,24 +19,23 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#include <gudhi/Edge_contraction.h> +#include <gudhi/Skeleton_blocker.h> +#include <gudhi/Off_reader.h> +#include <gudhi/Point.h> + #include <boost/timer/timer.hpp> #include <iostream> -#include "gudhi/Edge_contraction.h" -#include "gudhi/Skeleton_blocker.h" -#include "gudhi/Off_reader.h" -#include "gudhi/Point.h" using namespace std; using namespace Gudhi; using namespace skbl; using namespace contraction; - -struct Geometry_trait{ - typedef Point_d Point; +struct Geometry_trait { + typedef Point_d Point; }; - typedef Geometry_trait::Point Point; typedef Skeleton_blocker_simple_geometric_traits<Geometry_trait> Complex_geometric_traits; typedef Skeleton_blocker_geometric_complex< Complex_geometric_traits > Complex; @@ -44,62 +43,62 @@ typedef Edge_profile<Complex> Profile; typedef Skeleton_blocker_contractor<Complex> Complex_contractor; template<typename ComplexType> -void build_rips(ComplexType& complex, double offset){ - if (offset<=0) return; - auto vertices = complex.vertex_range(); - for (auto p = vertices.begin(); p != vertices.end(); ++p) - for (auto q = p; ++q != vertices.end(); /**/){ - if ( squared_dist(complex.point(*p), complex.point(*q)) < 4 * offset * offset) - complex.add_edge(*p,*q); - } +void build_rips(ComplexType& complex, double offset) { + if (offset <= 0) return; + auto vertices = complex.vertex_range(); + for (auto p = vertices.begin(); p != vertices.end(); ++p) + for (auto q = p; ++q != vertices.end(); /**/) { + if (squared_dist(complex.point(*p), complex.point(*q)) < 4 * offset * offset) + complex.add_edge(*p, *q); + } } -int main (int argc, char *argv[]) -{ - if (argc!=3){ - std::cerr << "Usage "<<argv[0]<<" ../../../data/meshes/SO3_10000.off 0.3 to load the file ../../data/SO3_10000.off and contract the Rips complex built with paremeter 0.3.\n"; - return -1; - } +int main(int argc, char *argv[]) { + if (argc != 3) { + std::cerr << "Usage " << argv[0] << " ../../../data/meshes/SO3_10000.off 0.3 to load the file " << + "../../data/SO3_10000.off and contract the Rips complex built with paremeter 0.3.\n"; + return -1; + } - Complex complex; + Complex complex; - // load only the points - Skeleton_blocker_off_reader<Complex> off_reader(argv[1],complex,true); - if(!off_reader.is_valid()){ - std::cerr << "Unable to read file:"<<argv[1]<<std::endl; - return EXIT_FAILURE; - } + // load only the points + Skeleton_blocker_off_reader<Complex> off_reader(argv[1], complex, true); + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file:" << argv[1] << std::endl; + return EXIT_FAILURE; + } - std::cout << "Build the Rips complex with "<<complex.num_vertices()<<" vertices"<<std::endl; + std::cout << "Build the Rips complex with " << complex.num_vertices() << " vertices" << std::endl; - build_rips(complex,atof(argv[2])); + build_rips(complex, atof(argv[2])); - boost::timer::auto_cpu_timer t; + boost::timer::auto_cpu_timer t; - std::cout << "Initial complex has "<< - complex.num_vertices()<<" vertices and "<< - complex.num_edges()<<" edges"<<std::endl; + std::cout << "Initial complex has " << + complex.num_vertices() << " vertices and " << + complex.num_edges() << " edges" << std::endl; - Complex_contractor contractor(complex, - new Edge_length_cost<Profile>, - contraction::make_first_vertex_placement<Profile>(), - contraction::make_link_valid_contraction<Profile>(), - contraction::make_remove_popable_blockers_visitor<Profile>()); - contractor.contract_edges(); + Complex_contractor contractor(complex, + new Edge_length_cost<Profile>, + contraction::make_first_vertex_placement<Profile>(), + contraction::make_link_valid_contraction<Profile>(), + contraction::make_remove_popable_blockers_visitor<Profile>()); + contractor.contract_edges(); - std::cout << "Counting final number of simplices \n"; - unsigned num_simplices = std::distance(complex.simplex_range().begin(),complex.simplex_range().end()); + std::cout << "Counting final number of simplices \n"; + unsigned num_simplices = std::distance(complex.simplex_range().begin(), complex.simplex_range().end()); - std::cout << "Final complex has "<< - complex.num_vertices()<<" vertices, "<< - complex.num_edges()<<" edges, "<< - complex.num_blockers()<<" blockers and "<< - num_simplices<<" simplices"<<std::endl; + std::cout << "Final complex has " << + complex.num_vertices() << " vertices, " << + complex.num_edges() << " edges, " << + complex.num_blockers() << " blockers and " << + num_simplices << " simplices" << std::endl; - std::cout << "Time to simplify and enumerate simplices:\n"; + std::cout << "Time to simplify and enumerate simplices:\n"; - return EXIT_SUCCESS; + return EXIT_SUCCESS; } diff --git a/src/Contraction/include/gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h b/src/Contraction/include/gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h index 10b89e13..5a55c513 100644 --- a/src/Contraction/include/gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h +++ b/src/Contraction/include/gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h @@ -16,76 +16,86 @@ // // Author(s) : Fernando Cacciola <fernando.cacciola@geometryfactory.com> // -#ifndef CGAL_MODIFIABLE_PRIORITY_QUEUE_H -#define CGAL_MODIFIABLE_PRIORITY_QUEUE_H +#ifndef CONTRACTION_CGAL_QUEUE_MODIFIABLE_PRIORITY_QUEUE_H_ +#define CONTRACTION_CGAL_QUEUE_MODIFIABLE_PRIORITY_QUEUE_H_ #define CGAL_SURFACE_MESH_SIMPLIFICATION_USE_RELAXED_HEAP -#include <climits> // Neeeded by the following Boost header for CHAR_BIT. #include <boost/optional.hpp> #include <boost/pending/relaxed_heap.hpp> -namespace CGAL { +#include <climits> // Neeeded by the following Boost header for CHAR_BIT. +#include <functional> // for less -template <class IndexedType_ - ,class Compare_ = std::less<IndexedType_> - ,class ID_ = boost::identity_property_map - > -class Modifiable_priority_queue -{ -public: +namespace CGAL { +template <class IndexedType_, class Compare_ = std::less<IndexedType_>, class ID_ = boost::identity_property_map> +class Modifiable_priority_queue { + public: typedef Modifiable_priority_queue Self; - - typedef IndexedType_ IndexedType ; - typedef Compare_ Compare; - typedef ID_ ID ; - - typedef boost::relaxed_heap<IndexedType,Compare,ID> Heap; + + typedef IndexedType_ IndexedType; + typedef Compare_ Compare; + typedef ID_ ID; + + typedef boost::relaxed_heap<IndexedType, Compare, ID> Heap; typedef typename Heap::value_type value_type; - typedef typename Heap::size_type size_type; - - typedef bool handle ; - -public: - - Modifiable_priority_queue( size_type largest_ID, Compare const& c, ID const& id ) : mHeap(largest_ID,c,id) {} - - handle push ( value_type const& v ) { mHeap.push(v) ; return handle(true) ; } - - handle update ( value_type const& v, handle h ) { mHeap.update(v); return h ; } - - handle erase ( value_type const& v, handle ) { mHeap.remove(v); return null_handle() ; } - - value_type top() const { return mHeap.top() ; } - - void pop() { mHeap.pop(); } - - bool empty() const { return mHeap.empty() ; } - - bool contains ( value_type const& v ) { return mHeap.contains(v) ; } - - boost::optional<value_type> extract_top() - { - boost::optional<value_type> r ; - if ( !empty() ) - { + typedef typename Heap::size_type size_type; + + typedef bool handle; + + public: + Modifiable_priority_queue(size_type largest_ID, Compare const& c, ID const& id) : mHeap(largest_ID, c, id) { } + + handle push(value_type const& v) { + mHeap.push(v); + return handle(true); + } + + handle update(value_type const& v, handle h) { + mHeap.update(v); + return h; + } + + handle erase(value_type const& v, handle) { + mHeap.remove(v); + return null_handle(); + } + + value_type top() const { + return mHeap.top(); + } + + void pop() { + mHeap.pop(); + } + + bool empty() const { + return mHeap.empty(); + } + + bool contains(value_type const& v) { + return mHeap.contains(v); + } + + boost::optional<value_type> extract_top() { + boost::optional<value_type> r; + if (!empty()) { value_type v = top(); pop(); - r = boost::optional<value_type>(v) ; - } - return r ; + r = boost::optional<value_type>(v); + } + return r; + } + + static handle null_handle() { + return handle(false); } - - static handle null_handle() { return handle(false); } - -private: - Heap mHeap ; - -} ; + private: + Heap mHeap; +}; -} //namespace CGAL +} // namespace CGAL -#endif - +#endif // CONTRACTION_CGAL_QUEUE_MODIFIABLE_PRIORITY_QUEUE_H_ diff --git a/src/Contraction/include/gudhi/Contraction/Edge_profile.h b/src/Contraction/include/gudhi/Contraction/Edge_profile.h index f90bd71a..e4910b27 100644 --- a/src/Contraction/include/gudhi/Contraction/Edge_profile.h +++ b/src/Contraction/include/gudhi/Contraction/Edge_profile.h @@ -1,130 +1,130 @@ - /* 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-Mediterranee (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 GUDHI_EDGE_PROFILE_H_ -#define GUDHI_EDGE_PROFILE_H_ -//#include "combinatorics/Skeleton_blocker/Simplex.h" - - -namespace Gudhi{ +/* 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-Mediterranee (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 CONTRACTION_EDGE_PROFILE_H_ +#define CONTRACTION_EDGE_PROFILE_H_ + +#include <ostream> + +namespace Gudhi { namespace contraction { -template<typename GeometricSimplifiableComplex> class Edge_profile{ -public: - typedef GeometricSimplifiableComplex Complex; - typedef typename Complex::GT GT; +template<typename GeometricSimplifiableComplex> class Edge_profile { + public: + typedef GeometricSimplifiableComplex Complex; + typedef typename Complex::GT GT; - typedef typename GeometricSimplifiableComplex::Vertex_handle Vertex_handle; - typedef typename GeometricSimplifiableComplex::Root_vertex_handle Root_vertex_handle; + typedef typename GeometricSimplifiableComplex::Vertex_handle Vertex_handle; + typedef typename GeometricSimplifiableComplex::Root_vertex_handle Root_vertex_handle; - typedef typename GeometricSimplifiableComplex::Edge_handle Edge_handle; - typedef typename GeometricSimplifiableComplex::Graph_vertex Graph_vertex; - typedef typename GeometricSimplifiableComplex::Graph_edge Graph_edge; - typedef typename GeometricSimplifiableComplex::Point Point; + typedef typename GeometricSimplifiableComplex::Edge_handle Edge_handle; + typedef typename GeometricSimplifiableComplex::Graph_vertex Graph_vertex; + typedef typename GeometricSimplifiableComplex::Graph_edge Graph_edge; + typedef typename GeometricSimplifiableComplex::Point Point; + Edge_profile(GeometricSimplifiableComplex& complex, Edge_handle edge) : complex_(complex), edge_handle_(edge), + v0_(complex_.first_vertex(edge_handle_)), v1_(complex_.second_vertex(edge_handle_)) { + assert(complex_.get_address(complex_[edge_handle_].first())); + assert(complex_.get_address(complex_[edge_handle_].second())); + assert(complex_.contains_edge(v0_handle(), v1_handle())); + assert(v0_handle() != v1_handle()); + } + virtual ~Edge_profile() { } + GeometricSimplifiableComplex& complex() const { + return complex_; + } - Edge_profile( GeometricSimplifiableComplex& complex,Edge_handle edge):complex_(complex),edge_handle_(edge), - v0_(complex_.first_vertex(edge_handle_)),v1_(complex_.second_vertex(edge_handle_)) -{ - assert(complex_.get_address(complex_[edge_handle_].first())); - assert(complex_.get_address(complex_[edge_handle_].second())); - assert(complex_.contains_edge(v0_handle(),v1_handle())); - assert(v0_handle() != v1_handle()); -} + Edge_handle edge_handle() const { + return edge_handle_; + } - virtual ~Edge_profile(){ } + Graph_edge& edge() const { + return complex_[edge_handle_]; + } + Graph_vertex& v0() const { + return complex_[v0_handle()]; + } - GeometricSimplifiableComplex& complex() const { - return complex_; - } + Graph_vertex& v1() const { + return complex_[v1_handle()]; + } - Edge_handle edge_handle() const{ - return edge_handle_; - } + Vertex_handle v0_handle() const { + return v0_; + // Root_vertex_handle root = complex_[edge_handle_].first(); + // assert(complex_.get_address(root)); + // return *complex_.get_address(root); + } - Graph_edge& edge() const{ - return complex_[edge_handle_]; - } + Vertex_handle v1_handle() const { + return v1_; + // Root_vertex_handle root = complex_[edge_handle_].second(); + // assert(complex_.get_address(root)); + // return *complex_.get_address(root); + } + const Point& p0() const { + return complex_.point(v0_handle()); + } - Graph_vertex& v0() const{return complex_[v0_handle()];} - Graph_vertex& v1() const{return complex_[v1_handle()];} + const Point& p1() const { + return complex_.point(v1_handle()); + } + friend std::ostream& operator<<(std::ostream& o, const Edge_profile& v) { + return o << "v0:" << v.v0_handle() << " v1:" << v.v1_handle(); + } - Vertex_handle v0_handle() const{ - return v0_; -// Root_vertex_handle root = complex_[edge_handle_].first(); -// assert(complex_.get_address(root)); -// return *complex_.get_address(root); - } + private: + GeometricSimplifiableComplex& complex_; - Vertex_handle v1_handle() const{ - return v1_; -// Root_vertex_handle root = complex_[edge_handle_].second(); -// assert(complex_.get_address(root)); -// return *complex_.get_address(root); - } + Edge_handle edge_handle_; - const Point& p0() const {return complex_.point(v0_handle());} + Vertex_handle v0_; - const Point& p1() const {return complex_.point(v1_handle());} - - friend std::ostream& operator << (std::ostream& o, const Edge_profile & v){ - o << "v0:"<<v.v0_handle() << " v1:"<<v.v1_handle(); - return o; - } -private: - - GeometricSimplifiableComplex& complex_; - - Edge_handle edge_handle_; - - Vertex_handle v0_; + Vertex_handle v1_; +}; - Vertex_handle v1_; +template<typename EdgeProfile> class Edge_profile_factory { + public: + typedef typename EdgeProfile::Edge_handle Edge_handle_; + typedef typename EdgeProfile::Complex Complex_; -}; + virtual EdgeProfile make_profile( + Complex_& complex, + Edge_handle_ edge) const { + return EdgeProfile(complex, edge); + } -template<typename EdgeProfile> class Edge_profile_factory{ -public: - typedef typename EdgeProfile::Edge_handle Edge_handle_; - typedef typename EdgeProfile::Complex Complex_; - virtual EdgeProfile make_profile( - Complex_& complex, - Edge_handle_ edge) const{ - return EdgeProfile(complex,edge); - } - - virtual ~Edge_profile_factory(){}; + virtual ~Edge_profile_factory() { } }; - } // namespace contraction -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_EDGE_PROFILE_H_ */ +#endif // CONTRACTION_EDGE_PROFILE_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h b/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h index b8b1e87a..7ee05aad 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h @@ -1,32 +1,32 @@ - /* 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-Mediterranee (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 GUDHI_CONTRACTION_VISITOR_H_ -#define GUDHI_CONTRACTION_VISITOR_H_ - -#include "gudhi/Contraction/Edge_profile.h" -#include "boost/optional.hpp" - -namespace Gudhi{ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_CONTRACTION_VISITOR_H_ +#define CONTRACTION_POLICIES_CONTRACTION_VISITOR_H_ + +#include <gudhi/Contraction/Edge_profile.h> +#include <boost/optional.hpp> + +namespace Gudhi { namespace contraction { @@ -36,66 +36,56 @@ namespace contraction { *@ingroup contr */ template <typename EdgeProfile> -class Contraction_visitor {//: public Dummy_complex_visitor<typename EdgeProfile::Vertex_handle> { -public: - //typedef typename ComplexType::GeometryTrait GT; - typedef EdgeProfile Profile; - typedef double FT; - typedef typename Profile::Complex Complex; - typedef Complex ComplexType; - typedef typename ComplexType::Point Point; - - - virtual ~Contraction_visitor(){}; - - /** - * @brief Called before the edge contraction process starts. - */ - virtual void on_started (ComplexType & complex){} - - /** - * @brief Called when the algorithm stops. - */ - virtual void on_stop_condition_reached (){} - - - /** - * @brief Called during the collecting phase (when a cost is assigned to the edges), for each edge collected. - */ - virtual void on_collected (const Profile &profile, boost::optional< FT > cost){} - - /** - * @brief Called during the processing phase (when edges are contracted), for each edge that is selected. - */ - virtual void on_selected (const Profile &profile, boost::optional< FT > cost, int initial_count, int current_count){} - - - /** - * @brief Called when an edge is about to be contracted and replaced by a vertex whose position is *placement. - */ - virtual void on_contracting(const Profile &profile, boost::optional< Point > placement){ - } - - - - /** - * @brief Called when after an edge has been contracted onto a new point placement. - * A possibility would to remove popable blockers at this point for instance. - */ - virtual void on_contracted(const Profile &profile, boost::optional< Point > placement){ - - } - - - /** - * @brief Called for each selected edge which cannot be contracted because the ValidContractionPredicate is false - */ - virtual void on_non_valid(const Profile &profile){} - +class Contraction_visitor { // : public Dummy_complex_visitor<typename EdgeProfile::Vertex_handle> { + public: + // typedef typename ComplexType::GeometryTrait GT; + typedef EdgeProfile Profile; + typedef double FT; + typedef typename Profile::Complex Complex; + typedef Complex ComplexType; + typedef typename ComplexType::Point Point; + + virtual ~Contraction_visitor() { } + + /** + * @brief Called before the edge contraction process starts. + */ + virtual void on_started(ComplexType & complex) { } + + /** + * @brief Called when the algorithm stops. + */ + virtual void on_stop_condition_reached() { } + + /** + * @brief Called during the collecting phase (when a cost is assigned to the edges), for each edge collected. + */ + virtual void on_collected(const Profile &profile, boost::optional< FT > cost) { } + + /** + * @brief Called during the processing phase (when edges are contracted), for each edge that is selected. + */ + virtual void on_selected(const Profile &profile, boost::optional< FT > cost, int initial_count, int current_count) { } + + /** + * @brief Called when an edge is about to be contracted and replaced by a vertex whose position is *placement. + */ + virtual void on_contracting(const Profile &profile, boost::optional< Point > placement) { } + + /** + * @brief Called when after an edge has been contracted onto a new point placement. + * A possibility would to remove popable blockers at this point for instance. + */ + virtual void on_contracted(const Profile &profile, boost::optional< Point > placement) { } + + /** + * @brief Called for each selected edge which cannot be contracted because the ValidContractionPredicate is false + */ + virtual void on_non_valid(const Profile &profile) { } }; } // namespace contraction -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_CONTRACTION_VISITOR_H_ */ +#endif // CONTRACTION_POLICIES_CONTRACTION_VISITOR_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h b/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h index 3cb18c86..f4d343ec 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h @@ -1,51 +1,53 @@ - /* 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-Mediterranee (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 GUDHI_COST_POLICY_H_ -#define GUDHI_COST_POLICY_H_ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_COST_POLICY_H_ +#define CONTRACTION_POLICIES_COST_POLICY_H_ #include <boost/optional.hpp> -namespace Gudhi{ +namespace Gudhi { namespace contraction { /** -*@brief Policy to specify the cost of contracting an edge. + *@brief Policy to specify the cost of contracting an edge. *@ingroup contr -*/ -template< typename EdgeProfile> class Cost_policy{ -public: - typedef typename EdgeProfile::Point Point; - typedef typename EdgeProfile::Graph_vertex Graph_vertex; + */ +template< typename EdgeProfile> +class Cost_policy { + public: + typedef typename EdgeProfile::Point Point; + typedef typename EdgeProfile::Graph_vertex Graph_vertex; - typedef boost::optional<double> Cost_type; + typedef boost::optional<double> Cost_type; - virtual Cost_type operator()(const EdgeProfile& profile, const boost::optional<Point>& placement) const =0; - virtual ~Cost_policy(){ - }; + virtual Cost_type operator()(const EdgeProfile& profile, const boost::optional<Point>& placement) const = 0; + + virtual ~Cost_policy() { } }; } // namespace contraction -} // namespace GUDHI -#endif /* GUDHI_COST_POLICY_H_ */ +} // namespace Gudhi + +#endif // CONTRACTION_POLICIES_COST_POLICY_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h index de473944..5d329496 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h @@ -1,51 +1,49 @@ - /* 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-Mediterranee (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 GUDHI_DUMMY_VALID_CONTRACTION_H_ -#define GUDHI_DUMMY_VALID_CONTRACTION_H_ - -#include "Valid_contraction_policy.h" - -namespace Gudhi{ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_DUMMY_VALID_CONTRACTION_H_ +#define CONTRACTION_POLICIES_DUMMY_VALID_CONTRACTION_H_ + +#include <gudhi/Contraction/policies/Valid_contraction_policy.h> + +namespace Gudhi { namespace contraction { - - - /** - *@brief Policy that accept all edge contraction. - */ -template< typename EdgeProfile> class Dummy_valid_contraction : public Valid_contraction_policy<EdgeProfile>{ -public: - typedef typename EdgeProfile::Point Point; - bool operator()(const EdgeProfile& profile,const boost::optional<Point>& placement){ - return true; - } +/** + *@brief Policy that accept all edge contraction. + */ +template< typename EdgeProfile> +class Dummy_valid_contraction : public Valid_contraction_policy<EdgeProfile> { + public: + typedef typename EdgeProfile::Point Point; + + bool operator()(const EdgeProfile& profile, const boost::optional<Point>& placement) { + return true; + } }; } // namespace contraction -} // namespace GUDHI - - +} // namespace Gudhi -#endif /* GUDHI_DUMMY_VALID_CONTRACTION_H_ */ +#endif // CONTRACTION_POLICIES_DUMMY_VALID_CONTRACTION_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h b/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h index b22ada0d..dac2d448 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h @@ -1,56 +1,56 @@ - /* 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-Mediterranee (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 GUDHI_EDGE_LENGTH_COST_H_ -#define GUDHI_EDGE_LENGTH_COST_H_ - -#include "Cost_policy.h" - -namespace Gudhi{ +/* 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-Mediterranee (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/>. + */ -namespace contraction { +#ifndef CONTRACTION_POLICIES_EDGE_LENGTH_COST_H_ +#define CONTRACTION_POLICIES_EDGE_LENGTH_COST_H_ + +#include <gudhi/Contraction/policies/Cost_policy.h> +namespace Gudhi { + +namespace contraction { /** * @brief return a cost corresponding to the squared length of the edge */ -template< typename EdgeProfile> class Edge_length_cost : public Cost_policy<EdgeProfile>{ -public: - typedef typename 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{ - double res = 0; - auto p0_coord = profile.p0().begin(); - auto p1_coord = profile.p1().begin(); - for(; p0_coord != profile.p0().end(); p0_coord++, p1_coord++){ - res += (*p0_coord - *p1_coord) * (*p0_coord - *p1_coord); - } - return res; - } - +template< typename EdgeProfile> +class Edge_length_cost : public Cost_policy<EdgeProfile> { + public: + typedef typename 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 { + double res = 0; + auto p0_coord = profile.p0().begin(); + auto p1_coord = profile.p1().begin(); + for (; p0_coord != profile.p0().end(); p0_coord++, p1_coord++) { + res += (*p0_coord - *p1_coord) * (*p0_coord - *p1_coord); + } + return res; + } }; } // namespace contraction -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_EDGE_LENGTH_COST_H_ */ +#endif // CONTRACTION_POLICIES_EDGE_LENGTH_COST_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h b/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h index 93abac35..1f68db0d 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h +++ b/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h @@ -1,53 +1,52 @@ - /* 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-Mediterranee (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 GUDHI_FIRST_VERTEX_PLACEMENT_H_ -#define GUDHI_FIRST_VERTEX_PLACEMENT_H_ - -#include "Placement_policy.h" - -namespace Gudhi{ +/* 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-Mediterranee (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/>. + */ -namespace contraction { +#ifndef CONTRACTION_POLICIES_FIRST_VERTEX_PLACEMENT_H_ +#define CONTRACTION_POLICIES_FIRST_VERTEX_PLACEMENT_H_ + +#include <gudhi/Contraction/policies/Placement_policy.h> + +namespace Gudhi { +namespace contraction { /** * @brief Places the contracted point onto the first point of the edge */ -template< typename EdgeProfile> class First_vertex_placement : public Placement_policy<EdgeProfile>{ - -public: - typedef typename EdgeProfile::Point Point; - typedef typename EdgeProfile::Edge_handle Edge_handle; +template< typename EdgeProfile> +class First_vertex_placement : public Placement_policy<EdgeProfile> { + public: + typedef typename EdgeProfile::Point Point; + typedef typename EdgeProfile::Edge_handle Edge_handle; - typedef typename Placement_policy<EdgeProfile>::Placement_type Placement_type; + typedef typename Placement_policy<EdgeProfile>::Placement_type Placement_type; - Placement_type operator()(const EdgeProfile& profile) const override{ - return Placement_type(profile.p0()); - } + Placement_type operator()(const EdgeProfile& profile) const override { + return Placement_type(profile.p0()); + } }; -} // namespace contraction -} // namespace GUDHI +} // namespace contraction +} // namespace Gudhi -#endif /* GUDHI_FIRST_VERTEX_PLACEMENT_H_ */ +#endif // CONTRACTION_POLICIES_FIRST_VERTEX_PLACEMENT_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h index c901e629..919df243 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h @@ -1,54 +1,56 @@ - /* 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-Mediterranee (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 GUDHI_LINK_CONDITION_VALID_CONTRACTION_H_ -#define GUDHI_LINK_CONDITION_VALID_CONTRACTION_H_ - -#include "gudhi/Utils.h" -#include "Valid_contraction_policy.h" - - -namespace Gudhi{ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ +#define CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ + +#include <gudhi/Utils.h> +#include <gudhi/Contraction/policies/Valid_contraction_policy.h> + + +namespace Gudhi { namespace contraction { - - /** - *@brief Policy that only accept edges verifying the link condition (and therefore whose contraction preserving homotopy type). - *@ingroup contr - */ -template< typename EdgeProfile> class Link_condition_valid_contraction : public Valid_contraction_policy<EdgeProfile>{ -public: - typedef typename EdgeProfile::Edge_handle Edge_handle; - typedef typename EdgeProfile::Point Point; - //typedef typename EdgeProfile::Edge_handle Edge_handle; - bool operator()(const EdgeProfile& profile,const boost::optional<Point>& placement) const override{ - Edge_handle edge(profile.edge_handle()); - DBGMSG("Link_condition_valid_contraction:",profile.complex().link_condition(edge)); - return profile.complex().link_condition(edge); - } +/** + *@brief Policy that only accept edges verifying the link condition (and therefore whose contraction preserving homotopy type). + *@ingroup contr + */ +template< typename EdgeProfile> +class Link_condition_valid_contraction : public Valid_contraction_policy<EdgeProfile> { + public: + typedef typename EdgeProfile::Edge_handle Edge_handle; + typedef typename EdgeProfile::Point Point; + // typedef typename EdgeProfile::Edge_handle Edge_handle; + + bool operator()(const EdgeProfile& profile, const boost::optional<Point>& placement) const override { + Edge_handle edge(profile.edge_handle()); + DBGMSG("Link_condition_valid_contraction:", profile.complex().link_condition(edge)); + return profile.complex().link_condition(edge); + } }; + } // namespace contraction -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_LINK_CONDITION_VALID_CONTRACTION_H_ */ +#endif // CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h b/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h index 30f0a570..4b59f1b5 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h @@ -1,52 +1,51 @@ - /* 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-Mediterranee (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 GUDHI_MIDDLE_PLACEMENT_H_ -#define GUDHI_MIDDLE_PLACEMENT_H_ - -#include "Placement_policy.h" - - -namespace Gudhi{ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_MIDDLE_PLACEMENT_H_ +#define CONTRACTION_POLICIES_MIDDLE_PLACEMENT_H_ + +#include <gudhi/Contraction/policies/Placement_policy.h> + +namespace Gudhi { namespace contraction { +template< typename EdgeProfile> +class Middle_placement : public Placement_policy<EdgeProfile> { + public: + typedef typename EdgeProfile::Point Point; + typedef typename EdgeProfile::Edge_handle Edge_handle; + typedef typename EdgeProfile::Graph_vertex Graph_vertex; - -template< typename EdgeProfile> class Middle_placement : public Placement_policy<EdgeProfile>{ + typedef typename Placement_policy<EdgeProfile>::Placement_type Placement_type; -public: - typedef typename EdgeProfile::Point Point; - typedef typename EdgeProfile::Edge_handle Edge_handle; - typedef typename EdgeProfile::Graph_vertex Graph_vertex; - - typedef typename Placement_policy<EdgeProfile>::Placement_type Placement_type; - - Placement_type operator()(const EdgeProfile& profile) const override{ - //todo compute the middle - return Placement_type(profile.p0()); - } + Placement_type operator()(const EdgeProfile& profile) const override { + // todo compute the middle + return Placement_type(profile.p0()); + } }; + } // namespace contraction -} // namespace GUDHI -#endif /* GUDHI_MIDDLE_PLACEMENT_H_ */ +} // namespace Gudhi + +#endif // CONTRACTION_POLICIES_MIDDLE_PLACEMENT_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h b/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h index 3a804cf0..34ffa49f 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h @@ -1,49 +1,51 @@ - /* 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-Mediterranee (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 GUDHI_PLACEMENT_POLICY_H_ -#define GUDHI_PLACEMENT_POLICY_H_ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_PLACEMENT_POLICY_H_ +#define CONTRACTION_POLICIES_PLACEMENT_POLICY_H_ #include <boost/optional.hpp> namespace Gudhi { + namespace contraction { +/** + *@brief Policy to specify where the merged point had to be placed after an edge contraction. + *@ingroup contr + */ +template< typename EdgeProfile> +class Placement_policy { + public: + typedef typename EdgeProfile::Point Point; + typedef boost::optional<Point> Placement_type; - /** - *@brief Policy to specify where the merged point had to be placed after an edge contraction. - *@ingroup contr - */ -template< typename EdgeProfile> class Placement_policy{ -public: - typedef typename EdgeProfile::Point Point; - typedef boost::optional<Point> Placement_type; + virtual Placement_type operator()(const EdgeProfile& profile) const = 0; - virtual Placement_type operator()(const EdgeProfile& profile) const=0; - virtual ~Placement_policy(){}; + virtual ~Placement_policy() { } }; - } // namespace contraction -} // namespace GUDHI -#endif /* GUDHI_PLACEMENT_POLICY_H_ */ +} // namespace Gudhi + +#endif // CONTRACTION_POLICIES_PLACEMENT_POLICY_H_ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h b/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h index bee2ecd7..78d61173 100644 --- a/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h +++ b/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h @@ -1,47 +1,51 @@ - /* 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-Mediterranee (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 GUDHI_VALID_CONTRACTION_POLICY_H_ -#define GUDHI_VALID_CONTRACTION_POLICY_H_ +/* 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-Mediterranee (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 CONTRACTION_POLICIES_VALID_CONTRACTION_POLICY_H_ +#define CONTRACTION_POLICIES_VALID_CONTRACTION_POLICY_H_ namespace Gudhi { + namespace contraction { - /** - *@brief Policy to specify if an edge contraction is valid or not. - *@ingroup contr - */ -template< typename EdgeProfile> class Valid_contraction_policy{ -public: - typedef typename EdgeProfile::Point Point; - typedef typename EdgeProfile::Edge_handle Edge_handle; - typedef typename EdgeProfile::Graph_vertex Graph_vertex; - - virtual bool operator()(const EdgeProfile& profile,const boost::optional<Point>& placement) const =0; - virtual ~Valid_contraction_policy(){}; +/** + *@brief Policy to specify if an edge contraction is valid or not. + *@ingroup contr + */ +template< typename EdgeProfile> +class Valid_contraction_policy { + public: + typedef typename EdgeProfile::Point Point; + typedef typename EdgeProfile::Edge_handle Edge_handle; + typedef typename EdgeProfile::Graph_vertex Graph_vertex; + + virtual bool operator()(const EdgeProfile& profile, const boost::optional<Point>& placement) const = 0; + + virtual ~Valid_contraction_policy() { } }; } // namespace contraction -} // namespace GUDHI + +} // namespace Gudhi -#endif /* GUDHI_VALID_CONTRACTION_POLICY_H_ */ +#endif // CONTRACTION_POLICIES_VALID_CONTRACTION_POLICY_H_ diff --git a/src/Contraction/include/gudhi/Edge_contraction.h b/src/Contraction/include/gudhi/Edge_contraction.h index 2c254710..349bb7d8 100644 --- a/src/Contraction/include/gudhi/Edge_contraction.h +++ b/src/Contraction/include/gudhi/Edge_contraction.h @@ -20,24 +20,24 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef GUDHI_EDGE_CONTRACTION_H_ -#define GUDHI_EDGE_CONTRACTION_H_ +#ifndef EDGE_CONTRACTION_H_ +#define EDGE_CONTRACTION_H_ -#include "gudhi/Skeleton_blocker_contractor.h" -#include "gudhi/Contraction/policies/Edge_length_cost.h" -#include "gudhi/Contraction/policies/First_vertex_placement.h" -#include "gudhi/Contraction/policies/Valid_contraction_policy.h" -#include "gudhi/Contraction/policies/Dummy_valid_contraction.h" -#include "gudhi/Contraction/policies/Link_condition_valid_contraction.h" -#include "gudhi/Utils.h" +#include <gudhi/Skeleton_blocker_contractor.h> +#include <gudhi/Contraction/policies/Edge_length_cost.h> +#include <gudhi/Contraction/policies/First_vertex_placement.h> +#include <gudhi/Contraction/policies/Valid_contraction_policy.h> +#include <gudhi/Contraction/policies/Dummy_valid_contraction.h> +#include <gudhi/Contraction/policies/Link_condition_valid_contraction.h> +#include <gudhi/Utils.h> +namespace Gudhi { -namespace Gudhi{ -namespace contraction{ +namespace contraction { -/** \defgroup contr Contraction +/** \defgroup contr Edge contraction \author David Salinas @@ -120,9 +120,9 @@ while ensuring its homotopy type is preserved during the contraction (edge are c \code{.cpp} #include <boost/timer/timer.hpp> #include <iostream> -#include "gudhi/Edge_contraction.h" -#include "gudhi/Skeleton_blocker.h" -#include "gudhi/Off_reader.h" +#include <gudhi/Edge_contraction.h> +#include <gudhi/Skeleton_blocker.h> +#include <gudhi/Off_reader.h> using namespace std; @@ -226,11 +226,11 @@ Time to simplify and enumerate simplices: \copyright GNU General Public License v3. -\verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim +\verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim */ -/** @} */ // end defgroup +/** @} */ // end defgroup +} // namespace contraction -} -} +} // namespace Gudhi -#endif /* GUDHI_EDGE_CONTRACTION_H_ */ +#endif // EDGE_CONTRACTION_H_ diff --git a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h index dcc05c22..2759b540 100644 --- a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h +++ b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h @@ -20,80 +20,69 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef GUDHI_SKELETON_BLOCKER_CONTRACTOR_H_ -#define GUDHI_SKELETON_BLOCKER_CONTRACTOR_H_ - -#include <memory> -#include <cassert> +#ifndef SKELETON_BLOCKER_CONTRACTOR_H_ +#define SKELETON_BLOCKER_CONTRACTOR_H_ // todo remove the queue to be independent from cgald -#include "gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h" +#include <gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h> +#include <gudhi/Contraction/Edge_profile.h> +#include <gudhi/Contraction/policies/Cost_policy.h> +#include <gudhi/Contraction/policies/Edge_length_cost.h> +#include <gudhi/Contraction/policies/Placement_policy.h> +#include <gudhi/Contraction/policies/First_vertex_placement.h> +#include <gudhi/Contraction/policies/Valid_contraction_policy.h> +#include <gudhi/Contraction/policies/Dummy_valid_contraction.h> // xxx remove +#include <gudhi/Contraction/policies/Link_condition_valid_contraction.h> // xxx remove +#include <gudhi/Contraction/policies/Contraction_visitor.h> -#include <list> -#include <boost/scoped_array.hpp> -#include <boost/scoped_ptr.hpp> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h> +#include <gudhi/Utils.h> -#include "gudhi/Contraction/Edge_profile.h" -#include "gudhi/Contraction/policies/Cost_policy.h" -#include "gudhi/Contraction/policies/Edge_length_cost.h" -#include "gudhi/Contraction/policies/Placement_policy.h" -#include "gudhi/Contraction/policies/First_vertex_placement.h" - -#include "gudhi/Contraction/policies/Valid_contraction_policy.h" -#include "gudhi/Contraction/policies/Dummy_valid_contraction.h" //xxx remove -#include "gudhi/Contraction/policies/Link_condition_valid_contraction.h" //xxx remove - -#include "gudhi/Contraction/policies/Contraction_visitor.h" - -#include "gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h" +#include <boost/scoped_array.hpp> +#include <boost/scoped_ptr.hpp> -#include "gudhi/Utils.h" +#include <memory> +#include <cassert> +#include <list> +#include <utility> // for pair +#include <vector> -namespace Gudhi{ +namespace Gudhi { namespace contraction { - - - template <class Profile> -Placement_policy<Profile>* make_first_vertex_placement(){ - return new First_vertex_placement<Profile>(); +Placement_policy<Profile>* make_first_vertex_placement() { + return new First_vertex_placement<Profile>(); } template <class Profile> -Valid_contraction_policy<Profile>* make_link_valid_contraction(){ - return new Link_condition_valid_contraction<Profile>(); +Valid_contraction_policy<Profile>* make_link_valid_contraction() { + return new Link_condition_valid_contraction<Profile>(); } - /** -*@brief Visitor to remove popable blockers after an edge contraction. -*/ + *@brief Visitor to remove popable blockers after an edge contraction. + */ template <class Profile> -class Contraction_visitor_remove_popable : public Contraction_visitor<Profile>{ -public: - typedef typename Profile::Point Point; - typedef typename Profile::Complex Complex; - typedef typename Complex::Vertex_handle Vertex_handle; - - void on_contracted(const Profile &profile, boost::optional< Point > placement) override{ - profile.complex().remove_all_popable_blockers(profile.v0_handle()); - } +class Contraction_visitor_remove_popable : public Contraction_visitor<Profile> { + public: + typedef typename Profile::Point Point; + typedef typename Profile::Complex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + + void on_contracted(const Profile &profile, boost::optional< Point > placement) override { + profile.complex().remove_all_popable_blockers(profile.v0_handle()); + } }; template <class Profile> -Contraction_visitor<Profile>* make_remove_popable_blockers_visitor(){ - return new Contraction_visitor_remove_popable<Profile>(); +Contraction_visitor<Profile>* make_remove_popable_blockers_visitor() { + return new Contraction_visitor_remove_popable<Profile>(); } - - - - - /** *@class Skeleton_blocker_contractor *@brief Class that allows to contract iteratively edges of a simplicial complex. @@ -110,519 +99,489 @@ Contraction_visitor<Profile>* make_remove_popable_blockers_visitor(){ * a topological condition (link condition) or a geometrical condition (normals messed up). * */ -template< -class GeometricSimplifiableComplex, -class EdgeProfile = Edge_profile<GeometricSimplifiableComplex> -> -class Skeleton_blocker_contractor : private skbl::Dummy_complex_visitor<typename GeometricSimplifiableComplex::Vertex_handle>{ - - GeometricSimplifiableComplex& complex_; - -public: - typedef typename GeometricSimplifiableComplex::Graph_vertex Graph_vertex; - typedef typename GeometricSimplifiableComplex::Vertex_handle Vertex_handle; - typedef typename GeometricSimplifiableComplex::Simplex_handle Simplex_handle; - typedef typename GeometricSimplifiableComplex::Simplex_handle_iterator Simplex_handle_iterator; - - - - typedef typename GeometricSimplifiableComplex::Root_vertex_handle Root_vertex_handle; - - typedef typename GeometricSimplifiableComplex::Graph_edge Graph_edge; - typedef typename GeometricSimplifiableComplex::Edge_handle Edge_handle; - typedef typename GeometricSimplifiableComplex::Point Point; - - typedef EdgeProfile Profile; - - - typedef Cost_policy<Profile> Cost_policy_; - typedef Placement_policy<Profile> Placement_policy_; - typedef Valid_contraction_policy<Profile> Valid_contraction_policy_; - typedef Contraction_visitor<EdgeProfile> Contraction_visitor_; - typedef Edge_profile_factory<EdgeProfile> Edge_profile_factory_; +template<class GeometricSimplifiableComplex, class EdgeProfile = Edge_profile<GeometricSimplifiableComplex>> +class Skeleton_blocker_contractor : private skbl::Dummy_complex_visitor< +typename GeometricSimplifiableComplex::Vertex_handle> { + GeometricSimplifiableComplex& complex_; + public: + typedef typename GeometricSimplifiableComplex::Graph_vertex Graph_vertex; + typedef typename GeometricSimplifiableComplex::Vertex_handle Vertex_handle; + typedef typename GeometricSimplifiableComplex::Simplex_handle Simplex_handle; + typedef typename GeometricSimplifiableComplex::Simplex_handle_iterator Simplex_handle_iterator; - typedef boost::optional<double> Cost_type; - typedef boost::optional<Point> Placement_type ; - typedef size_t size_type; + typedef typename GeometricSimplifiableComplex::Root_vertex_handle Root_vertex_handle; - typedef Skeleton_blocker_contractor Self ; + typedef typename GeometricSimplifiableComplex::Graph_edge Graph_edge; + typedef typename GeometricSimplifiableComplex::Edge_handle Edge_handle; + typedef typename GeometricSimplifiableComplex::Point Point; + typedef EdgeProfile Profile; -private: + typedef Cost_policy<Profile> Cost_policy_; + typedef Placement_policy<Profile> Placement_policy_; + typedef Valid_contraction_policy<Profile> Valid_contraction_policy_; + typedef Contraction_visitor<EdgeProfile> Contraction_visitor_; + typedef Edge_profile_factory<EdgeProfile> Edge_profile_factory_; - struct Compare_id - { - Compare_id() : algorithm_(0) {} - Compare_id( Self const* aAlgorithm ) : algorithm_(aAlgorithm) {} - bool operator() ( Edge_handle a, Edge_handle b ) const - { - return algorithm_->get_undirected_edge_id(a) < algorithm_->get_undirected_edge_id(b); - } + typedef boost::optional<double> Cost_type; + typedef boost::optional<Point> Placement_type; - Self const* algorithm_ ; - } ; + typedef size_t size_type; - struct Compare_cost - { - Compare_cost() : algorithm_(0) { - } + typedef Skeleton_blocker_contractor Self; - Compare_cost( Self const* aAlgorithm ) : algorithm_(aAlgorithm) { - } + private: + struct Compare_id { + Compare_id() : algorithm_(0) { } - bool operator() ( Edge_handle a, Edge_handle b ) const - { - // NOTE: A cost is an optional<> value. - // Absent optionals are ordered first; that is, "none < T" and "T > none" for any defined T != none. - // In consequence, edges with undefined costs will be promoted to the top of the priority queue and poped out first. - return algorithm_->get_data(a).cost() < algorithm_->get_data(b).cost(); - } + Compare_id(Self const* aAlgorithm) : algorithm_(aAlgorithm) { } - Self const* algorithm_ ; + bool operator()(Edge_handle a, Edge_handle b) const { + return algorithm_->get_undirected_edge_id(a) < algorithm_->get_undirected_edge_id(b); + } - } ; + Self const* algorithm_; + }; - struct Undirected_edge_id : boost::put_get_helper<size_type, Undirected_edge_id> - { - typedef boost::readable_property_map_tag category; - typedef size_type value_type; - typedef size_type reference; - typedef Edge_handle key_type; + struct Compare_cost { + Compare_cost() : algorithm_(0) { } - Undirected_edge_id() : algorithm_(0) {} + Compare_cost(Self const* aAlgorithm) : algorithm_(aAlgorithm) { } - Undirected_edge_id( Self const* aAlgorithm ) : algorithm_(aAlgorithm) {} + bool operator()(Edge_handle a, Edge_handle b) const { + // NOTE: A cost is an optional<> value. + // Absent optionals are ordered first; that is, "none < T" and "T > none" for any defined T != none. + // In consequence, edges with undefined costs will be promoted to the top of the priority queue and popped out + // first. + return algorithm_->get_data(a).cost() < algorithm_->get_data(b).cost(); + } - size_type operator[] ( Edge_handle e ) const { return algorithm_->get_undirected_edge_id(e); } + Self const* algorithm_; + }; - Self const* algorithm_ ; - } ; + struct Undirected_edge_id : boost::put_get_helper<size_type, Undirected_edge_id> { + typedef boost::readable_property_map_tag category; + typedef size_type value_type; + typedef size_type reference; + typedef Edge_handle key_type; - typedef CGAL::Modifiable_priority_queue<Edge_handle,Compare_cost,Undirected_edge_id> PQ ; - typedef typename PQ::handle pq_handle ; + Undirected_edge_id() : algorithm_(0) { } + Undirected_edge_id(Self const* aAlgorithm) : algorithm_(aAlgorithm) { } - // An Edge_data is associated with EVERY edge in the complex (collapsible or not). - // It relates the edge with the PQ-handle needed to update the priority queue - // It also relates the edge with a policy-based cache - class Edge_data - { - public : + size_type operator[](Edge_handle e) const { + return algorithm_->get_undirected_edge_id(e); + } - Edge_data() : PQHandle_(),cost_() {} + Self const* algorithm_; + }; - Cost_type const& cost() const { return cost_ ; } - Cost_type & cost() { return cost_ ; } + typedef CGAL::Modifiable_priority_queue<Edge_handle, Compare_cost, Undirected_edge_id> PQ; + typedef typename PQ::handle pq_handle; - pq_handle PQ_handle() const { return PQHandle_ ;} - bool is_in_PQ() const { return PQHandle_ != PQ::null_handle() ; } + // An Edge_data is associated with EVERY edge in the complex (collapsible or not). + // It relates the edge with the PQ-handle needed to update the priority queue + // It also relates the edge with a policy-based cache - void set_PQ_handle( pq_handle h ) { PQHandle_ = h ; } + class Edge_data { + public: + Edge_data() : PQHandle_(), cost_() { } - void reset_PQ_handle() { PQHandle_ = PQ::null_handle() ; } + Cost_type const& cost() const { + return cost_; + } - private: - pq_handle PQHandle_ ; - Cost_type cost_ ; + Cost_type & cost() { + return cost_; + } - } ; - typedef Edge_data* Edge_data_ptr ; - typedef boost::scoped_array<Edge_data> Edge_data_array ; + pq_handle PQ_handle() const { + return PQHandle_; + } + bool is_in_PQ() const { + return PQHandle_ != PQ::null_handle(); + } - int get_undirected_edge_id ( Edge_handle edge ) const { - return complex_[edge].index() ; - } + void set_PQ_handle(pq_handle h) { + PQHandle_ = h; + } + void reset_PQ_handle() { + PQHandle_ = PQ::null_handle(); + } - const Edge_data& get_data ( Edge_handle edge ) const - { - return edge_data_array_[get_undirected_edge_id(edge)]; - } - - - Edge_data& get_data ( Edge_handle edge ) - { - return edge_data_array_[get_undirected_edge_id(edge)]; - } - - Cost_type get_cost(const Profile & profile) const{ - return (*cost_policy_)(profile,get_placement(profile)); - } - - Profile create_profile(Edge_handle edge) const{ - if(edge_profile_factory_) - return edge_profile_factory_->make_profile(complex_,edge); - else - return Profile(complex_,edge); - } - - - void insert_in_PQ( Edge_handle edge, Edge_data& data ) - { - data.set_PQ_handle(heap_PQ_->push(edge)); - ++current_num_edges_heap_; - } - - void update_in_PQ( Edge_handle edge, Edge_data& data ) - { - data.set_PQ_handle(heap_PQ_->update(edge,data.PQ_handle())) ; - } - - void remove_from_PQ( Edge_handle edge, Edge_data& data ) - { - data.set_PQ_handle(heap_PQ_->erase(edge,data.PQ_handle())); - --current_num_edges_heap_; - } - - boost::optional<Edge_handle> pop_from_PQ() { - boost::optional<Edge_handle> edge = heap_PQ_->extract_top(); - if ( edge ) - get_data(*edge).reset_PQ_handle(); - return edge ; - } - - - -private: - - /** - * @brief Collect edges. - * - * Iterates over all edges of the simplicial complex and - * 1) inserts them in the priority queue sorted according to the Cost policy. - * 2) set the id() field of each edge - */ - void collect_edges(){ - // - // Loop over all the edges in the complex in the heap - // - size_type size = complex_.num_edges(); - DBG("Collecting edges ..."); - DBGMSG("num edges :",size); - - edge_data_array_.reset( new Edge_data[size] ) ; - - heap_PQ_.reset( new PQ (size, Compare_cost(this), Undirected_edge_id(this) ) ) ; - - std::size_t id = 0 ; - - //xxx do a parralel for - for(auto edge : complex_.edge_range()){ - complex_[edge].index() = id++; - Profile const& profile = create_profile(edge); - Edge_data& data = get_data(edge); - data.cost() = get_cost(profile) ; - ++initial_num_edges_heap_; - insert_in_PQ(edge,data); - if(contraction_visitor_) contraction_visitor_->on_collected(profile,data.cost()); - } - - DBG("Edges collected."); - - } - - bool should_stop(double lCost,const Profile &profile) const{ - return false; - } - - boost::optional<Point> get_placement(const Profile& profile) const{ - return (*placement_policy_)(profile); - } - - bool is_contraction_valid( Profile const& profile, Placement_type placement ) const{ - if(!valid_contraction_policy_) return true; - return (*valid_contraction_policy_)(profile,placement); - } - - -public: - /** - * \brief Contract edges. - * - * While the heap is not empty, it extracts the edge with the minimum - * cost in the heap then try to contract it. - * It stops when the Stop policy says so or when the number of contractions - * given by 'num_max_contractions' is reached (if this number is positive). - */ - void contract_edges(int num_max_contractions=-1){ - - DBG("\n\nContract edges"); - int num_contraction = 0 ; - - bool unspecified_num_contractions = (num_max_contractions == -1); - // - // Pops and processes each edge from the PQ - // - boost::optional<Edge_handle> edge ; - while ( (edge = pop_from_PQ())&& ((num_contraction<num_max_contractions)||(unspecified_num_contractions))) - { - Profile const& profile = create_profile(*edge); - Cost_type cost(get_data(*edge).cost()); - if(contraction_visitor_) contraction_visitor_->on_selected(profile,cost,0,0); - - DBGMSG("\n\n---- Pop edge - num vertices :",complex_.num_vertices()); - - if (cost){ - DBGMSG("sqrt(cost):",std::sqrt(*cost)); - if (should_stop(*cost,profile) ) - { - if(contraction_visitor_) contraction_visitor_->on_stop_condition_reached(); - DBG("should_stop"); - break ; - } - Placement_type placement = get_placement(profile); - if ( is_contraction_valid(profile,placement) && placement ) - { - DBG("contraction_valid"); - contract_edge(profile,placement); - ++ num_contraction; - } - else - { - DBG("contraction not valid"); - if(contraction_visitor_) contraction_visitor_->on_non_valid(profile); - } - } - else - DBG("uncomputable cost"); - } - if(contraction_visitor_) contraction_visitor_->on_stop_condition_reached(); - } - - - bool is_in_heap(Edge_handle edge) const{ - if(heap_PQ_->empty()) return false; - else{ - return edge_data_array_[get_undirected_edge_id(edge)].is_in_PQ(); - } - } - - bool is_heap_empty() const{ - return heap_PQ_->empty(); - } - - - /** - * @brief Returns an Edge_handle and a Placement_type. This pair consists in - * the edge with the lowest cost in the heap together with its placement. - * The returned value is initialized iff the heap is non-empty. - */ - boost::optional<std::pair<Edge_handle,Placement_type > > top_edge(){ - boost::optional<std::pair<Edge_handle,Placement_type > > res; - - if(!heap_PQ_->empty()) { - auto edge = heap_PQ_->top(); - Profile const& profile = create_profile(edge); - Placement_type placement = get_placement(profile); - res = make_pair(edge,placement); - DBGMSG("top edge:",complex_[edge]); - - } - return res; - } - - - /** - * @brief Constructor with default policies. - * - * @details The default cost, placement, valid and visitor policies - * are respectively : the edge length, the first point, the link condition - */ - Skeleton_blocker_contractor(GeometricSimplifiableComplex& complex) - :complex_(complex), - cost_policy_(new Edge_length_cost<Profile>), - placement_policy_(new First_vertex_placement<Profile>), - valid_contraction_policy_(new Link_condition_valid_contraction<Profile>), - contraction_visitor_(new Contraction_visitor_()), - edge_profile_factory_(0), - initial_num_edges_heap_(0), - current_num_edges_heap_(0) - { - complex_.set_visitor(this); - if(contraction_visitor_) contraction_visitor_->on_started(complex); - collect_edges(); - } - - /** - * @brief Constructor with customed policies. - * @remark Policies destruction is handle by the class with smart pointers. - */ - Skeleton_blocker_contractor(GeometricSimplifiableComplex& complex, - Cost_policy_ *cost_policy, - Placement_policy_ * placement_policy = new First_vertex_placement<Profile>, - Valid_contraction_policy_ * valid_contraction_policy = new Link_condition_valid_contraction<Profile>, - Contraction_visitor_* contraction_visitor = new Contraction_visitor_(), - Edge_profile_factory_* edge_profile_factory = NULL - ): - complex_(complex), - cost_policy_(cost_policy), - placement_policy_(placement_policy), - valid_contraction_policy_(valid_contraction_policy), - contraction_visitor_(contraction_visitor), - edge_profile_factory_(edge_profile_factory), - initial_num_edges_heap_(0), - current_num_edges_heap_(0) - { - complex_.set_visitor(this); - if(contraction_visitor) contraction_visitor->on_started(complex); - collect_edges(); - } - - - ~Skeleton_blocker_contractor(){ - complex_.set_visitor(0); - } - -private: - - - void contract_edge(const Profile& profile, Placement_type placement ) { - if(contraction_visitor_) contraction_visitor_->on_contracting(profile,placement); - - assert(complex_.contains_vertex(profile.v0_handle())); - assert(complex_.contains_vertex(profile.v1_handle())); - assert(placement); - - profile.complex().point(profile.v0_handle()) = *placement; - - // remark : this is not necessary since v1 will be deactivated - // profile.complex().point(profile.v1_handle()) = *placement; - - complex_.contract_edge(profile.v0_handle(),profile.v1_handle()); - - assert(complex_.contains_vertex(profile.v0_handle())); - assert(!complex_.contains_vertex(profile.v1_handle())); - - update_changed_edges(); - - // the visitor could do something as complex_.remove_popable_blockers(); - if(contraction_visitor_) contraction_visitor_->on_contracted(profile,placement); - } - -private: - - // every time the visitor's method on_changed_edge is called, it adds an - // edge to changed_edges_ - std::vector< Edge_handle > changed_edges_; - - /** - * @brief we update the cost and the position in the heap of an edge that has - * been changed - */ - inline void on_changed_edge(Vertex_handle a,Vertex_handle b) override{ - boost::optional<Edge_handle> ab(complex_[std::make_pair(a,b)]); - assert(ab); - changed_edges_.push_back(*ab); - } - - void update_changed_edges(){ - //xxx do a parralel for - - DBG("update edges"); - - // sequential loop - for(auto ab : changed_edges_){ - //1-get the Edge_handle corresponding to ab - //2-change the data in mEdgeArray[ab.id()] - //3-update the heap - Edge_data& data = get_data(ab); - Profile const& profile = create_profile(ab); - data.cost() = get_cost(profile) ; - if ( data.is_in_PQ()){ - update_in_PQ(ab,data); - } - else{ - insert_in_PQ(ab,data); - } - } - changed_edges_.clear(); - } - - -private: - void on_remove_edge(Vertex_handle a,Vertex_handle b) override{ - - boost::optional<Edge_handle> ab((complex_[std::make_pair(a,b)])); - assert(ab); - Edge_data& lData = get_data(*ab) ; - if ( lData.is_in_PQ() ) - { - remove_from_PQ(*ab,lData) ; - } - } -private: - /** - * @brief Called when the edge 'ax' has been added while the edge 'bx' - * is still there but will be removed on next instruction. - * We assign the index of 'bx' to the edge index of 'ax' - */ - void on_swaped_edge(Vertex_handle a,Vertex_handle b,Vertex_handle x) override{ - boost::optional<Edge_handle> ax(complex_[std::make_pair(a,x)]); - boost::optional<Edge_handle> bx(complex_[std::make_pair(b,x)]); - assert(ax&& bx); - complex_[*ax].index() =complex_[*bx].index(); - } -private: - /** - * @brief Called when a blocker is removed. - * All the edges that passes through the blocker may be edge-contractible - * again and are thus reinserted in the heap. - */ - void on_delete_blocker(const Simplex_handle * blocker) override{ - // we go for all pairs xy that belongs to the blocker - // note that such pairs xy are necessarily edges of the complex - // by definition of a blocker - - // todo uniqument utile pour la link condition - // laisser à l'utilisateur? booleen update_heap_on_removed_blocker? - Simplex_handle blocker_copy(*blocker); - for (auto x = blocker_copy.begin(); x!= blocker_copy.end(); ++x){ - for(auto y=x ; ++y != blocker_copy.end(); ){ - auto edge_descr(complex_[std::make_pair(*x,*y)]); - assert(edge_descr); - Edge_data& data = get_data(*edge_descr); - Profile const& profile = create_profile(*edge_descr); - data.cost() = get_cost(profile) ; - - // If the edge is already in the heap - // its priority has not changed. - // If the edge is not present, we reinsert it - // remark : we could also reinsert the edge - // only if it is valid - if ( !data.is_in_PQ() ){ - insert_in_PQ(*edge_descr,data); - } - } - } - } - - -private: - std::shared_ptr<Cost_policy_> cost_policy_; - std::shared_ptr<Placement_policy_> placement_policy_; - std::shared_ptr<Valid_contraction_policy_> valid_contraction_policy_; - std::shared_ptr<Contraction_visitor_> contraction_visitor_; - - //in case the user wants to do something special when the edge profile - //are created (for instance add some info) - std::shared_ptr<Edge_profile_factory_> edge_profile_factory_; - Edge_data_array edge_data_array_ ; - - boost::scoped_ptr<PQ> heap_PQ_ ; - int initial_num_edges_heap_; - int current_num_edges_heap_; - + private: + pq_handle PQHandle_; + Cost_type cost_; + }; + typedef Edge_data* Edge_data_ptr; + typedef boost::scoped_array<Edge_data> Edge_data_array; + + int get_undirected_edge_id(Edge_handle edge) const { + return complex_[edge].index(); + } + + const Edge_data& get_data(Edge_handle edge) const { + return edge_data_array_[get_undirected_edge_id(edge)]; + } + + Edge_data& get_data(Edge_handle edge) { + return edge_data_array_[get_undirected_edge_id(edge)]; + } + + Cost_type get_cost(const Profile & profile) const { + return (*cost_policy_)(profile, get_placement(profile)); + } + + Profile create_profile(Edge_handle edge) const { + if (edge_profile_factory_) + return edge_profile_factory_->make_profile(complex_, edge); + else + return Profile(complex_, edge); + } + + void insert_in_PQ(Edge_handle edge, Edge_data& data) { + data.set_PQ_handle(heap_PQ_->push(edge)); + ++current_num_edges_heap_; + } + + void update_in_PQ(Edge_handle edge, Edge_data& data) { + data.set_PQ_handle(heap_PQ_->update(edge, data.PQ_handle())); + } + + void remove_from_PQ(Edge_handle edge, Edge_data& data) { + data.set_PQ_handle(heap_PQ_->erase(edge, data.PQ_handle())); + --current_num_edges_heap_; + } + + boost::optional<Edge_handle> pop_from_PQ() { + boost::optional<Edge_handle> edge = heap_PQ_->extract_top(); + if (edge) + get_data(*edge).reset_PQ_handle(); + return edge; + } + + private: + /** + * @brief Collect edges. + * + * Iterates over all edges of the simplicial complex and + * 1) inserts them in the priority queue sorted according to the Cost policy. + * 2) set the id() field of each edge + */ + void collect_edges() { + // + // Loop over all the edges in the complex in the heap + // + size_type size = complex_.num_edges(); + DBG("Collecting edges ..."); + DBGMSG("num edges :", size); + + edge_data_array_.reset(new Edge_data[size]); + + heap_PQ_.reset(new PQ(size, Compare_cost(this), Undirected_edge_id(this))); + + std::size_t id = 0; + + // xxx do a parralel for + for (auto edge : complex_.edge_range()) { + complex_[edge].index() = id++; + Profile const& profile = create_profile(edge); + Edge_data& data = get_data(edge); + data.cost() = get_cost(profile); + ++initial_num_edges_heap_; + insert_in_PQ(edge, data); + if (contraction_visitor_) contraction_visitor_->on_collected(profile, data.cost()); + } + + DBG("Edges collected."); + } + + bool should_stop(double lCost, const Profile &profile) const { + return false; + } + + boost::optional<Point> get_placement(const Profile& profile) const { + return (*placement_policy_)(profile); + } + + bool is_contraction_valid(Profile const& profile, Placement_type placement) const { + if (!valid_contraction_policy_) return true; + return (*valid_contraction_policy_)(profile, placement); + } + + + public: + /** + * \brief Contract edges. + * + * While the heap is not empty, it extracts the edge with the minimum + * cost in the heap then try to contract it. + * It stops when the Stop policy says so or when the number of contractions + * given by 'num_max_contractions' is reached (if this number is positive). + */ + void contract_edges(int num_max_contractions = -1) { + DBG("\n\nContract edges"); + int num_contraction = 0; + + bool unspecified_num_contractions = (num_max_contractions == -1); + // + // Pops and processes each edge from the PQ + // + boost::optional<Edge_handle> edge; + while ((edge = pop_from_PQ()) && ((num_contraction < num_max_contractions) || (unspecified_num_contractions))) { + Profile const& profile = create_profile(*edge); + Cost_type cost(get_data(*edge).cost()); + if (contraction_visitor_) contraction_visitor_->on_selected(profile, cost, 0, 0); + + DBGMSG("\n\n---- Pop edge - num vertices :", complex_.num_vertices()); + + if (cost) { + DBGMSG("sqrt(cost):", std::sqrt(*cost)); + if (should_stop(*cost, profile)) { + if (contraction_visitor_) contraction_visitor_->on_stop_condition_reached(); + DBG("should_stop"); + break; + } + Placement_type placement = get_placement(profile); + if (is_contraction_valid(profile, placement) && placement) { + DBG("contraction_valid"); + contract_edge(profile, placement); + ++num_contraction; + } else { + DBG("contraction not valid"); + if (contraction_visitor_) contraction_visitor_->on_non_valid(profile); + } + } else { + DBG("uncomputable cost"); + } + } + if (contraction_visitor_) contraction_visitor_->on_stop_condition_reached(); + } + + bool is_in_heap(Edge_handle edge) const { + if (heap_PQ_->empty()) { + return false; + } else { + return edge_data_array_[get_undirected_edge_id(edge)].is_in_PQ(); + } + } + + bool is_heap_empty() const { + return heap_PQ_->empty(); + } + + /** + * @brief Returns an Edge_handle and a Placement_type. This pair consists in + * the edge with the lowest cost in the heap together with its placement. + * The returned value is initialized iff the heap is non-empty. + */ + boost::optional<std::pair<Edge_handle, Placement_type > > top_edge() { + boost::optional<std::pair<Edge_handle, Placement_type > > res; + + if (!heap_PQ_->empty()) { + auto edge = heap_PQ_->top(); + Profile const& profile = create_profile(edge); + Placement_type placement = get_placement(profile); + res = std::make_pair(edge, placement); + DBGMSG("top edge:", complex_[edge]); + } + return res; + } + + /** + * @brief Constructor with default policies. + * + * @details The default cost, placement, valid and visitor policies + * are respectively : the edge length, the first point, the link condition + */ + Skeleton_blocker_contractor(GeometricSimplifiableComplex& complex) + : complex_(complex), + cost_policy_(new Edge_length_cost<Profile>), + placement_policy_(new First_vertex_placement<Profile>), + valid_contraction_policy_(new Link_condition_valid_contraction<Profile>), + contraction_visitor_(new Contraction_visitor_()), + edge_profile_factory_(0), + initial_num_edges_heap_(0), + current_num_edges_heap_(0) { + complex_.set_visitor(this); + if (contraction_visitor_) contraction_visitor_->on_started(complex); + collect_edges(); + } + + /** + * @brief Constructor with customed policies. + * @remark Policies destruction is handle by the class with smart pointers. + */ + Skeleton_blocker_contractor(GeometricSimplifiableComplex& complex, + Cost_policy_ *cost_policy, + Placement_policy_ * placement_policy = new First_vertex_placement<Profile>, + Valid_contraction_policy_ * valid_contraction_policy = + new Link_condition_valid_contraction<Profile>, + Contraction_visitor_* contraction_visitor = new Contraction_visitor_(), + Edge_profile_factory_* edge_profile_factory = NULL) : + complex_(complex), + cost_policy_(cost_policy), + placement_policy_(placement_policy), + valid_contraction_policy_(valid_contraction_policy), + contraction_visitor_(contraction_visitor), + edge_profile_factory_(edge_profile_factory), + initial_num_edges_heap_(0), + current_num_edges_heap_(0) { + complex_.set_visitor(this); + if (contraction_visitor) contraction_visitor->on_started(complex); + collect_edges(); + } + + ~Skeleton_blocker_contractor() { + complex_.set_visitor(0); + } + + private: + void contract_edge(const Profile& profile, Placement_type placement) { + if (contraction_visitor_) contraction_visitor_->on_contracting(profile, placement); + + assert(complex_.contains_vertex(profile.v0_handle())); + assert(complex_.contains_vertex(profile.v1_handle())); + assert(placement); + + profile.complex().point(profile.v0_handle()) = *placement; + + // remark : this is not necessary since v1 will be deactivated + // profile.complex().point(profile.v1_handle()) = *placement; + + complex_.contract_edge(profile.v0_handle(), profile.v1_handle()); + + assert(complex_.contains_vertex(profile.v0_handle())); + assert(!complex_.contains_vertex(profile.v1_handle())); + + update_changed_edges(); + + // the visitor could do something as complex_.remove_popable_blockers(); + if (contraction_visitor_) contraction_visitor_->on_contracted(profile, placement); + } + + private: + // every time the visitor's method on_changed_edge is called, it adds an + // edge to changed_edges_ + std::vector< Edge_handle > changed_edges_; + + /** + * @brief we update the cost and the position in the heap of an edge that has + * been changed + */ + inline void on_changed_edge(Vertex_handle a, Vertex_handle b) override { + boost::optional<Edge_handle> ab(complex_[std::make_pair(a, b)]); + assert(ab); + changed_edges_.push_back(*ab); + } + + void update_changed_edges() { + // xxx do a parralel for + DBG("update edges"); + + // sequential loop + for (auto ab : changed_edges_) { + // 1-get the Edge_handle corresponding to ab + // 2-change the data in mEdgeArray[ab.id()] + // 3-update the heap + Edge_data& data = get_data(ab); + Profile const& profile = create_profile(ab); + data.cost() = get_cost(profile); + if (data.is_in_PQ()) { + update_in_PQ(ab, data); + } else { + insert_in_PQ(ab, data); + } + } + changed_edges_.clear(); + } + + + private: + void on_remove_edge(Vertex_handle a, Vertex_handle b) override { + boost::optional<Edge_handle> ab((complex_[std::make_pair(a, b)])); + assert(ab); + Edge_data& lData = get_data(*ab); + if (lData.is_in_PQ()) { + remove_from_PQ(*ab, lData); + } + } + + private: + /** + * @brief Called when the edge 'ax' has been added while the edge 'bx' + * is still there but will be removed on next instruction. + * We assign the index of 'bx' to the edge index of 'ax' + */ + void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) override { + boost::optional<Edge_handle> ax(complex_[std::make_pair(a, x)]); + boost::optional<Edge_handle> bx(complex_[std::make_pair(b, x)]); + assert(ax && bx); + complex_[*ax].index() = complex_[*bx].index(); + } + + private: + /** + * @brief Called when a blocker is removed. + * All the edges that passes through the blocker may be edge-contractible + * again and are thus reinserted in the heap. + */ + void on_delete_blocker(const Simplex_handle * blocker) override { + // we go for all pairs xy that belongs to the blocker + // note that such pairs xy are necessarily edges of the complex + // by definition of a blocker + + // todo uniqument utile pour la link condition + // laisser a l'utilisateur ? booleen update_heap_on_removed_blocker? + Simplex_handle blocker_copy(*blocker); + for (auto x = blocker_copy.begin(); x != blocker_copy.end(); ++x) { + for (auto y = x; ++y != blocker_copy.end();) { + auto edge_descr(complex_[std::make_pair(*x, *y)]); + assert(edge_descr); + Edge_data& data = get_data(*edge_descr); + Profile const& profile = create_profile(*edge_descr); + data.cost() = get_cost(profile); + + // If the edge is already in the heap + // its priority has not changed. + // If the edge is not present, we reinsert it + // remark : we could also reinsert the edge + // only if it is valid + if (!data.is_in_PQ()) { + insert_in_PQ(*edge_descr, data); + } + } + } + } + + + private: + std::shared_ptr<Cost_policy_> cost_policy_; + std::shared_ptr<Placement_policy_> placement_policy_; + std::shared_ptr<Valid_contraction_policy_> valid_contraction_policy_; + std::shared_ptr<Contraction_visitor_> contraction_visitor_; + + // in case the user wants to do something special when the edge profile + // are created (for instance add some info) + std::shared_ptr<Edge_profile_factory_> edge_profile_factory_; + Edge_data_array edge_data_array_; + + boost::scoped_ptr<PQ> heap_PQ_; + int initial_num_edges_heap_; + int current_num_edges_heap_; }; } // namespace contraction -} // namespace GUDHI -#endif /* GUDHI_SKELETON_BLOCKER_CONTRACTOR_H_ */ +} // namespace Gudhi + +#endif // SKELETON_BLOCKER_CONTRACTOR_H_ |