diff options
author | ROUVREAU Vincent <vincent.rouvreau@inria.fr> | 2020-04-12 10:33:38 +0200 |
---|---|---|
committer | ROUVREAU Vincent <vincent.rouvreau@inria.fr> | 2020-04-12 10:33:38 +0200 |
commit | 1ce5d0d19e13a14e8a67442aec7bc40eae68dc8e (patch) | |
tree | 4e4c148cfd7935e8a686a7cafaaaacba2db432b9 /src/Collapse/include/gudhi | |
parent | f000725296c1962155e2ec331a3db6244d7c9f9e (diff) |
Modify interface and utils
Diffstat (limited to 'src/Collapse/include/gudhi')
-rw-r--r-- | src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h | 86 |
1 files changed, 51 insertions, 35 deletions
diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index d472bf15..e90d284d 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -16,6 +16,7 @@ #include <gudhi/graph_simplicial_complex.h> #include <boost/functional/hash.hpp> +#include <boost/graph/adjacency_list.hpp> #include <Eigen/Sparse> @@ -32,6 +33,7 @@ #include <list> #include <algorithm> + namespace Gudhi { namespace collapse { @@ -47,26 +49,28 @@ namespace collapse { * Algorithm. * * \tparam Vertex_handle type must be a signed integer type. It admits a total order <. - * \tparam Filtration_value type for the value of the filtration function. Must be comparable with <. + * \tparam Filtration type for the value of the filtration function. Must be comparable with <. */ -template<typename Vertex_handle, typename Filtration_value> +template<typename Vertex_handle, typename Filtration> class Flag_complex_sparse_matrix { private: using Edge = std::pair<Vertex_handle, Vertex_handle>; // This is an ordered pair, An edge is stored with convention of the first // element being the smaller i.e {2,3} not {3,2}. However this is at the level // of row indices on actual vertex lables - using Filtered_edge = std::pair<Edge, Filtration_value>; + using Filtered_edge = std::pair<Edge, Filtration>; using Row_index = std::size_t; using Map_vertex_to_index = std::unordered_map<Vertex_handle, Row_index>; - using Sparse_row_matrix = Eigen::SparseMatrix<Filtration_value, Eigen::RowMajor>; + using Sparse_row_matrix = Eigen::SparseMatrix<Filtration, Eigen::RowMajor>; using Row_indices_vector = std::vector<Row_index>; public: - using Filtered_sorted_edge_list = std::vector<std::tuple<Filtration_value, Vertex_handle, Vertex_handle>>; + using Filtered_sorted_edge_list = std::vector<std::tuple<Filtration, Vertex_handle, Vertex_handle>>; + using Filtration_value = Filtration; + using Proximity_graph = Gudhi::Proximity_graph<Flag_complex_sparse_matrix>; private: std::unordered_map<Row_index, Vertex_handle> row_to_vertex_; @@ -88,9 +92,9 @@ class Flag_complex_sparse_matrix { // Boolean vector to indicate if the index is critical or not. std::vector<bool> dominated_edge_indicator_; // domination indicator - //! Stores the Map between vertices_<B>row_to_vertex_ and row indices <B>row_to_vertex_ -> row-index</B>. + //! Stores the Map between vertices<B>row_to_vertex_ and row indices <B>row_to_vertex_ -> row-index</B>. /*! - So, if the original simplex tree had vertices_ 0,1,4,5 <br> + So, if the original simplex tree had vertices 0,1,4,5 <br> <B>row_to_vertex_</B> would store : <br> \verbatim Values = | 0 | 1 | 4 | 5 | @@ -106,10 +110,10 @@ class Flag_complex_sparse_matrix { */ std::unordered_map<Vertex_handle, Row_index> vertex_to_row_; - //! Stores the Sparse matrix of Filtration_value values representing the Original Simplicial Complex. + //! Stores the Sparse matrix of Filtration values representing the Original Simplicial Complex. /*! \code - Sparse_row_matrix = Eigen::SparseMatrix<Filtration_value, Eigen::RowMajor> ; + Sparse_row_matrix = Eigen::SparseMatrix<Filtration, Eigen::RowMajor> ; \endcode ; */ @@ -120,7 +124,7 @@ class Flag_complex_sparse_matrix { //! Stores <I>true</I> for dominated rows and <I>false</I> for undominated rows. /*! Initialised to a vector of length equal to the value of the variable <B>rows</B> with all <I>false</I> values. - Subsequent removal of dominated vertices_ is reflected by concerned entries changing to <I>true</I> in this vector. + Subsequent removal of dominated vertices is reflected by concerned entries changing to <I>true</I> in this vector. */ std::vector<bool> domination_indicator_; //(domination indicator) @@ -128,9 +132,9 @@ class Flag_complex_sparse_matrix { std::vector<Filtered_edge> f_edge_vector_; - //! Stores the number of vertices_ in the original Simplicial Complex. + //! Stores the number of vertices in the original Simplicial Complex. /*! - This stores the count of vertices_ (which is also the number of rows in the Matrix). + This stores the count of vertices (which is also the number of rows in the Matrix). */ Row_index rows; @@ -202,7 +206,7 @@ class Flag_complex_sparse_matrix { } template<typename FilteredEdgeInsertion> - void set_edge_critical(Row_index indx, Filtration_value filt, FilteredEdgeInsertion filtered_edge_insert) { + void set_edge_critical(Row_index indx, Filtration filt, FilteredEdgeInsertion filtered_edge_insert) { #ifdef DEBUG_TRACES std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << std::endl; @@ -290,7 +294,7 @@ class Flag_complex_sparse_matrix { return common; } - void insert_vertex(Vertex_handle vertex, Filtration_value filt_val) { + void insert_vertex(Vertex_handle vertex, Filtration filt_val) { auto rw = vertex_to_row_.find(vertex); if (rw == vertex_to_row_.end()) { // Initializing the diagonal element of the adjency matrix corresponding to rw_b. @@ -302,7 +306,7 @@ class Flag_complex_sparse_matrix { } } - void insert_new_edges(Vertex_handle u, Vertex_handle v, Filtration_value filt_val) + void insert_new_edges(Vertex_handle u, Vertex_handle v, Filtration filt_val) { // The edge must not be added before, it should be a new edge. insert_vertex(u, filt_val); @@ -336,19 +340,27 @@ class Flag_complex_sparse_matrix { <B>domination_indicator_</B> are initialised by init() function which is called at the begining of this. <br> */ - Flag_complex_sparse_matrix(const Filtered_sorted_edge_list& edge_t) + template<typename DistanceMatrix> + Flag_complex_sparse_matrix(const DistanceMatrix& distance_matrix) : rows(0) { - for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { - Vertex_handle u = std::get<1>(edge_t[bgn_idx]); - Vertex_handle v = std::get<2>(edge_t[bgn_idx]); - f_edge_vector_.push_back({{u, v}, std::get<0>(edge_t[bgn_idx])}); - vertices_.emplace(u); - vertices_.emplace(v); + Vertex_handle num_vertices = std::distance(std::begin(distance_matrix), std::end(distance_matrix)); + + // This one is not part of the loop + vertices_.emplace(0); + // Only browse the lower part of the distance matrix + for (Vertex_handle line_index = 1; line_index < num_vertices; line_index++) { + for (Vertex_handle row_index = 0; row_index < line_index; row_index++) { +#ifdef DEBUG_TRACES + std::cout << "Insert edge: fn[" << row_index << ", " << line_index << "] = " + << distance_matrix[line_index][row_index] << std::endl; +#endif // DEBUG_TRACES + f_edge_vector_.push_back({{row_index, line_index}, distance_matrix[line_index][row_index]}); + } + vertices_.emplace(line_index); } } - template<typename OneSkeletonGraph> - Flag_complex_sparse_matrix(const OneSkeletonGraph& one_skeleton_graph) + Flag_complex_sparse_matrix(const Proximity_graph& one_skeleton_graph) : rows(0) { // Insert all vertices_ for (auto v_it = boost::vertices(one_skeleton_graph); v_it.first != v_it.second; ++v_it.first) { @@ -362,6 +374,18 @@ class Flag_complex_sparse_matrix { Vertex_handle v = target(edge, one_skeleton_graph); f_edge_vector_.push_back({{u, v}, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge)}); } + } + + // Performs edge collapse in a decreasing sequence of the filtration value. + template<typename FilteredEdgeInsertion> + void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { + Row_index endIdx = 0; + + u_set_removed_redges_.clear(); + u_set_dominated_redges_.clear(); + critical_edge_indicator_.clear(); + + std::cout << "Sort it - " << f_edge_vector_.size() << std::endl; // Sort edges auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool { @@ -373,17 +397,9 @@ class Flag_complex_sparse_matrix { #else std::stable_sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); #endif - } - - // Performs edge collapse in a decreasing sequence of the filtration value. - template<typename FilteredEdgeInsertion> - void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { - Row_index endIdx = 0; - - u_set_removed_redges_.clear(); - u_set_dominated_redges_.clear(); - critical_edge_indicator_.clear(); + std::cout << "Sorted" << std::endl; + std::cout << vertices_.size() << std::endl; // Initializing sparse_row_adjacency_matrix_, This is a row-major sparse matrix. sparse_row_adjacency_matrix_ = Sparse_row_matrix(vertices_.size(), vertices_.size()); @@ -392,7 +408,7 @@ class Flag_complex_sparse_matrix { Edge edge = std::get<0>(fec); Vertex_handle u = std::get<0>(edge); Vertex_handle v = std::get<1>(edge); - Filtration_value filt = std::get<1>(fec); + Filtration filt = std::get<1>(fec); // Inserts the edge in the sparse matrix to update the graph (G_i) insert_new_edges(u, v, filt); |