summaryrefslogtreecommitdiff
path: root/src/Toplex_map
diff options
context:
space:
mode:
authorvrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb>2018-10-16 14:33:27 +0000
committervrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb>2018-10-16 14:33:27 +0000
commitdda6af124625a4fbcd2524d623ef904b394af001 (patch)
treef9ccd21ed95443633b42a80c9e76fa1eba7d817a /src/Toplex_map
parent3cf8477c5b259cd83ee869cb2b0913c31566aeda (diff)
Add copyrights
Fix cpplint git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3959 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 02c873347468e28d50f0c8ac385be988c07c96df
Diffstat (limited to 'src/Toplex_map')
-rw-r--r--src/Toplex_map/benchmark/benchmark_tm.cpp170
-rw-r--r--src/Toplex_map/doc/Intro_Toplex_map.h6
-rw-r--r--src/Toplex_map/example/simple_toplex_map.cpp17
-rw-r--r--src/Toplex_map/include/gudhi/Lazy_toplex_map.h299
-rw-r--r--src/Toplex_map/include/gudhi/Toplex_map.h369
-rw-r--r--src/Toplex_map/test/lazy_toplex_map_unit_test.cpp27
-rw-r--r--src/Toplex_map/test/toplex_map_unit_test.cpp27
7 files changed, 497 insertions, 418 deletions
diff --git a/src/Toplex_map/benchmark/benchmark_tm.cpp b/src/Toplex_map/benchmark/benchmark_tm.cpp
index 5f13288c..eedb442b 100644
--- a/src/Toplex_map/benchmark/benchmark_tm.cpp
+++ b/src/Toplex_map/benchmark/benchmark_tm.cpp
@@ -1,3 +1,25 @@
+/* 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: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * 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/>.
+ */
+
#include <iostream>
#include <random>
#include <chrono>
@@ -10,11 +32,10 @@ using namespace Gudhi;
typedef Toplex_map::Simplex Simplex;
typedef Toplex_map::Vertex Vertex;
-typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool;
+typedef std::pair<Simplex_tree<>::Simplex_handle, bool> typePairSimplexBool;
class ST_wrapper {
-
-public:
+ public:
void insert_simplex(const Simplex& tau) {
/*std::cout << "insert_simplex - " << simplexTree.num_simplices() << " - ";
for (auto v : tau)
@@ -24,28 +45,22 @@ public:
simplexTree.insert_simplex_and_subfaces(tau);
}
- bool membership(const Simplex& tau) {
- return simplexTree.find(tau) != simplexTree.null_simplex();
- }
+ bool membership(const Simplex& tau) { return simplexTree.find(tau) != simplexTree.null_simplex(); }
Vertex contraction(const Vertex x, const Vertex y) {
// TODO (VR): edge contraction is not yet available for Simplex_tree
return y;
}
- std::size_t num_maximal_simplices() {
- return simplexTree.num_simplices();
- }
+ std::size_t num_maximal_simplices() { return simplexTree.num_simplices(); }
-private:
- Simplex_tree<> simplexTree;
- void erase_max(const Simplex& sigma) {
- if(membership(sigma))
- simplexTree.remove_maximal_simplex(simplexTree.find(sigma));
- }
+ private:
+ Simplex_tree<> simplexTree;
+ void erase_max(const Simplex& sigma) {
+ if (membership(sigma)) simplexTree.remove_maximal_simplex(simplexTree.find(sigma));
+ }
};
-
int n = 300;
int nb_insert_simplex1 = 3000;
@@ -54,76 +69,69 @@ int nb_contraction = 300;
int nb_insert_simplex2 = 3000;
int nb_membership2 = 400000;
-Simplex random_simplex(int n, std::size_t d){
- std::random_device rd;
- std::mt19937 gen(rd());
- std::uniform_int_distribution<std::size_t> dis(1, n);
- Simplex s;
- while(s.size() < d)
- s.insert(dis(gen));
- return s;
+Simplex random_simplex(int n, std::size_t d) {
+ std::random_device rd;
+ std::mt19937 gen(rd());
+ std::uniform_int_distribution<std::size_t> dis(1, n);
+ Simplex s;
+ while (s.size() < d) s.insert(dis(gen));
+ return s;
}
-std::vector<Simplex> r_vector_simplices(int n, int max_d, int m){
- std::random_device rd;
- std::mt19937 gen(rd());
- std::uniform_int_distribution<std::size_t> dis(1, max_d);
- std::vector<Simplex> v;
- for(int i=0; i<m; i++)
- v.push_back(random_simplex(n,dis(gen)));
- return v;
+std::vector<Simplex> r_vector_simplices(int n, int max_d, int m) {
+ std::random_device rd;
+ std::mt19937 gen(rd());
+ std::uniform_int_distribution<std::size_t> dis(1, max_d);
+ std::vector<Simplex> v;
+ for (int i = 0; i < m; i++) v.push_back(random_simplex(n, dis(gen)));
+ return v;
}
-template<typename complex_type>
-void chrono(int n, int d){
- complex_type K;
- std::vector<Simplex> simplices_insert_simplex1 = r_vector_simplices(n,d,nb_insert_simplex1);
- std::vector<Simplex> simplices_membership1 = r_vector_simplices(n,d,nb_membership1);
- std::vector<Simplex> simplices_insert_simplex2 = r_vector_simplices(n - 2*nb_contraction,d,nb_insert_simplex2);
- std::vector<Simplex> simplices_membership2 = r_vector_simplices(n - 2*nb_contraction,d,nb_membership2);
- std::chrono::time_point<std::chrono::system_clock> start, end;
-
- for(const Simplex& s : simplices_insert_simplex1)
- K.insert_simplex(s);
-
- for(const Simplex& s : simplices_membership1)
- K.membership(s);
-
- start = std::chrono::system_clock::now();
- for(int i = 1; i<=nb_contraction; i++)
- K.contraction(n-2*i,n-2*i-1);
- end = std::chrono::system_clock::now();
- auto c3 = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
-
- start = std::chrono::system_clock::now();
- for(const Simplex& s : simplices_insert_simplex2)
- K.insert_simplex(s);
- end = std::chrono::system_clock::now();
- auto c1 = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
-
- start = std::chrono::system_clock::now();
- for(const Simplex& s : simplices_membership2)
- K.membership(s);
- end = std::chrono::system_clock::now();
- auto c2 = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
-
- if (c3 > 0)
- std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_maximal_simplices() << std::endl;
- else
- std::cout << c1 << "\t \t" << c2 << "\t \tN/A\t \t" << K.num_maximal_simplices() << std::endl;
+template <typename complex_type>
+void chrono(int n, int d) {
+ complex_type K;
+ std::vector<Simplex> simplices_insert_simplex1 = r_vector_simplices(n, d, nb_insert_simplex1);
+ std::vector<Simplex> simplices_membership1 = r_vector_simplices(n, d, nb_membership1);
+ std::vector<Simplex> simplices_insert_simplex2 = r_vector_simplices(n - 2 * nb_contraction, d, nb_insert_simplex2);
+ std::vector<Simplex> simplices_membership2 = r_vector_simplices(n - 2 * nb_contraction, d, nb_membership2);
+ std::chrono::time_point<std::chrono::system_clock> start, end;
+
+ for (const Simplex& s : simplices_insert_simplex1) K.insert_simplex(s);
+
+ for (const Simplex& s : simplices_membership1) K.membership(s);
+
+ start = std::chrono::system_clock::now();
+ for (int i = 1; i <= nb_contraction; i++) K.contraction(n - 2 * i, n - 2 * i - 1);
+ end = std::chrono::system_clock::now();
+ auto c3 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
+
+ start = std::chrono::system_clock::now();
+ for (const Simplex& s : simplices_insert_simplex2) K.insert_simplex(s);
+ end = std::chrono::system_clock::now();
+ auto c1 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
+
+ start = std::chrono::system_clock::now();
+ for (const Simplex& s : simplices_membership2) K.membership(s);
+ end = std::chrono::system_clock::now();
+ auto c2 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
+
+ if (c3 > 0)
+ std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_maximal_simplices() << std::endl;
+ else
+ std::cout << c1 << "\t \t" << c2 << "\t \tN/A\t \t" << K.num_maximal_simplices() << std::endl;
}
-int main(){
- for(int d=5;d<=40;d+=5){
- std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl;
- std::cout << "T Map \t \t";
- chrono<Toplex_map>(n,d);
- std::cout << "Lazy \t \t";
- chrono<Lazy_toplex_map>(n,d);
- if(d<=15){
- std::cout << "ST \t \t";
- chrono<ST_wrapper>(n,d);
- }
- std::cout << std::endl;
+int main() {
+ for (int d = 5; d <= 40; d += 5) {
+ std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl;
+ std::cout << "T Map \t \t";
+ chrono<Toplex_map>(n, d);
+ std::cout << "Lazy \t \t";
+ chrono<Lazy_toplex_map>(n, d);
+ if (d <= 15) {
+ std::cout << "ST \t \t";
+ chrono<ST_wrapper>(n, d);
}
+ std::cout << std::endl;
+ }
}
diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h
index 93534e0e..649c27f9 100644
--- a/src/Toplex_map/doc/Intro_Toplex_map.h
+++ b/src/Toplex_map/doc/Intro_Toplex_map.h
@@ -20,8 +20,8 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#ifndef DOC_TOPLEX_MAP_H_
-#define DOC_TOPLEX_MAP_H_
+#ifndef DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_
+#define DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_
// needs namespace for Doxygen to link on classes
namespace Gudhi {
@@ -56,4 +56,4 @@ namespace Gudhi {
} // namespace Gudhi
-#endif // DOC_TOPLEX_MAP_H_
+#endif // DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_
diff --git a/src/Toplex_map/example/simple_toplex_map.cpp b/src/Toplex_map/example/simple_toplex_map.cpp
index 912d79a0..e1c12ed6 100644
--- a/src/Toplex_map/example/simple_toplex_map.cpp
+++ b/src/Toplex_map/example/simple_toplex_map.cpp
@@ -27,7 +27,7 @@
#include <vector>
#include <cassert>
-int main(int argc, char * const argv[]) {
+int main(int argc, char* const argv[]) {
using Simplex = Gudhi::Toplex_map::Simplex;
Simplex sigma1 = {1, 2, 3};
Simplex sigma2 = {2, 3, 4, 5};
@@ -43,7 +43,8 @@ int main(int argc, char * const argv[]) {
/* o---o */
/* 1 3 */
- std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl;
+ std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices()
+ << std::endl;
// Browse maximal cofaces
Simplex sigma3 = {2, 3};
@@ -75,7 +76,8 @@ int main(int argc, char * const argv[]) {
/* \5/ */
/* o */
/* 3 */
- std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl;
+ std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices()
+ << std::endl;
// Browse maximal simplices
std::cout << "Maximal simplices are :" << std::endl;
@@ -97,7 +99,8 @@ int main(int argc, char * const argv[]) {
/* \X/ */
/* o */
/* 5 */
- std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl;
+ std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices()
+ << std::endl;
// Browse maximal simplices
std::cout << "Maximal simplices are :" << std::endl;
@@ -125,7 +128,8 @@ int main(int argc, char * const argv[]) {
/* / \5/ */
/* o---o */
/* 1 3 */
- std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl;
+ std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices()
+ << std::endl;
// Browse maximal simplices
std::cout << "Maximal simplices are :" << std::endl;
@@ -145,7 +149,8 @@ int main(int argc, char * const argv[]) {
/* \5/ */
/* o */
/* 3 */
- std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl;
+ std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices()
+ << std::endl;
// Browse maximal simplices
std::cout << "Maximal simplices are :" << std::endl;
diff --git a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h
index 8cc5610a..63c933d9 100644
--- a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h
+++ b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h
@@ -1,3 +1,25 @@
+/* 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: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * 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 LAZY_TOPLEX_MAP_H
#define LAZY_TOPLEX_MAP_H
@@ -14,8 +36,7 @@ namespace Gudhi {
*
* \ingroup toplex_map */
class Lazy_toplex_map {
-
-public:
+ public:
/** Vertex is the type of vertices. */
using Vertex = Toplex_map::Vertex;
@@ -47,7 +68,6 @@ public:
template <typename Input_vertex_range>
bool membership(const Input_vertex_range &vertex_range);
-
/** Do all the facets of a simplex belong to the complex ? */
template <typename Input_vertex_range>
bool all_facets_inside(const Input_vertex_range &vertex_range);
@@ -58,16 +78,12 @@ public:
Vertex contraction(const Vertex x, const Vertex y);
/** \brief Number of maximal simplices. */
- std::size_t num_maximal_simplices() const {
- return size;
- }
+ std::size_t num_maximal_simplices() const { return size; }
/** \brief Number of vertices. */
- std::size_t num_vertices() const{
- return t0.size();
- }
+ std::size_t num_vertices() const { return t0.size(); }
-private:
+ private:
template <typename Input_vertex_range>
void erase_max(const Input_vertex_range &vertex_range);
template <typename Input_vertex_range>
@@ -77,9 +93,9 @@ private:
std::unordered_map<Vertex, std::size_t> gamma0_lbounds;
std::unordered_map<Vertex, Simplex_ptr_set> t0;
- bool empty_toplex; // Is the empty simplex a toplex ?
+ bool empty_toplex; // Is the empty simplex a toplex ?
- typedef boost::heap::fibonacci_heap<std::pair<std::size_t,Vertex>> PriorityQueue;
+ typedef boost::heap::fibonacci_heap<std::pair<std::size_t, Vertex>> PriorityQueue;
PriorityQueue cleaning_priority;
std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles;
@@ -88,169 +104,168 @@ private:
std::size_t size_lbound = 0;
std::size_t size = 0;
- const double ALPHA = 4; //time
- const double BETTA = 8; //memory
+ const double ALPHA = 4; // time
+ const double BETTA = 8; // memory
};
template <typename Input_vertex_range>
-void Lazy_toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range){
- for(const Vertex& v : vertex_range)
- if(!gamma0_lbounds.count(v)) gamma0_lbounds.emplace(v,1);
- else gamma0_lbounds[v]++;
- size_lbound++;
- insert_simplex(vertex_range);
+void Lazy_toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range) {
+ for (const Vertex &v : vertex_range)
+ if (!gamma0_lbounds.count(v))
+ gamma0_lbounds.emplace(v, 1);
+ else
+ gamma0_lbounds[v]++;
+ size_lbound++;
+ insert_simplex(vertex_range);
}
template <typename Input_vertex_range>
-bool Lazy_toplex_map::insert_simplex(const Input_vertex_range &vertex_range){
- Simplex sigma(vertex_range.begin(),vertex_range.end());
- empty_toplex = (sigma.size()==0); //vérifier la gestion de empty face
- Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
- bool inserted = false;
- for(const Vertex& v : sigma){
- if(!t0.count(v)){
- t0.emplace(v, Simplex_ptr_set());
- auto v_handle = cleaning_priority.push(std::make_pair(0, v));
- cp_handles.emplace(v, v_handle);
- }
- inserted = t0.at(v).emplace(sptr).second;
- cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v),v));
+bool Lazy_toplex_map::insert_simplex(const Input_vertex_range &vertex_range) {
+ Simplex sigma(vertex_range.begin(), vertex_range.end());
+ // Check empty face management
+ empty_toplex = (sigma.size() == 0);
+ Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
+ bool inserted = false;
+ for (const Vertex &v : sigma) {
+ if (!t0.count(v)) {
+ t0.emplace(v, Simplex_ptr_set());
+ auto v_handle = cleaning_priority.push(std::make_pair(0, v));
+ cp_handles.emplace(v, v_handle);
}
- if(inserted)
- size++;
- if(size > (size_lbound+1) * BETTA)
- clean(cleaning_priority.top().second);
- return inserted;
+ inserted = t0.at(v).emplace(sptr).second;
+ cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v), v));
+ }
+ if (inserted) size++;
+ if (size > (size_lbound + 1) * BETTA) clean(cleaning_priority.top().second);
+ return inserted;
}
template <typename Input_vertex_range>
-void Lazy_toplex_map::remove_simplex(const Input_vertex_range &vertex_range){
- if(vertex_range.begin()==vertex_range.end()){
- t0.clear();
- gamma0_lbounds.clear();
- cleaning_priority.clear();
- size_lbound = 0;
- size = 0;
- empty_toplex = false;
- }
- else {
- const Vertex& v = best_index(vertex_range);
- //Copy constructor needed because the set is modified
- if(t0.count(v)) for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v)))
- if(included(vertex_range, *sptr)){
- erase_max(*sptr);
- for(const Simplex& f : facets(vertex_range))
- insert_independent_simplex(f);
- }
- }
+void Lazy_toplex_map::remove_simplex(const Input_vertex_range &vertex_range) {
+ if (vertex_range.begin() == vertex_range.end()) {
+ t0.clear();
+ gamma0_lbounds.clear();
+ cleaning_priority.clear();
+ size_lbound = 0;
+ size = 0;
+ empty_toplex = false;
+ } else {
+ const Vertex &v = best_index(vertex_range);
+ // Copy constructor needed because the set is modified
+ if (t0.count(v))
+ for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v)))
+ if (included(vertex_range, *sptr)) {
+ erase_max(*sptr);
+ for (const Simplex &f : facets(vertex_range)) insert_independent_simplex(f);
+ }
+ }
}
template <typename Input_vertex_range>
-bool Lazy_toplex_map::membership(const Input_vertex_range &vertex_range){
- if(t0.size()==0 && !empty_toplex) return false; //empty complex
- if(vertex_range.begin()==vertex_range.end()) return true; //empty query simplex
- Vertex v = best_index(vertex_range);
- if(!t0.count(v)) return false;
- for(const Simplex_ptr& sptr : t0.at(v))
- if(included(vertex_range, *sptr)) return true;
- return false;
+bool Lazy_toplex_map::membership(const Input_vertex_range &vertex_range) {
+ if (t0.size() == 0 && !empty_toplex) return false; // empty complex
+ if (vertex_range.begin() == vertex_range.end()) return true; // empty query simplex
+ Vertex v = best_index(vertex_range);
+ if (!t0.count(v)) return false;
+ for (const Simplex_ptr &sptr : t0.at(v))
+ if (included(vertex_range, *sptr)) return true;
+ return false;
}
template <typename Input_vertex_range>
-bool Lazy_toplex_map::all_facets_inside(const Input_vertex_range &vertex_range){
- Simplex sigma(vertex_range.begin(),vertex_range.end());
- Vertex v = best_index(sigma);
- if(!t0.count(v)) return false;
- Simplex f = sigma; f.erase(v);
- if(!membership(f)) return false;
- std::unordered_set<Vertex> facets_inside;
- for(const Simplex_ptr& sptr : t0.at(v))
- for(const Vertex& w : sigma){
- f = sigma; f.erase(w);
- if(included(f, *sptr)) facets_inside.insert(w);
- }
- return facets_inside.size() == sigma.size() - 1;
+bool Lazy_toplex_map::all_facets_inside(const Input_vertex_range &vertex_range) {
+ Simplex sigma(vertex_range.begin(), vertex_range.end());
+ Vertex v = best_index(sigma);
+ if (!t0.count(v)) return false;
+ Simplex f = sigma;
+ f.erase(v);
+ if (!membership(f)) return false;
+ std::unordered_set<Vertex> facets_inside;
+ for (const Simplex_ptr &sptr : t0.at(v))
+ for (const Vertex &w : sigma) {
+ f = sigma;
+ f.erase(w);
+ if (included(f, *sptr)) facets_inside.insert(w);
+ }
+ return facets_inside.size() == sigma.size() - 1;
}
/* Returns the remaining vertex */
-Lazy_toplex_map::Vertex Lazy_toplex_map::contraction(const Vertex x, const Vertex y){
- if(!t0.count(x)) return y;
- if(!t0.count(y)) return x;
- Vertex k, d;
- if(t0.at(x).size() > t0.at(y).size())
- k=x, d=y;
- else
- k=y, d=x;
- //Copy constructor needed because the set is modified
- for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){
- Simplex sigma(*sptr);
- erase_max(sigma);
- sigma.erase(d);
- sigma.insert(k);
- insert_simplex(sigma);
- }
- t0.erase(d);
- return k;
+Lazy_toplex_map::Vertex Lazy_toplex_map::contraction(const Vertex x, const Vertex y) {
+ if (!t0.count(x)) return y;
+ if (!t0.count(y)) return x;
+ Vertex k, d;
+ if (t0.at(x).size() > t0.at(y).size())
+ k = x, d = y;
+ else
+ k = y, d = x;
+ // Copy constructor needed because the set is modified
+ for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(d))) {
+ Simplex sigma(*sptr);
+ erase_max(sigma);
+ sigma.erase(d);
+ sigma.insert(k);
+ insert_simplex(sigma);
+ }
+ t0.erase(d);
+ return k;
}
/* No facets insert_simplexed */
template <typename Input_vertex_range>
-inline void Lazy_toplex_map::erase_max(const Input_vertex_range &vertex_range){
- Simplex sigma(vertex_range.begin(),vertex_range.end());
- empty_toplex = false;
- Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
- bool erased=false;
- for(const Vertex& v : sigma){
- erased = t0.at(v).erase(sptr) > 0;
- if(t0.at(v).size()==0)
- t0.erase(v);
- }
- if (erased)
- size--;
+inline void Lazy_toplex_map::erase_max(const Input_vertex_range &vertex_range) {
+ Simplex sigma(vertex_range.begin(), vertex_range.end());
+ empty_toplex = false;
+ Simplex_ptr sptr = std::make_shared<Simplex>(sigma);
+ bool erased = false;
+ for (const Vertex &v : sigma) {
+ erased = t0.at(v).erase(sptr) > 0;
+ if (t0.at(v).size() == 0) t0.erase(v);
+ }
+ if (erased) size--;
}
template <typename Input_vertex_range>
Lazy_toplex_map::Vertex Lazy_toplex_map::best_index(const Input_vertex_range &vertex_range) {
- Simplex tau(vertex_range.begin(),vertex_range.end());
- std::size_t min = std::numeric_limits<size_t>::max(); Vertex arg_min = -1;
- for(const Vertex& v : tau)
- if(!t0.count(v)) return v;
- else if(t0.at(v).size() < min)
- min = t0.at(v).size(), arg_min = v;
- if(min > ALPHA * get_gamma0_lbound(arg_min))
- clean(arg_min);
- return arg_min;
+ Simplex tau(vertex_range.begin(), vertex_range.end());
+ std::size_t min = std::numeric_limits<size_t>::max();
+ Vertex arg_min = -1;
+ for (const Vertex &v : tau)
+ if (!t0.count(v))
+ return v;
+ else if (t0.at(v).size() < min)
+ min = t0.at(v).size(), arg_min = v;
+ if (min > ALPHA * get_gamma0_lbound(arg_min)) clean(arg_min);
+ return arg_min;
}
-std::size_t Lazy_toplex_map::get_gamma0_lbound(const Vertex v) const{
- return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0;
+std::size_t Lazy_toplex_map::get_gamma0_lbound(const Vertex v) const {
+ return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0;
}
-void Lazy_toplex_map::clean(const Vertex v){
- Toplex_map toplices;
- std::unordered_map<int, std::vector<Simplex>> dsorted_simplices;
- std::size_t max_dim = 0;
- for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){
- if(sptr->size() > max_dim){
- for(std::size_t d = max_dim+1; d<=sptr->size(); d++)
- dsorted_simplices.emplace(d, std::vector<Simplex>());
- max_dim = sptr->size();
- }
- dsorted_simplices[sptr->size()].emplace_back(*sptr);
- erase_max(*sptr);
+void Lazy_toplex_map::clean(const Vertex v) {
+ Toplex_map toplices;
+ std::unordered_map<int, std::vector<Simplex>> dsorted_simplices;
+ std::size_t max_dim = 0;
+ for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v))) {
+ if (sptr->size() > max_dim) {
+ for (std::size_t d = max_dim + 1; d <= sptr->size(); d++) dsorted_simplices.emplace(d, std::vector<Simplex>());
+ max_dim = sptr->size();
}
- for(std::size_t d = max_dim; d>=1; d--)
- for(const Simplex &s : dsorted_simplices.at(d))
- if(!toplices.membership(s))
- toplices.insert_independent_simplex(s);
- Simplex sv; sv.insert(v);
- auto clean_cofaces = toplices.maximal_cofaces(sv);
- size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size();
- gamma0_lbounds[v] = clean_cofaces.size();
- for(const Simplex_ptr& sptr : clean_cofaces)
- insert_simplex(*sptr);
+ dsorted_simplices[sptr->size()].emplace_back(*sptr);
+ erase_max(*sptr);
+ }
+ for (std::size_t d = max_dim; d >= 1; d--)
+ for (const Simplex &s : dsorted_simplices.at(d))
+ if (!toplices.membership(s)) toplices.insert_independent_simplex(s);
+ Simplex sv;
+ sv.insert(v);
+ auto clean_cofaces = toplices.maximal_cofaces(sv);
+ size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size();
+ gamma0_lbounds[v] = clean_cofaces.size();
+ for (const Simplex_ptr &sptr : clean_cofaces) insert_simplex(*sptr);
}
-} //namespace Gudhi
+} // namespace Gudhi
#endif /* LAZY_TOPLEX_MAP_H */
diff --git a/src/Toplex_map/include/gudhi/Toplex_map.h b/src/Toplex_map/include/gudhi/Toplex_map.h
index b7a5db41..3da505f8 100644
--- a/src/Toplex_map/include/gudhi/Toplex_map.h
+++ b/src/Toplex_map/include/gudhi/Toplex_map.h
@@ -1,3 +1,25 @@
+/* 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: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * 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 TOPLEX_MAP_H
#define TOPLEX_MAP_H
@@ -17,9 +39,7 @@ namespace Gudhi {
*
* \ingroup toplex_map */
class Toplex_map {
-
-public:
-
+ public:
/** Vertex is the type of vertices. */
using Vertex = std::size_t;
@@ -33,7 +53,7 @@ public:
std::size_t operator()(const Toplex_map::Simplex_ptr& s) const;
};
- struct Sptr_equal{
+ struct Sptr_equal {
std::size_t operator()(const Toplex_map::Simplex_ptr& a, const Toplex_map::Simplex_ptr& b) const;
};
@@ -43,26 +63,27 @@ public:
/** \brief Adds the given simplex to the complex.
* Nothing happens if the simplex has a coface in the complex. */
template <typename Input_vertex_range>
- void insert_simplex(const Input_vertex_range &vertex_range);
+ void insert_simplex(const Input_vertex_range& vertex_range);
/** \brief Removes the given simplex and its cofaces from the complex.
* Its faces are kept inside. */
template <typename Input_vertex_range>
- void remove_simplex(const Input_vertex_range &vertex_range);
+ void remove_simplex(const Input_vertex_range& vertex_range);
/** Does a simplex belong to the complex ? */
template <typename Input_vertex_range>
- bool membership(const Input_vertex_range &vertex_range) const;
+ bool membership(const Input_vertex_range& vertex_range) const;
/** Does a simplex is a toplex ? */
template <typename Input_vertex_range>
- bool maximality(const Input_vertex_range &vertex_range) const;
+ bool maximality(const Input_vertex_range& vertex_range) const;
/** Gives a set of pointers to the maximal cofaces of a simplex.
* Gives all the toplices if given the empty simplex.
* Gives not more than max_number maximal cofaces if max_number is strictly positive. */
template <typename Input_vertex_range>
- Toplex_map::Simplex_ptr_set maximal_cofaces(const Input_vertex_range &vertex_range, const std::size_t max_number = 0) const;
+ Toplex_map::Simplex_ptr_set maximal_cofaces(const Input_vertex_range& vertex_range,
+ const std::size_t max_number = 0) const;
/** Gives a set of pointers to the maximal simplices.
* Gives not more than max_number maximal cofaces if max_number is strictly positive. */
@@ -79,26 +100,22 @@ public:
void remove_vertex(const Toplex_map::Vertex x);
/** \brief Number of maximal simplices. */
- std::size_t num_maximal_simplices() const {
- return maximal_simplices().size();
- }
+ std::size_t num_maximal_simplices() const { return maximal_simplices().size(); }
/** \brief Number of vertices. */
- std::size_t num_vertices() const {
- return t0.size();
- }
+ std::size_t num_vertices() const { return t0.size(); }
std::set<Toplex_map::Vertex> unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d);
/** Adds the given simplex to the complex.
* The simplex must not have neither maximal face nor coface in the complex. */
template <typename Input_vertex_range>
- void insert_independent_simplex(const Input_vertex_range &vertex_range);
+ void insert_independent_simplex(const Input_vertex_range& vertex_range);
-protected:
+ protected:
/** \internal Gives an index in order to look for a simplex quickly. */
template <typename Input_vertex_range>
- Toplex_map::Vertex best_index(const Input_vertex_range &vertex_range) const;
+ Toplex_map::Vertex best_index(const Input_vertex_range& vertex_range) const;
/** \internal The map from vertices to toplices */
std::unordered_map<Toplex_map::Vertex, Toplex_map::Simplex_ptr_set> t0;
@@ -107,219 +124,215 @@ protected:
/** \internal Removes a toplex without adding facets after. */
void erase_maximal(const Toplex_map::Simplex_ptr& sptr);
-
};
// Pointers are also used as key in the hash sets.
template <typename Input_vertex_range>
-Toplex_map::Simplex_ptr get_key(const Input_vertex_range &vertex_range);
+Toplex_map::Simplex_ptr get_key(const Input_vertex_range& vertex_range);
// Is the first simplex a face of the second ?
template <typename Input_vertex_range1, typename Input_vertex_range2>
-bool included(const Input_vertex_range1 &vertex_range1, const Input_vertex_range2 &vertex_range2);
+bool included(const Input_vertex_range1& vertex_range1, const Input_vertex_range2& vertex_range2);
// All the facets of the given simplex.
template <typename Input_vertex_range>
-std::vector<Toplex_map::Simplex> facets(const Input_vertex_range &vertex_range);
+std::vector<Toplex_map::Simplex> facets(const Input_vertex_range& vertex_range);
template <typename Input_vertex_range>
-void Toplex_map::insert_simplex(const Input_vertex_range &vertex_range){
- if(membership(vertex_range)) return;
- bool replace_facets = true;
- for(const Toplex_map::Simplex& facet : facets(vertex_range))
- if(!maximality(facet))
- {
- replace_facets=false;
- break;
- }
- if(replace_facets)
- for(const Toplex_map::Simplex& facet : facets(vertex_range))
- erase_maximal(get_key(facet));
- else
- for(const Toplex_map::Vertex& v : vertex_range)
- if(t0.count(v)) for(const Toplex_map::Simplex_ptr& fptr : Simplex_ptr_set(t0.at(v)))
- //Copy constructor needed because the set is modified
- if(included(*fptr,vertex_range)) erase_maximal(fptr);
- // We erase all the maximal faces of the simplex
- insert_independent_simplex(vertex_range);
+void Toplex_map::insert_simplex(const Input_vertex_range& vertex_range) {
+ if (membership(vertex_range)) return;
+ bool replace_facets = true;
+ for (const Toplex_map::Simplex& facet : facets(vertex_range))
+ if (!maximality(facet)) {
+ replace_facets = false;
+ break;
+ }
+ if (replace_facets)
+ for (const Toplex_map::Simplex& facet : facets(vertex_range)) erase_maximal(get_key(facet));
+ else
+ for (const Toplex_map::Vertex& v : vertex_range)
+ if (t0.count(v))
+ for (const Toplex_map::Simplex_ptr& fptr : Simplex_ptr_set(t0.at(v)))
+ // Copy constructor needed because the set is modified
+ if (included(*fptr, vertex_range)) erase_maximal(fptr);
+ // We erase all the maximal faces of the simplex
+ insert_independent_simplex(vertex_range);
}
template <typename Input_vertex_range>
-void Toplex_map::remove_simplex(const Input_vertex_range &vertex_range){
- if(vertex_range.begin()==vertex_range.end())
- t0.clear();
- // Removal of the empty simplex means cleaning everything
- else {
- const Toplex_map::Vertex& v = best_index(vertex_range);
- if(t0.count(v)) for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v)))
- //Copy constructor needed because the set is modified
- if(included(vertex_range, *sptr)){
- erase_maximal(sptr);
- for(const Toplex_map::Simplex& f : facets(vertex_range))
- if(!membership(f)) insert_independent_simplex(f);
- // We add the facets which are new maximal simplices
- }
- }
+void Toplex_map::remove_simplex(const Input_vertex_range& vertex_range) {
+ if (vertex_range.begin() == vertex_range.end()) t0.clear();
+ // Removal of the empty simplex means cleaning everything
+ else {
+ const Toplex_map::Vertex& v = best_index(vertex_range);
+ if (t0.count(v))
+ for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v)))
+ // Copy constructor needed because the set is modified
+ if (included(vertex_range, *sptr)) {
+ erase_maximal(sptr);
+ for (const Toplex_map::Simplex& f : facets(vertex_range))
+ if (!membership(f)) insert_independent_simplex(f);
+ // We add the facets which are new maximal simplices
+ }
+ }
}
template <typename Input_vertex_range>
-bool Toplex_map::membership(const Input_vertex_range &vertex_range) const{
- if(t0.size()==0) return false;
- const Toplex_map::Vertex& v = best_index(vertex_range);
- if(!t0.count(v)) return false;
- if(maximality(vertex_range)) return true;
- for(const Toplex_map::Simplex_ptr& sptr : t0.at(v))
- if(included(vertex_range, *sptr))
- return true;
- return false;
+bool Toplex_map::membership(const Input_vertex_range& vertex_range) const {
+ if (t0.size() == 0) return false;
+ const Toplex_map::Vertex& v = best_index(vertex_range);
+ if (!t0.count(v)) return false;
+ if (maximality(vertex_range)) return true;
+ for (const Toplex_map::Simplex_ptr& sptr : t0.at(v))
+ if (included(vertex_range, *sptr)) return true;
+ return false;
}
template <typename Input_vertex_range>
-bool Toplex_map::maximality(const Input_vertex_range &vertex_range) const{
- const Toplex_map::Vertex& v = best_index(vertex_range);
- if(!t0.count(v)) return false;
- return t0.at(v).count(get_key(vertex_range));
+bool Toplex_map::maximality(const Input_vertex_range& vertex_range) const {
+ const Toplex_map::Vertex& v = best_index(vertex_range);
+ if (!t0.count(v)) return false;
+ return t0.at(v).count(get_key(vertex_range));
}
template <typename Input_vertex_range>
-Toplex_map::Simplex_ptr_set Toplex_map::maximal_cofaces(const Input_vertex_range &vertex_range, const std::size_t max_number) const{
- Simplex_ptr_set cofaces;
- if(maximality(vertex_range))
- cofaces.emplace(get_key(vertex_range));
- else if(vertex_range.begin()==vertex_range.end())
- for(const auto& kv : t0)
- for(const Toplex_map::Simplex_ptr& sptr : kv.second){
- //kv.second is a Simplex_ptr_set
- cofaces.emplace(sptr);
- if(cofaces.size()==max_number)
- return cofaces;
- }
- else {
- const Toplex_map::Vertex& v = best_index(vertex_range);
- if(t0.count(v)) for(const Toplex_map::Simplex_ptr& sptr : t0.at(v))
- if(included(vertex_range, *sptr)){
- cofaces.emplace(sptr);
- if(cofaces.size()==max_number)
- return cofaces;
- }
- }
- return cofaces;
+Toplex_map::Simplex_ptr_set Toplex_map::maximal_cofaces(const Input_vertex_range& vertex_range,
+ const std::size_t max_number) const {
+ Simplex_ptr_set cofaces;
+ if (maximality(vertex_range))
+ cofaces.emplace(get_key(vertex_range));
+ else if (vertex_range.begin() == vertex_range.end())
+ for (const auto& kv : t0)
+ for (const Toplex_map::Simplex_ptr& sptr : kv.second) {
+ // kv.second is a Simplex_ptr_set
+ cofaces.emplace(sptr);
+ if (cofaces.size() == max_number) return cofaces;
+ }
+ else {
+ const Toplex_map::Vertex& v = best_index(vertex_range);
+ if (t0.count(v))
+ for (const Toplex_map::Simplex_ptr& sptr : t0.at(v))
+ if (included(vertex_range, *sptr)) {
+ cofaces.emplace(sptr);
+ if (cofaces.size() == max_number) return cofaces;
+ }
+ }
+ return cofaces;
}
-Toplex_map::Vertex Toplex_map::contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y){
- if(!t0.count(x)) return y;
- if(!t0.count(y)) return x;
- int k, d;
- if(t0.at(x).size() > t0.at(y).size())
- k=x, d=y;
- else
- k=y, d=x;
- for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){
- //Copy constructor needed because the set is modified
- Simplex sigma(*sptr);
- erase_maximal(sptr);
- sigma.erase(d);
- sigma.insert(k);
- insert_simplex(sigma);
- }
- return k;
+Toplex_map::Vertex Toplex_map::contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y) {
+ if (!t0.count(x)) return y;
+ if (!t0.count(y)) return x;
+ int k, d;
+ if (t0.at(x).size() > t0.at(y).size())
+ k = x, d = y;
+ else
+ k = y, d = x;
+ for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))) {
+ // Copy constructor needed because the set is modified
+ Simplex sigma(*sptr);
+ erase_maximal(sptr);
+ sigma.erase(d);
+ sigma.insert(k);
+ insert_simplex(sigma);
+ }
+ return k;
}
-std::set<Toplex_map::Vertex> Toplex_map::unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d){
- std::set<Toplex_map::Vertex> r;
- for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){
- //Copy constructor needed because the set is modified
- Simplex sigma(*sptr);
- erase_maximal(sptr);
- sigma.erase(d);
- for(const Toplex_map::Vertex v : sigma)
- r.insert(v);
- sigma.insert(k);
- insert_simplex(sigma);
- }
- return r;
+std::set<Toplex_map::Vertex> Toplex_map::unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d) {
+ std::set<Toplex_map::Vertex> r;
+ for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))) {
+ // Copy constructor needed because the set is modified
+ Simplex sigma(*sptr);
+ erase_maximal(sptr);
+ sigma.erase(d);
+ for (const Toplex_map::Vertex v : sigma) r.insert(v);
+ sigma.insert(k);
+ insert_simplex(sigma);
+ }
+ return r;
}
template <typename Input_vertex_range>
-void Toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range){
- auto key = get_key(vertex_range);
- for(const Toplex_map::Vertex& v : vertex_range){
- if(!t0.count(v)) t0.emplace(v, Simplex_ptr_set());
- t0.at(v).emplace(key);
- }
+void Toplex_map::insert_independent_simplex(const Input_vertex_range& vertex_range) {
+ auto key = get_key(vertex_range);
+ for (const Toplex_map::Vertex& v : vertex_range) {
+ if (!t0.count(v)) t0.emplace(v, Simplex_ptr_set());
+ t0.at(v).emplace(key);
+ }
}
-void Toplex_map::remove_vertex(const Toplex_map::Vertex x){
- for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(x))){
- Simplex sigma(*sptr);
- erase_maximal(sptr);
- sigma.erase(x);
- insert_simplex(sigma);
- }
+void Toplex_map::remove_vertex(const Toplex_map::Vertex x) {
+ for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(x))) {
+ Simplex sigma(*sptr);
+ erase_maximal(sptr);
+ sigma.erase(x);
+ insert_simplex(sigma);
+ }
}
-inline void Toplex_map::erase_maximal(const Toplex_map::Simplex_ptr& sptr){
- Simplex sigma(*sptr);
- if (sptr->size()==0)
- sigma.insert(VERTEX_UPPER_BOUND);
- for(const Toplex_map::Vertex& v : sigma){
- t0.at(v).erase(sptr);
- if(t0.at(v).size()==0) t0.erase(v);
- }
+inline void Toplex_map::erase_maximal(const Toplex_map::Simplex_ptr& sptr) {
+ Simplex sigma(*sptr);
+ if (sptr->size() == 0) sigma.insert(VERTEX_UPPER_BOUND);
+ for (const Toplex_map::Vertex& v : sigma) {
+ t0.at(v).erase(sptr);
+ if (t0.at(v).size() == 0) t0.erase(v);
+ }
}
template <typename Input_vertex_range>
-Toplex_map::Vertex Toplex_map::best_index(const Input_vertex_range &vertex_range) const{
- std::size_t min = std::numeric_limits<size_t>::max();
- Vertex arg_min = VERTEX_UPPER_BOUND;
- for(const Toplex_map::Vertex& v : vertex_range)
- if(!t0.count(v)) return v;
- else if(t0.at(v).size() < min)
- min = t0.at(v).size(), arg_min = v;
- return arg_min;
+Toplex_map::Vertex Toplex_map::best_index(const Input_vertex_range& vertex_range) const {
+ std::size_t min = std::numeric_limits<size_t>::max();
+ Vertex arg_min = VERTEX_UPPER_BOUND;
+ for (const Toplex_map::Vertex& v : vertex_range)
+ if (!t0.count(v))
+ return v;
+ else if (t0.at(v).size() < min)
+ min = t0.at(v).size(), arg_min = v;
+ return arg_min;
}
-std::size_t Toplex_map::Sptr_equal::operator()(const Toplex_map::Simplex_ptr& s1, const Toplex_map::Simplex_ptr& s2) const {
- if (s1->size() != s2->size()) return false;
- return included(*s1,*s2);
- // inclusion tests equality for same size simplices
+std::size_t Toplex_map::Sptr_equal::operator()(const Toplex_map::Simplex_ptr& s1,
+ const Toplex_map::Simplex_ptr& s2) const {
+ if (s1->size() != s2->size()) return false;
+ return included(*s1, *s2);
+ // inclusion tests equality for same size simplices
}
std::size_t Toplex_map::Sptr_hash::operator()(const Toplex_map::Simplex_ptr& s) const {
- std::hash<double> h_f;
- //double hash works better than int hash
- size_t h = 0;
- for(const Toplex_map::Vertex& v : *s)
- h += h_f(static_cast<double>(v));
- return h;
+ std::hash<double> h_f;
+ // double hash works better than int hash
+ size_t h = 0;
+ for (const Toplex_map::Vertex& v : *s) h += h_f(static_cast<double>(v));
+ return h;
}
template <typename Input_vertex_range>
-Toplex_map::Simplex_ptr get_key(const Input_vertex_range &vertex_range){
- Toplex_map::Simplex s(vertex_range.begin(), vertex_range.end());
- return std::make_shared<Toplex_map::Simplex>(s);
+Toplex_map::Simplex_ptr get_key(const Input_vertex_range& vertex_range) {
+ Toplex_map::Simplex s(vertex_range.begin(), vertex_range.end());
+ return std::make_shared<Toplex_map::Simplex>(s);
}
template <typename Input_vertex_range1, typename Input_vertex_range2>
-bool included(const Input_vertex_range1 &vertex_range1, const Input_vertex_range2 &vertex_range2){
- Toplex_map::Simplex s2(vertex_range2.begin(), vertex_range2.end());
- for(const Toplex_map::Vertex& v : vertex_range1)
- if(!s2.count(v)) return false;
- return true;
+bool included(const Input_vertex_range1& vertex_range1, const Input_vertex_range2& vertex_range2) {
+ Toplex_map::Simplex s2(vertex_range2.begin(), vertex_range2.end());
+ for (const Toplex_map::Vertex& v : vertex_range1)
+ if (!s2.count(v)) return false;
+ return true;
}
template <typename Input_vertex_range>
-std::vector<Toplex_map::Simplex> facets(const Input_vertex_range &vertex_range){
- std::vector<Toplex_map::Simplex> facets;
- Toplex_map::Simplex f(vertex_range.begin(), vertex_range.end());
- for(const Toplex_map::Vertex& v : vertex_range){
- f.erase(v);
- facets.emplace_back(f);
- f.insert(v);
- }
- return facets;
+std::vector<Toplex_map::Simplex> facets(const Input_vertex_range& vertex_range) {
+ std::vector<Toplex_map::Simplex> facets;
+ Toplex_map::Simplex f(vertex_range.begin(), vertex_range.end());
+ for (const Toplex_map::Vertex& v : vertex_range) {
+ f.erase(v);
+ facets.emplace_back(f);
+ f.insert(v);
+ }
+ return facets;
}
-} //namespace Gudhi
+} // namespace Gudhi
#endif /* TOPLEX_MAP_H */
diff --git a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp
index 5d71c295..eb1aa0b5 100644
--- a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp
+++ b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp
@@ -1,8 +1,29 @@
+/* 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: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * 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/>.
+ */
+
#include <iostream>
#include <vector>
#include <gudhi/Lazy_toplex_map.h>
-
#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE "lazy toplex map"
#include <boost/test/unit_test.hpp>
@@ -43,7 +64,7 @@ BOOST_AUTO_TEST_CASE(toplex_map) {
BOOST_CHECK(tm.membership(sigma5));
std::cout << "contraction(4,5)" << std::endl;
- auto r = tm.contraction(4,5);
+ auto r = tm.contraction(4, 5);
std::cout << "r=" << r << std::endl;
BOOST_CHECK(r == 5);
@@ -73,6 +94,4 @@ BOOST_AUTO_TEST_CASE(toplex_map) {
BOOST_CHECK(tm.membership(edge));
edge = {7, 5};
BOOST_CHECK(tm.membership(edge));
-
}
-
diff --git a/src/Toplex_map/test/toplex_map_unit_test.cpp b/src/Toplex_map/test/toplex_map_unit_test.cpp
index 59c104ce..2bd27936 100644
--- a/src/Toplex_map/test/toplex_map_unit_test.cpp
+++ b/src/Toplex_map/test/toplex_map_unit_test.cpp
@@ -1,8 +1,29 @@
+/* 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: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * 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/>.
+ */
+
#include <iostream>
#include <vector>
#include <gudhi/Toplex_map.h>
-
#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MODULE "toplex map"
#include <boost/test/unit_test.hpp>
@@ -67,7 +88,7 @@ BOOST_AUTO_TEST_CASE(toplex_map) {
BOOST_CHECK(tm.membership(sigma5));
std::cout << "contraction(4,5)" << std::endl;
- auto r = tm.contraction(4,5);
+ auto r = tm.contraction(4, 5);
std::cout << "r=" << r << std::endl;
BOOST_CHECK(r == 5);
@@ -114,6 +135,4 @@ BOOST_AUTO_TEST_CASE(toplex_map) {
BOOST_CHECK(tm.membership(edge));
edge = {7, 5};
BOOST_CHECK(tm.membership(edge));
-
}
-