3 files - 3 docs

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2945 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: ce6663f33da653f2ac520b4d0f3684b4776aec94

4 files changed, 98 insertions, 243 deletions

diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h
index 3de962af..8876b56d 100644
--- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h
+++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h
@@ -25,39 +25,78 @@ struct Visitor {
     }
 };
 
+/** Fake_simplex_tree is a wrapper for Filtered_toplex_map which has the interface of the Simplex_tree.
+ * Mostly for retro-compatibility purpose. If you use a function that output non maximal simplices, it will be non efficient.
+ * \ingroup toplex_map   */
 class Fake_simplex_tree : public Filtered_toplex_map {
 
 public:
+    /** Vertex is the type of vertices.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Vertex Vertex;
+
+    /** Simplex is the type of simplices.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Simplex Simplex;
+
+    /** The type of the pointers to maximal simplices.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Simplex_ptr Simplex_ptr;
+
+    /** The type of the sets of Simplex_ptr.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set;
 
+    /** Handle type to a vertex contained in the simplicial complex.
+     * \ingroup toplex_map   */
     typedef Vertex Vertex_handle;
 
+    /**  Handle type to a simplex contained in the simplicial complex.
+     * \ingroup toplex_map   */
     typedef Simplex Simplex_handle;
 
     typedef void Insertion_result_type;
 
-    /** \brief Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` in the simplicial
-     * complex. */
+    /**  Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph`
+     * in the simplicial complex.
+     * \ingroup toplex_map   */
     template<class OneSkeletonGraph>
     void insert_graph(const OneSkeletonGraph& skel_graph);
 
-    /** \brief Do nothing */
+    /**  Do actually nothing.
+     * \ingroup toplex_map   */
     void expansion(int max_dim);
 
-    /** \brief Returns the number of vertices stored i.e. the number of max simplices */
+    /**  Returns the number of vertices stored i.e. the number of max simplices
+     *  \ingroup toplex_map   */
     std::size_t num_vertices() const;
 
+    /**  Returns the dimension of the complex.
+      * \ingroup toplex_map   */
     std::size_t dimension() const;
 
+    /**  Returns the dimension of a given simplex in the complex.
+      * \ingroup toplex_map   */
     std::size_t dimension(Simplex_ptr& sptr) const;
 
+    /**  Returns the number of simplices stored i.e. the number of maximal simplices.
+      * \ingroup toplex_map   */
     std::size_t num_simplices() const;
 
+    /**  Returns a range over the vertices of a simplex.
+      * \ingroup toplex_map   */
     Simplex simplex_vertex_range(const Simplex& s) const;
 
+    /**  Returns a set of all maximal (critical if there is filtration values) simplices.
+      * \ingroup toplex_map   */
     std::vector<Simplex> max_simplices() const;
 
+    /** Returns all the simplices, of max dimension d if a parameter d is given.
+      * \ingroup toplex_map   */
     std::vector<Simplex> filtration_simplex_range(int d=std::numeric_limits<int>::max()) const;
 
+    /** Returns all the simplices of max dimension d
+      * \ingroup toplex_map   */
     std::vector<Simplex> skeleton_simplex_range(int d) const;
 
 
@@ -73,6 +112,12 @@ protected:
 template<class OneSkeletonGraph>
 void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){
     toplex_maps.emplace(nan(""),Toplex_map());
+    using vertex_iterator = typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator;
+    vertex_iterator vi, vi_end;
+    for (std::tie(vi, vi_end) = boost::vertices(skel_graph); vi != vi_end; ++vi) {
+        Simplex s; s.insert(*vi);
+        insert_simplex_and_subfaces(s);
+    }
     bron_kerbosch_all_cliques(skel_graph, Visitor(&(this->toplex_maps.at(nan("")))));
 }
 
diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h
index a0c24304..28814d15 100644
--- a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h
+++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h
@@ -7,17 +7,45 @@
 
 namespace Gudhi {
 
+/** A Filtered_toplex_map represents the simplicial complex with a filtration.
+ * A "toplex" is a critical simplex.
+ * \ingroup toplex_map   */
 class Filtered_toplex_map {
 
 public:
+    /** Vertex is the type of vertices.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Vertex Vertex;
+
+    /** Simplex is the type of simplices.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Simplex Simplex;
+
+    /** The type of the pointers to maximal simplices.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Simplex_ptr Simplex_ptr;
+
+    /** The type of the sets of Simplex_ptr.
+     * \ingroup toplex_map   */
+    typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set;
+
+    /** The type of the filtration values.
+     * \ingroup toplex_map   */
     typedef double Filtration_value;
 
+    /** Add a simplex and its subfaces with the given filtration value
+     * in the Filtered_toplex_map.
+     * \ingroup toplex_map   */
     template <typename Input_vertex_range>
     std::pair<Simplex, bool> insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = nan(""));
 
+    /** Gives the filtration of the input simplex.
+     * \ingroup toplex_map   */
     template <typename Input_vertex_range>
     Filtration_value filtration(const Input_vertex_range &vertex_range) const;
 
+    /** Is the input simplex member of the complex ?
+     * \ingroup toplex_map   */
     template <typename Input_vertex_range>
     bool membership(const Input_vertex_range &vertex_range) const;
 
diff --git a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h
deleted file mode 100644
index 3ffe8214..00000000
--- a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h
+++ /dev/null
@@ -1,218 +0,0 @@
-#ifndef LAZY_TOPLEX_MAP_H
-#define LAZY_TOPLEX_MAP_H
-
-#include <gudhi/Toplex_map.h>
-#include <boost/heap/fibonacci_heap.hpp>
-
-namespace Gudhi {
-
-class Lazy_Toplex_map {
-
-public:
-    template <typename Input_vertex_range>
-    void insert_max_simplex(const Input_vertex_range &vertex_range);
-    template <typename Input_vertex_range>
-    bool insert_simplex(const Input_vertex_range &vertex_range);
-    template <typename Input_vertex_range>
-    void remove_simplex(const Input_vertex_range &vertex_range);
-
-    template <typename Input_vertex_range>
-    bool membership(const Input_vertex_range &vertex_range);
-    template <typename Input_vertex_range>
-    bool all_facets_inside(const Input_vertex_range &vertex_range);
-
-    Vertex contraction(const Vertex x, const Vertex y);
-
-    std::size_t num_simplices() const;
-
-private:
-    template <typename Input_vertex_range>
-    void erase_max(const Input_vertex_range &vertex_range);
-    template <typename Input_vertex_range>
-    Vertex best_index(const Input_vertex_range &vertex_range);
-    void clean(const Vertex v);
-
-    std::unordered_map<Vertex, Simplex_ptr_set> t0;
-    bool empty_toplex; // Is the empty simplex a toplex ?
-
-    typedef boost::heap::fibonacci_heap<std::pair<std::size_t,Vertex>> PriorityQueue;
-    PriorityQueue cleaning_priority;
-    std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles;
-
-    std::unordered_map<Vertex, std::size_t> gamma0_lbounds;
-    std::size_t get_gamma0_lbound(const Vertex v) const;
-
-    std::size_t size_lbound = 0;
-    std::size_t size = 0;
-
-    const double alpha = 2; //time
-    const double betta = 3; //memory
-};
-
-template <typename Input_vertex_range>
-void Lazy_Toplex_map::insert_max_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));
-    }
-    if(inserted)
-        size++;
-    if(size > size_lbound * 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_max_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;
-}
-
-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;
-}
-
-/* Returns the remaining vertex */
-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;
-    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>
-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;
-}
-
-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;
-    int max_dim = 0;
-    for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){
-        if(sptr->size() > max_dim){
-            for(int 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);
-    }
-    for(int 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);
-}
-
-std::size_t Lazy_Toplex_map::num_simplices() const{
-    return size;
-}
-
-} //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 9de3a6be..b433f3de 100644
--- a/src/Toplex_map/include/gudhi/Toplex_map.h
+++ b/src/Toplex_map/include/gudhi/Toplex_map.h
@@ -11,30 +11,31 @@
 
 namespace Gudhi {
 
-/** Vertex is the type of vertices.
- * \ingroup toplex_map   */
-typedef std::size_t Vertex;
-
-/** Simplex is the type of simplices.
- * \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:
+
+    /** Vertex is the type of vertices.
+     * \ingroup toplex_map   */
+    typedef std::size_t Vertex;
+
+    /** Simplex is the type of simplices.
+     * \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;
+
     /** \brief Adds the given simplex to the complex.
      * Nothing happens if the simplex has a coface in the complex.
      * \ingroup toplex_map   */
@@ -58,7 +59,7 @@ public:
     bool maximality(const Input_vertex_range &vertex_range) const;
 
     /** Gives a set of pointers to the maximal cofaces of a simplex.
-     * Gives the toplices if given the empty simplex.
+     * Gives all the toplices if given the empty simplex.
      * Gives not more than max_number maximal cofaces if max_number is strictly positive.
      * \ingroup toplex_map   */
     template <typename Input_vertex_range>
@@ -85,8 +86,7 @@ public:
     void remove_vertex(const Vertex x);
 
     /** \brief Number of maximal simplices.
-         * /!\ Not efficient !
-         * \ingroup toplex_map   */
+      * \ingroup toplex_map   */
     std::size_t num_simplices() const;
 
 protected: