From e6992894cf4e9b76acee98e2c1ad840a3ebd7274 Mon Sep 17 00:00:00 2001 From: skachano Date: Tue, 4 Oct 2016 18:07:42 +0000 Subject: Fixed a major bug in the Active_witness_iterator git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/relaxed-witness@1633 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d4f474b44835b11e65a152f9d3fe87cc32b527f5 --- .../include/gudhi/Active_witness/Active_witness.h | 14 ++++---- .../gudhi/Active_witness/Active_witness_iterator.h | 12 +++++-- .../include/gudhi/Witness_complex.h | 41 +++++++++++++++++----- 3 files changed, 49 insertions(+), 18 deletions(-) (limited to 'src/Witness_complex/include') diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h index 7b169784..9ae41a69 100644 --- a/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness.h @@ -34,23 +34,26 @@ namespace witness_complex { template< typename Id_distance_pair, typename INS_range > class Active_witness { -public: +public: typedef Active_witness ActiveWitness; typedef typename INS_range::iterator INS_iterator; typedef Active_witness_iterator< ActiveWitness, Id_distance_pair, INS_iterator > iterator; typedef typename std::list Table; - + + Table end_element_table_ = {Id_distance_pair(-1,0)}; + typename Table::iterator end_pointer = end_element_table_.begin(); + Table nearest_landmark_table_; INS_range search_range_; INS_iterator iterator_last_; INS_iterator iterator_end_; Active_witness(INS_range search_range) - : search_range_(search_range), iterator_end_(search_range.end()), iterator_last_(search_range.begin()) + : search_range_(search_range), iterator_last_(search_range.begin()), iterator_end_(search_range.end()) { nearest_landmark_table_.push_back(*iterator_last_); } - + iterator begin() { return iterator(this, nearest_landmark_table_.begin()); @@ -60,9 +63,6 @@ public: { return iterator(this); } - - Table end_element_table_ = {Id_distance_pair(-1,0)}; - typename Table::iterator end_pointer = end_element_table_.begin(); }; } diff --git a/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h index 658405f6..5d4f3d75 100644 --- a/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h +++ b/src/Witness_complex/include/gudhi/Active_witness/Active_witness_iterator.h @@ -64,7 +64,7 @@ public: private : - Id_distance_pair dereference() const + Id_distance_pair& dereference() const { return *lh_; } @@ -76,9 +76,17 @@ private : void increment() { + // if neighbor search is at its end, check if lh_++ is end + if (aw_->iterator_last_ == aw_->iterator_end_) { + if (lh_++ == aw_->nearest_landmark_table_.end()) { + lh_ = aw_->end_pointer; + return; + } + return; + } // if the id of the current landmark is the same as the last one if (lh_->first == aw_->iterator_last_->first) { - // if the next iterator is end, lh_it = nullptr + // if the next iterator is end, lh_it = end pointer if (++(aw_->iterator_last_) == aw_->iterator_end_) { lh_ = aw_->end_pointer; return; diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 158f92ec..e939de34 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -84,9 +84,9 @@ private: typedef FT Filtration_value; - typedef std::size_t Witness_id; - typedef std::size_t Landmark_id; - typedef std::pair Id_distance_pair; + typedef std::ptrdiff_t Witness_id; + typedef std::ptrdiff_t Landmark_id; + typedef std::pair Id_distance_pair; typedef Active_witness ActiveWitness; typedef std::list< ActiveWitness > ActiveWitnessList; typedef std::vector< Landmark_id > typeVectorVertex; @@ -155,7 +155,7 @@ private: } typeVectorVertex vv; ActiveWitnessList active_witnesses;// = new ActiveWitnessList(); - for (auto i = 0; i != nbL; ++i) { + for (unsigned 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++; @@ -166,10 +166,12 @@ private: unsigned k = 1; /* current dimension in iterative construction */ for (auto w: witnesses_) active_witnesses.push_back(ActiveWitness(landmark_tree_.query_incremental_nearest_neighbors(w))); + ActiveWitness aw_copy(active_witnesses.front()); while (!active_witnesses.empty() && k < nbL ) { typename ActiveWitnessList::iterator aw_it = active_witnesses.begin(); while (aw_it != active_witnesses.end()) { std::vector simplex; + //simplex.reserve(k+1); bool ok = add_all_faces_of_dimension(k, max_alpha_square, std::numeric_limits::infinity(), @@ -178,10 +180,13 @@ private: complex, aw_it->end()); if (!ok) - active_witnesses.erase(aw_it++); //First increase the iterator and then erase the previous element + //{aw_it++;} + active_witnesses.erase(aw_it++); //First increase the iterator and then erase the previous element else aw_it++; - } + } + std::cout << "Active witnesses after dim=" << k << " is finished: " << active_witnesses.size() << "\n"; + std::cout << complex << "\n"; k++; } return true; @@ -190,7 +195,6 @@ private: //@} private: - /* \brief Adds recursively all the faces of a certain dimension dim witnessed by the same witness * Iterator is needed to know until how far we can take landmarks to form simplexes * simplex is the prefix of the simplexes to insert @@ -222,12 +226,13 @@ private: sc, end) || will_be_active; } + assert(!simplex.empty()); simplex.pop_back(); // If norelax_dist is infinity, change to first omitted distance if (l_it->second <= norelax_dist2) norelax_dist2 = l_it->second; typename ActiveWitness::iterator next_it = l_it; - will_be_active = add_all_faces_of_dimension(dim-1, + will_be_active = add_all_faces_of_dimension(dim, alpha2, norelax_dist2, ++next_it, @@ -240,12 +245,16 @@ private: simplex.push_back(l_it->first); double filtration_value = 0; // if norelax_dist is infinite, relaxation is 0. + //std::cout << "landmark_id=" << l_it->first << " distance=" << l_it->second << "\n"; + // std::size_t landmark_id = l_it->first; + // double distance = l_it->second; if (l_it->second > norelax_dist2) filtration_value = l_it->second - norelax_dist2; if (all_faces_in(simplex, &filtration_value, sc)) { will_be_active = true; sc.insert_simplex(simplex, filtration_value); } + assert(!simplex.empty()); simplex.pop_back(); // If norelax_dist is infinity, change to first omitted distance if (l_it->second < norelax_dist2) @@ -301,9 +310,23 @@ private: // } // return (fv_it == fvr.end()); // } - + public: + template < typename SimplicialComplexForWitness > + void print_complex(SimplicialComplexForWitness& complex) + { + std::cout << complex << "\n"; + } + + template < typename Container > + void print_container(Container& container) + { + for (auto l: container) + std::cout << l << ", "; + std::cout << "\n"; + } + // /* // * \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 -- cgit v1.2.3