diff options
Diffstat (limited to 'src/Contraction/include/gudhi/Contraction')
11 files changed, 562 insertions, 0 deletions
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 new file mode 100644 index 00000000..10b89e13 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/CGAL_queue/Modifiable_priority_queue.h @@ -0,0 +1,91 @@ +// Copyright (c) 2006-2011 GeometryFactory (France). All rights reserved. +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Fernando Cacciola <fernando.cacciola@geometryfactory.com> +// +#ifndef CGAL_MODIFIABLE_PRIORITY_QUEUE_H +#define CGAL_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 { + +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 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() ) + { + value_type v = top(); + pop(); + r = boost::optional<value_type>(v) ; + } + return r ; + } + + static handle null_handle() { return handle(false); } + +private: + + Heap mHeap ; + +} ; + +} //namespace CGAL + +#endif + diff --git a/src/Contraction/include/gudhi/Contraction/Edge_profile.h b/src/Contraction/include/gudhi/Contraction/Edge_profile.h new file mode 100644 index 00000000..7005f02c --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/Edge_profile.h @@ -0,0 +1,115 @@ +/* + * Edge_profile.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_EDGE_PROFILE_H_ +#define GUDHI_EDGE_PROFILE_H_ +//#include "combinatorics/Skeleton_blocker/Simplex.h" + + +namespace Gudhi{ + +namespace contraction { +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::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_handle edge_handle() const{ + return edge_handle_; + } + + Graph_edge& edge() const{ + return complex_[edge_handle_]; + } + + + Graph_vertex& v0() const{return complex_[v0_handle()];} + Graph_vertex& v1() const{return complex_[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); + } + + 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());} + + 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_; + +}; + +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(){}; +}; + + +} // namespace contraction + +} // namespace GUDHI + +#endif /* GUDHI_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 new file mode 100644 index 00000000..ef670234 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h @@ -0,0 +1,83 @@ +/* + * Contraction_visitor.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_CONTRACTION_VISITOR_H_ +#define GUDHI_CONTRACTION_VISITOR_H_ + +#include "gudhi/Contraction/Edge_profile.h" +#include "boost/optional.hpp" + +namespace Gudhi{ + +namespace contraction { + +/** + *@class Contraction_visitor + *@brief Interface for a visitor of the edge contraction process. + */ +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 StopPredicate returned true (but not if the algorithm terminates because the surface could not be simplified any further). + */ + virtual void on_stop_condition_reached (const Profile &profile){} + + + /** + * @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 + +#endif /* GUDHI_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 new file mode 100644 index 00000000..e183a74d --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h @@ -0,0 +1,32 @@ +/* + * Cost_policy.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_COST_POLICY_H_ +#define GUDHI_COST_POLICY_H_ + +#include <boost/optional.hpp> + +namespace Gudhi{ + +namespace contraction { + +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; + + 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_ */ diff --git a/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h new file mode 100644 index 00000000..b0202fae --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h @@ -0,0 +1,34 @@ +/* + * Dummy_valid_contraction.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_DUMMY_VALID_CONTRACTION_H_ +#define GUDHI_DUMMY_VALID_CONTRACTION_H_ + +#include "Valid_contraction_policy.h" + +namespace Gudhi{ + +namespace 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 + + + +#endif /* GUDHI_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 new file mode 100644 index 00000000..32c8768e --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h @@ -0,0 +1,41 @@ +/* + * Edge_length_cost.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_EDGE_LENGTH_COST_H_ +#define GUDHI_EDGE_LENGTH_COST_H_ + +#include "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; + } + +}; + +} // namespace contraction + +} // namespace GUDHI + +#endif /* GUDHI_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 new file mode 100644 index 00000000..cad87e3e --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h @@ -0,0 +1,39 @@ +/* + * First_vertex_placement.h + * + * Created on: Feb 20, 2014 + * Author: David Salinas + * Copyright 2013 INRIA. All rights reserved + */ + +#ifndef GUDHI_FIRST_VERTEX_PLACEMENT_H_ +#define GUDHI_FIRST_VERTEX_PLACEMENT_H_ + +#include "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; + + typedef typename Placement_policy<EdgeProfile>::Placement_type Placement_type; + + Placement_type operator()(const EdgeProfile& profile) const override{ + return Placement_type(profile.p0()); + } +}; +} // namespace contraction + +} // namespace GUDHI + + +#endif /* GUDHI_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 new file mode 100644 index 00000000..77fb6f95 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h @@ -0,0 +1,36 @@ +/* + * Link_condition_valid_contraction.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#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{ + +namespace contraction { + + + +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 + +#endif /* GUDHI_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 new file mode 100644 index 00000000..872c6d80 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h @@ -0,0 +1,35 @@ +/* + * Middle_placement.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_MIDDLE_PLACEMENT_H_ +#define GUDHI_MIDDLE_PLACEMENT_H_ + +#include "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; + + 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()); + } +}; +} // namespace contraction +} // namespace GUDHI + +#endif /* GUDHI_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 new file mode 100644 index 00000000..78595f3b --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h @@ -0,0 +1,29 @@ +/* + * Placement_policy.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_PLACEMENT_POLICY_H_ +#define GUDHI_PLACEMENT_POLICY_H_ + +#include <boost/optional.hpp> + +namespace Gudhi { +namespace contraction { + +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_policy(){}; +}; + + +} // namespace contraction +} // namespace GUDHI + +#endif /* GUDHI_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 new file mode 100644 index 00000000..f6016e2d --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h @@ -0,0 +1,27 @@ +/* + * Valid_contraction_policy.h + * + * Created on: Feb 13, 2014 + * Author: dsalinas + */ + +#ifndef GUDHI_VALID_CONTRACTION_POLICY_H_ +#define GUDHI_VALID_CONTRACTION_POLICY_H_ + +namespace Gudhi { +namespace contraction { +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 + + +#endif /* GUDHI_VALID_CONTRACTION_POLICY_H_ */ |