diff options
author | skachano <skachano@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-09-28 12:33:22 +0000 |
---|---|---|
committer | skachano <skachano@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-09-28 12:33:22 +0000 |
commit | d16822ea1d3cedea66dcddd390becdd4cbb557bb (patch) | |
tree | b1c592e415f43c1be425608db861e5348e61dcf3 /src/Witness_complex/include/gudhi/Witness_complex.h | |
parent | 1c09c91ddf4d38196a91bbff5ae432fb13be6762 (diff) | |
parent | a138c9ed4fb9770a3612ff4ee0f914942bbe9724 (diff) |
Merged trunk into relaxed witness branch
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/relaxed-witness@1579 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: a9ca2e7a968ebf4bb80cfa795965ae78511e8dd4
Diffstat (limited to 'src/Witness_complex/include/gudhi/Witness_complex.h')
-rw-r--r-- | src/Witness_complex/include/gudhi/Witness_complex.h | 96 |
1 files changed, 56 insertions, 40 deletions
diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 34cbc882..489cdf11 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -28,8 +28,7 @@ #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> -#include <boost/container/flat_map.hpp> -#include <boost/iterator/transform_iterator.hpp> +#include <boost/range/size.hpp> #include <gudhi/distance_functions.h> @@ -47,12 +46,13 @@ namespace Gudhi { namespace witness_complex { -/** - \class Witness_complex - \brief Constructs the witness complex for the given set of witnesses and landmarks. - \ingroup witness_complex - */ -template< class Simplicial_complex> +// /* +// * \private +// \class Witness_complex +// \brief Constructs the witness complex for the given set of witnesses and landmarks. +// \ingroup witness_complex +// */ +template< class SimplicialComplex> class Witness_complex { private: struct Active_witness { @@ -65,13 +65,12 @@ class Witness_complex { }; private: - typedef typename Simplicial_complex::Simplex_handle Simplex_handle; - typedef typename Simplicial_complex::Vertex_handle Vertex_handle; + typedef typename SimplicialComplex::Simplex_handle Simplex_handle; + typedef typename SimplicialComplex::Vertex_handle Vertex_handle; typedef std::vector< double > Point_t; typedef std::vector< Point_t > Point_Vector; - // typedef typename Simplicial_complex::Filtration_value Filtration_value; typedef std::vector< Vertex_handle > typeVectorVertex; typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; typedef std::pair< Simplex_handle, bool > typePairSimplexBool; @@ -81,19 +80,19 @@ class Witness_complex { typedef std::list< Vertex_handle > ActiveWitnessList; private: - int nbL; // Number of landmarks - Simplicial_complex& sc; // Simplicial complex + int nbL_; // Number of landmarks + SimplicialComplex& sc_; // Simplicial complex public: ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - /** @name Constructor + /* @name Constructor */ //@{ // Witness_range<Closest_landmark_range<Vertex_handle>> - /** + /* * \brief Iterative construction of the witness complex. * \details The witness complex is written in sc_ basing on a matrix knn of * nearest neighbours of the form {witnesses}x{landmarks}. @@ -109,31 +108,29 @@ class Witness_complex { */ template< typename KNearestNeighbors > Witness_complex(KNearestNeighbors const & knn, - Simplicial_complex & sc_, - int nbL_, - int dim) : nbL(nbL_), sc(sc_) { + int nbL, + int dim, + SimplicialComplex & sc) : nbL_(nbL), sc_(sc) { // Construction of the active witness list - int nbW = knn.size(); + int nbW = boost::size(knn); typeVectorVertex vv; int counter = 0; /* The list of still useful witnesses * it will diminuish in the course of iterations */ ActiveWitnessList active_w; // = new ActiveWitnessList(); - for (int i = 0; i != nbL; ++i) { + for (Vertex_handle i = 0; i != nbL_; ++i) { // initial fill of 0-dimensional simplices // by doing it we don't assume that landmarks are necessarily witnesses themselves anymore counter++; vv = {i}; - sc.insert_simplex(vv); + sc_.insert_simplex(vv); // TODO(SK) Error if not inserted : normally no need here though } int k = 1; /* current dimension in iterative construction */ for (int i = 0; i != nbW; ++i) active_w.push_back(i); - // std::cout << "Successfully added edges" << std::endl; while (!active_w.empty() && k < dim) { - // std::cout << "Started the step k=" << k << std::endl; typename ActiveWitnessList::iterator it = active_w.begin(); while (it != active_w.end()) { typeVectorVertex simplex_vector; @@ -142,9 +139,9 @@ class Witness_complex { if (ok) { for (int i = 0; i != k + 1; ++i) simplex_vector.push_back(knn[*it][i]); - sc.insert_simplex(simplex_vector, 0.0); + sc_.insert_simplex(simplex_vector); // TODO(SK) Error if not inserted : normally no need here though - it++; + ++it; } else { active_w.erase(it++); // First increase the iterator and then erase the previous element } @@ -156,15 +153,13 @@ class Witness_complex { //@} private: - /** \brief Check if the facets of the k-dimensional simplex witnessed + /* \brief Check if the facets of the k-dimensional simplex witnessed * by witness witness_id are already in the complex. * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id */ template <typename KNearestNeighbors> bool all_faces_in(KNearestNeighbors const &knn, int witness_id, int k) { - // std::cout << "All face in with the landmark " << inserted_vertex << std::endl; std::vector< Vertex_handle > facet; - // Vertex_handle curr_vh = curr_sh->first; // CHECK ALL THE FACETS for (int i = 0; i != k + 1; ++i) { facet = {}; @@ -173,9 +168,8 @@ class Witness_complex { facet.push_back(knn[witness_id][j]); } } // endfor - if (sc.find(facet) == sc.null_simplex()) + if (sc_.find(facet) == sc_.null_simplex()) return false; - // std::cout << "++++ finished loop safely\n"; } // endfor return true; } @@ -194,27 +188,25 @@ class Witness_complex { } public: - /** - * \brief Verification if every simplex in the complex is witnessed by witnesses in knn. - * \param print_output =true will print the witnesses for each simplex - * \remark Added for debugging purposes. - */ + // /* + // * \brief Verification if every simplex in the complex is witnessed by witnesses in knn. + // * \param print_output =true will print the witnesses for each simplex + // * \remark Added for debugging purposes. + // */ template< class KNearestNeighbors > bool is_witness_complex(KNearestNeighbors const & knn, bool print_output) { - // bool final_result = true; - for (Simplex_handle sh : sc.complex_simplex_range()) { + for (Simplex_handle sh : sc_.complex_simplex_range()) { bool is_witnessed = false; typeVectorVertex simplex; int nbV = 0; // number of verticed in the simplex - for (int v : sc.simplex_vertex_range(sh)) + for (Vertex_handle v : sc_.simplex_vertex_range(sh)) simplex.push_back(v); nbV = simplex.size(); for (typeVectorVertex w : knn) { bool has_vertices = true; - for (int v : simplex) + for (Vertex_handle v : simplex) if (std::find(w.begin(), w.begin() + nbV, v) == w.begin() + nbV) { has_vertices = false; - // break; } if (has_vertices) { is_witnessed = true; @@ -242,6 +234,30 @@ class Witness_complex { } }; + /** + * \ingroup witness_complex + * \brief Iterative construction of the witness complex. + * \details The witness complex is written in simplicial complex sc_ + * basing on a matrix knn of + * nearest neighbours of the form {witnesses}x{landmarks}. + * + * The type KNearestNeighbors can be seen as + * Witness_range<Closest_landmark_range<Vertex_handle>>, where + * Witness_range and Closest_landmark_range are random access ranges. + * + * Procedure takes into account at most (dim+1) + * first landmarks from each landmark range to construct simplices. + * + * Landmarks are supposed to be in [0,nbL_-1] + */ + template <class KNearestNeighbors, class SimplicialComplexForWitness> + void witness_complex(KNearestNeighbors const & knn, + int nbL, + int dim, + SimplicialComplexForWitness & sc) { + Witness_complex<SimplicialComplexForWitness>(knn, nbL, dim, sc); + } + } // namespace witness_complex } // namespace Gudhi |