summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorfgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb>2017-10-25 11:19:00 +0000
committerfgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb>2017-10-25 11:19:00 +0000
commit23e265d8c48d921a51eb0265afa6d8af27b27559 (patch)
treef008c1dc24209204ede4b69386f6bf56513a72c2 /src
parent8fd07bda067d82fd0d345c3bde0dce7de18a6722 (diff)
include limits in toplex_map
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2804 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: a42cc7c557c193c57e3696eb0b877f6196841aaf
Diffstat (limited to 'src')
-rw-r--r--src/Rips_complex/example/CMakeLists.txt2
-rw-r--r--src/Rips_complex/example/example_rips_complex_from_fvecs.cpp67
-rw-r--r--src/Toplex_map/include/gudhi/Fake_simplex_tree.h142
-rw-r--r--src/Toplex_map/include/gudhi/Filtered_toplex_map.h8
-rw-r--r--src/Toplex_map/include/gudhi/Toplex_map.h30
-rw-r--r--src/Witness_complex/example/CMakeLists.txt2
-rw-r--r--src/Witness_complex/example/example_strong_witness_complex_off.cpp4
7 files changed, 153 insertions, 102 deletions
diff --git a/src/Rips_complex/example/CMakeLists.txt b/src/Rips_complex/example/CMakeLists.txt
index 2940f164..b854b1c9 100644
--- a/src/Rips_complex/example/CMakeLists.txt
+++ b/src/Rips_complex/example/CMakeLists.txt
@@ -4,6 +4,8 @@ project(Rips_complex_examples)
# Point cloud
add_executable ( Rips_complex_example_from_off example_rips_complex_from_off_file.cpp )
+add_executable ( Rips_complex_example_from_fvecs example_rips_complex_from_fvecs.cpp )
+
add_executable ( Rips_complex_example_one_skeleton_from_points example_one_skeleton_rips_from_points.cpp )
# Distance matrix
diff --git a/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp b/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp
new file mode 100644
index 00000000..c05d038a
--- /dev/null
+++ b/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp
@@ -0,0 +1,67 @@
+#include <gudhi/Rips_complex.h>
+// to construct Rips_complex from a fvecs file of points
+#include <gudhi/Simplex_tree.h>
+#include <gudhi/Fake_simplex_tree.h>
+#include <gudhi/distance_functions.h>
+#include <gudhi/Points_fvecs_reader.h>
+
+#include <CGAL/Epick_d.h>
+
+#include <iostream>
+#include <string>
+#include <vector>
+
+void usage(int nbArgs, char * const progName) {
+ std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n";
+ std::cerr << "Usage: " << progName << " filename.fvecs threshold dim_max [ouput_file.txt]\n";
+ std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.fvecs 60.0\n";
+ exit(-1); // ----- >>
+}
+
+int main(int argc, char **argv) {
+ if ((argc != 4) && (argc != 5)) usage(argc, (argv[0] - 1));
+
+ std::string file_name(argv[1]);
+ double threshold = atof(argv[2]);
+ int dim_max = atoi(argv[3]);
+
+ // Type definitions
+ using K = CGAL::Epick_d<CGAL::Dynamic_dimension_tag>;
+ using Point = typename K::Point_d;
+ //using Simplex_tree = Gudhi::Simplex_tree<>;
+ using Simplex_tree = Gudhi::Fake_simplex_tree;
+ using Filtration_value = Simplex_tree::Filtration_value;
+ using Rips_complex = Gudhi::rips_complex::Rips_complex<Filtration_value>;
+ using Point_vector = std::vector<Point>;
+
+ // ----------------------------------------------------------------------------
+ // Init of a Rips complex from an fvecs file
+ // ----------------------------------------------------------------------------
+ Point_vector point_vector;
+ Gudhi::load_points_from_fvecs_file<K>(file_name, std::back_insert_iterator< Point_vector >(point_vector));
+
+ Rips_complex rips_complex_from_file(point_vector, threshold, Gudhi::Euclidean_distance());
+
+ std::streambuf* streambufffer;
+ std::ofstream ouput_file_stream;
+
+ if (argc == 5) {
+ ouput_file_stream.open(std::string(argv[4]));
+ streambufffer = ouput_file_stream.rdbuf();
+ } else {
+ streambufffer = std::cout.rdbuf();
+ }
+
+ Simplex_tree stree;
+ rips_complex_from_file.create_complex(stree, dim_max);
+ std::ostream output_stream(streambufffer);
+
+ // ----------------------------------------------------------------------------
+ // Display information about the Rips complex
+ // ----------------------------------------------------------------------------
+ output_stream << "Rips complex is of dimension " << stree.dimension() <<
+ " - " << stree.num_simplices() << " simplices." << std::endl;
+
+ ouput_file_stream.close();
+ return 0;
+}
diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h
index 10ef39d7..b318acb4 100644
--- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h
+++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h
@@ -1,9 +1,12 @@
#ifndef FAKE_SIMPLEX_TREE_H
#define FAKE_SIMPLEX_TREE_H
+#include <gudhi/Simplex_tree.h>
#include <gudhi/Filtered_toplex_map.h>
+
#include <boost/graph/adjacency_list.hpp>
+
namespace Gudhi {
class Fake_simplex_tree : public Filtered_toplex_map {
@@ -12,7 +15,7 @@ public:
typedef Vertex Vertex_handle;
- typedef Simplex_ptr Simplex_handle;
+ typedef Simplex Simplex_handle;
typedef void Insertion_result_type;
@@ -36,20 +39,16 @@ public:
void set_dimension(int d);
- Simplex simplex_vertex_range(Simplex_ptr &sptr) const;
+ Simplex simplex_vertex_range(const Simplex& s) const;
- std::vector<Simplex_ptr> max_simplices() const;
+ std::vector<Simplex> max_simplices() const;
- std::unordered_set<Simplex_ptr> filtration_simplex_range() const;
+ std::vector<Simplex> filtration_simplex_range() const;
- std::unordered_set<Simplex_ptr> skeleton_simplex_range(int d=std::numeric_limits<int>::max()) const;
+ std::vector<Simplex> skeleton_simplex_range(int d=std::numeric_limits<int>::max()) const;
std::size_t dimension(Simplex_ptr& sptr) const;
- void assign_filtration(Simplex_ptr& f_simplex, Filtration_value alpha_complex_filtration);
-
- void make_filtration_non_decreasing();
-
protected:
/** \internal Does all the facets of the given simplex belong to the complex ?
@@ -65,28 +64,34 @@ void Fake_simplex_tree::set_dimension(int d){
template<class OneSkeletonGraph>
void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){
- typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it,
- e_it_end;
+ if (boost::num_vertices(skel_graph) == 0) return;
+ typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it, v_it_end;
+ for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end; ++v_it){
+ Simplex s;
+ s.insert(*v_it);
+ insert_simplex_and_subfaces(s, boost::get(vertex_filtration_t(), skel_graph, *v_it));
+ }
+
+ typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it, e_it_end;
for (std::tie(e_it, e_it_end) = boost::edges(skel_graph); e_it != e_it_end; ++e_it) {
- auto u = source(*e_it, skel_graph);
- auto v = target(*e_it, skel_graph);
- if(u<v){
+ Vertex u = source(*e_it, skel_graph);
+ Vertex v = target(*e_it, skel_graph);
+ if (u < v) {
Simplex s;
- s.emplace(u);
- s.emplace(v);
- insert_simplex_and_subfaces(s);
+ s.insert(u);
+ s.insert(v);
+ insert_simplex_and_subfaces(s, boost::get(edge_filtration_t(), skel_graph, *e_it));
}
}
}
void Fake_simplex_tree::expansion(int max_dim){
- for(int d=3; d <= max_dim; d++){
- auto cs = candidates();
+ for(int d=2; d <= max_dim; d++){
+ Simplex_ptr_set cs = candidates(); //dimension ?
+ if(cs.empty()) std::cout << d << std::endl;
if(cs.empty()) return;
- for(const Simplex_ptr& sptr: cs){
- Simplex sigma = *sptr;
- insert_simplex_and_subfaces(sigma);
- }
+ for(const Simplex_ptr& sptr: cs)
+ insert_simplex_and_subfaces(*sptr); //filtration ?
}
}
@@ -100,16 +105,18 @@ bool Fake_simplex_tree::all_facets_inside(const Input_vertex_range &vertex_range
Simplex_ptr_set Fake_simplex_tree::candidates() const{
Simplex_ptr_set c;
- std::unordered_map<Simplex_ptr, std::vector<Vertex>, Toplex_map::Sptr_hash, Toplex_map::Sptr_equal> facets_to_max;
+ std::unordered_map<Simplex_ptr, std::vector<Vertex>, Sptr_hash, Sptr_equal> facets_to_max;
for(const auto& kv : filtrations){
Simplex sigma (*(kv.first));
- for(Vertex v : sigma){
- sigma.erase(v);
- auto sptr = get_key(sigma);
- if(!facets_to_max.count(sptr)) facets_to_max.emplace(sptr, std::vector<Vertex>());
- facets_to_max.at(sptr).emplace_back(v);
- sigma.insert(v);
- }
+ if(sigma.size()>1)
+ for(Vertex v : *(kv.first)){
+ sigma.erase(v);
+ auto sptr = get_key(sigma);
+ if(!facets_to_max.count(sptr))
+ facets_to_max.emplace(sptr, std::vector<Vertex>());
+ facets_to_max.at(sptr).emplace_back(v);
+ sigma.insert(v);
+ }
}
for(const auto& kv : facets_to_max){
std::unordered_set<Vertex> facets(kv.second.begin(), kv.second.end());
@@ -132,11 +139,12 @@ std::size_t Fake_simplex_tree::dimension() const {
std::size_t max = 0;
for(auto kv : filtrations)
max = std::max(max, kv.first->size());
- return max;
+ return max-1;
}
std::size_t Fake_simplex_tree::num_simplices() const {
- return filtration_simplex_range().size();
+ //return filtration_simplex_range().size();
+ return max_simplices().size();
}
std::size_t Fake_simplex_tree::num_vertices() const {
@@ -147,42 +155,40 @@ std::size_t Fake_simplex_tree::num_vertices() const {
return vertices.size();
}
-Simplex Fake_simplex_tree::simplex_vertex_range(Simplex_ptr& sptr) const {
- return *sptr;
+Simplex Fake_simplex_tree::simplex_vertex_range(const Simplex& s) const {
+ return s;
}
-std::unordered_set<Simplex_ptr> Fake_simplex_tree::filtration_simplex_range() const{
- std::vector<Simplex_ptr> m = max_simplices();
- std::cout << m.size()<< std::endl;
- std::cout << m.size()<< std::endl;
-
- std::cout << m.size()<< std::endl;
-
- std::unordered_set<Simplex_ptr> seen;
+std::vector<Simplex> Fake_simplex_tree::filtration_simplex_range() const{
+ std::vector<Simplex> m = max_simplices();
+ std::vector<Simplex> seen1;
+ Simplex_ptr_set seen2;
while(m.begin()!=m.end()){
- Simplex_ptr& sptr = m.back();
+ Simplex s(m.back());
m.pop_back();
- if(seen.find(sptr)!=seen.end()){
- seen.emplace(sptr);
- for(Simplex& sigma : facets(*sptr))
- m.emplace_back(get_key(sigma));
+ if(seen2.find(get_key(s))==seen2.end()){
+ seen1.emplace_back(s);
+ seen2.emplace(get_key(s));
+ if(s.size()>0)
+ for(Simplex& sigma : facets(s))
+ m.emplace_back(sigma);
}
}
- return seen;
+ return seen1;
}
-std::unordered_set<Simplex_ptr> Fake_simplex_tree::skeleton_simplex_range(int d) const{
- std::unordered_set<Simplex_ptr> simplices;
- for(auto sptr: filtration_simplex_range())
- if(sptr->size()<=d)
- simplices.emplace(sptr);
+std::vector<Simplex> Fake_simplex_tree::skeleton_simplex_range(int d) const{
+ std::vector<Simplex> simplices;
+ for(auto s: filtration_simplex_range())
+ if(s.size()<=d)
+ simplices.emplace_back(s);
return simplices;
}
-std::vector<Simplex_ptr> Fake_simplex_tree::max_simplices() const{
- std::vector<Simplex_ptr> s;
+std::vector<Simplex> Fake_simplex_tree::max_simplices() const{
+ std::vector<Simplex> s;
for(auto kv : filtrations)
- s.emplace_back(kv.first);
+ s.emplace_back(*(kv.first));
return s;
}
@@ -190,28 +196,6 @@ std::size_t Fake_simplex_tree::dimension(Simplex_ptr& sptr) const{
return sptr->size();
}
-
-void Fake_simplex_tree::assign_filtration(Simplex_ptr& f_simplex, Filtration_value alpha_complex_filtration){
- filtrations.emplace(f_simplex,alpha_complex_filtration);
-}
-
-void Fake_simplex_tree::make_filtration_non_decreasing(){
- for(auto yt = filtrations.begin(); yt != filtrations.end(); ++yt)
- for (auto it = toplex_maps.begin(); it != toplex_maps.end(); ++it){
- if(it->first == yt -> second)
- break;
- if(it->second.membership(*(yt->first)))
- for(const Simplex_ptr& sptr : it->second.maximal_cofaces(*(yt->first))){
- it->second.erase_maximal(sptr);
- toplex_maps.at(yt->second).insert_simplex(*sptr);
- filtrations.emplace(sptr,yt->second);
- }
- }
-
-}
-
-
-
} //namespace Gudhi
#endif /* FAKE_SIMPLEX_TREE_H */
diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h
index 4b626f11..6d89c062 100644
--- a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h
+++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h
@@ -8,11 +8,11 @@
namespace Gudhi {
-typedef double Filtration_value;
-
class Filtered_toplex_map {
public:
+ typedef double Filtration_value;
+
template <typename Input_vertex_range>
void insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = filtration_upper_bound);
@@ -21,7 +21,7 @@ public:
protected:
std::unordered_map<Filtration_value, Toplex_map> toplex_maps;
- std::unordered_map<Simplex_ptr, Filtration_value> filtrations;
+ std::unordered_map<Simplex_ptr, Filtration_value, Sptr_hash, Sptr_equal> filtrations;
};
@@ -33,7 +33,7 @@ void Filtered_toplex_map::insert_simplex_and_subfaces(const Input_vertex_range &
}
template <typename Input_vertex_range>
-Filtration_value Filtered_toplex_map::filtration(const Input_vertex_range &vertex_range) const{
+Filtered_toplex_map::Filtration_value Filtered_toplex_map::filtration(const Input_vertex_range &vertex_range) const{
for(auto kv : toplex_maps)
if(kv.second.membership(vertex_range))
return kv.first;
diff --git a/src/Toplex_map/include/gudhi/Toplex_map.h b/src/Toplex_map/include/gudhi/Toplex_map.h
index 0b6cad37..9de3a6be 100644
--- a/src/Toplex_map/include/gudhi/Toplex_map.h
+++ b/src/Toplex_map/include/gudhi/Toplex_map.h
@@ -5,6 +5,7 @@
#include <unordered_set>
#include <unordered_map>
#include <memory>
+#include <limits>
#define vertex_upper_bound std::numeric_limits<Vertex>::max()
@@ -18,22 +19,22 @@ typedef std::size_t Vertex;
* \ingroup toplex_map */
typedef std::unordered_set<Vertex> Simplex;
+/** The type of the pointers to maximal simplices.
+ * \ingroup toplex_map */
+typedef std::shared_ptr<Simplex> Simplex_ptr;
+
+struct Sptr_hash{ std::size_t operator()(const Simplex_ptr& s) const; };
+struct Sptr_equal{ std::size_t operator()(const Simplex_ptr& a, const Simplex_ptr& b) const; };
+/** The type of the sets of Simplex_ptr.
+ * \ingroup toplex_map */
+typedef std::unordered_set<Simplex_ptr, Sptr_hash, Sptr_equal> Simplex_ptr_set;
+
/** A Toplex_map represents the simplicial complex.
* A "toplex" is a maximal simplex.
* \ingroup toplex_map */
class Toplex_map {
public:
- /** The type of the pointers to maximal simplices.
- * \ingroup toplex_map */
- typedef std::shared_ptr<Simplex> Simplex_ptr;
-
- struct Sptr_hash{ std::size_t operator()(const Simplex_ptr& s) const; };
- struct Sptr_equal{ std::size_t operator()(const Simplex_ptr& a, const Simplex_ptr& b) const; };
- /** The type of the sets of Simplex_ptr.
- * \ingroup toplex_map */
- typedef std::unordered_set<Simplex_ptr, Sptr_hash, Sptr_equal> Simplex_ptr_set;
-
/** \brief Adds the given simplex to the complex.
* Nothing happens if the simplex has a coface in the complex.
* \ingroup toplex_map */
@@ -75,7 +76,6 @@ public:
template <typename Input_vertex_range>
void insert_independent_simplex(const Input_vertex_range &vertex_range);
-
/** \internal Removes a toplex without adding facets after.
* \ingroup toplex_map */
void erase_maximal(const Simplex_ptr& sptr);
@@ -98,12 +98,8 @@ protected:
/** \internal The map from vertices to toplices
* \ingroup toplex_map */
std::unordered_map<Vertex, Simplex_ptr_set> t0;
-
};
-typedef Toplex_map::Simplex_ptr Simplex_ptr;
-typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set;
-
// Pointers are also used as key in the hash sets.
template <typename Input_vertex_range>
Simplex_ptr get_key(const Input_vertex_range &vertex_range);
@@ -261,13 +257,13 @@ Vertex Toplex_map::best_index(const Input_vertex_range &vertex_range) const{
return arg_min;
}
-std::size_t Toplex_map::Sptr_equal::operator()(const Simplex_ptr& s1, const Simplex_ptr& s2) const {
+std::size_t Sptr_equal::operator()(const Simplex_ptr& s1, const 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 Simplex_ptr& s) const {
+std::size_t Sptr_hash::operator()(const Simplex_ptr& s) const {
std::hash<double> h_f;
//double hash works better than int hash
size_t h = 0;
diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt
index cbc53902..0f709409 100644
--- a/src/Witness_complex/example/CMakeLists.txt
+++ b/src/Witness_complex/example/CMakeLists.txt
@@ -14,6 +14,7 @@ install(TARGETS Witness_complex_example_nearest_landmark_table DESTINATION bin)
if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.6.0)
add_executable( Witness_complex_example_off example_witness_complex_off.cpp )
add_executable( Witness_complex_example_strong_off example_strong_witness_complex_off.cpp )
+add_executable( Witness_complex_example_strong_fvecs example_strong_witness_complex_fvecs.cpp )
add_executable ( Witness_complex_example_sphere example_witness_complex_sphere.cpp )
add_executable ( Witness_complex_example_witness_persistence example_witness_complex_persistence.cpp )
@@ -44,6 +45,7 @@ if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.6.0)
install(TARGETS Witness_complex_example_off DESTINATION bin)
install(TARGETS Witness_complex_example_strong_off DESTINATION bin)
+ install(TARGETS Witness_complex_example_strong_fvecs DESTINATION bin)
install(TARGETS Witness_complex_example_sphere DESTINATION bin)
install(TARGETS Witness_complex_example_witness_persistence DESTINATION bin)
install(TARGETS Witness_complex_example_strong_witness_persistence DESTINATION bin)
diff --git a/src/Witness_complex/example/example_strong_witness_complex_off.cpp b/src/Witness_complex/example/example_strong_witness_complex_off.cpp
index 4a232481..6292e248 100644
--- a/src/Witness_complex/example/example_strong_witness_complex_off.cpp
+++ b/src/Witness_complex/example/example_strong_witness_complex_off.cpp
@@ -50,8 +50,8 @@ int main(int argc, char * const argv[]) {
int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]);
double alpha2 = atof(argv[3]);
clock_t start, end;
- //Gudhi::Simplex_tree<> simplex_tree;
- Gudhi::Fake_simplex_tree simplex_tree;
+ Gudhi::Simplex_tree<> simplex_tree;
+ //Gudhi::Fake_simplex_tree simplex_tree;
// Read the point file
Point_vector point_vector, landmarks;