summaryrefslogtreecommitdiff
path: root/src/Witness_complex/include/gudhi/Witness_complex.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/Witness_complex/include/gudhi/Witness_complex.h')
-rw-r--r--src/Witness_complex/include/gudhi/Witness_complex.h96
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-01 07:43:40 +0000