diff options
Diffstat (limited to 'src/Contraction/include/gudhi/Contraction')
10 files changed, 521 insertions, 0 deletions
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..0e914de9 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/Edge_profile.h @@ -0,0 +1,119 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef CONTRACTION_EDGE_PROFILE_H_ +#define CONTRACTION_EDGE_PROFILE_H_ + +#include <ostream> +#include <cassert> + +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) { + return o << "v0:" << v.v0_handle() << " v1:" << v.v1_handle(); + } + + 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 // 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 new file mode 100644 index 00000000..243bc51c --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Contraction_visitor.h @@ -0,0 +1,79 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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 { + +/** + *@class Contraction_visitor + *@brief Interface for a visitor of the edge contraction process. + *@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) { } +}; + +} // namespace contraction + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..97114794 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Cost_policy.h @@ -0,0 +1,41 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef CONTRACTION_POLICIES_COST_POLICY_H_ +#define CONTRACTION_POLICIES_COST_POLICY_H_ + +#include <boost/optional.hpp> + +namespace Gudhi { + +namespace contraction { + +/** + *@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; + + 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 // 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 new file mode 100644 index 00000000..27a4dc7a --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Dummy_valid_contraction.h @@ -0,0 +1,37 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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; + } +}; + +} // namespace contraction + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..97589385 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Edge_length_cost.h @@ -0,0 +1,44 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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; + } +}; + +} // namespace contraction + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..005b80e0 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/First_vertex_placement.h @@ -0,0 +1,40 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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; + + 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 // 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 new file mode 100644 index 00000000..2e7ea481 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Link_condition_valid_contraction.h @@ -0,0 +1,44 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ +#define CONTRACTION_POLICIES_LINK_CONDITION_VALID_CONTRACTION_H_ + +#include <gudhi/Contraction/policies/Valid_contraction_policy.h> +#include <gudhi/Debug_utils.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); + } +}; + +} // namespace contraction + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..7dcf708b --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Middle_placement.h @@ -0,0 +1,39 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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; + + 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 // 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 new file mode 100644 index 00000000..5f97d6a7 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Placement_policy.h @@ -0,0 +1,39 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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; + + virtual Placement_type operator()(const EdgeProfile& profile) const = 0; + + virtual ~Placement_policy() { } +}; + +} // namespace contraction + +} // 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 new file mode 100644 index 00000000..413c5bd6 --- /dev/null +++ b/src/Contraction/include/gudhi/Contraction/policies/Valid_contraction_policy.h @@ -0,0 +1,39 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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() { } +}; + +} // namespace contraction + +} // namespace Gudhi + + +#endif // CONTRACTION_POLICIES_VALID_CONTRACTION_POLICY_H_ |