From 2acc203de9dcdb55983db29a903ef0ff16e0a597 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 10 Apr 2020 09:02:52 +0200 Subject: Conventions for variables and type names --- .../include/gudhi/Flag_complex_sparse_matrix.h | 257 ++++++++++----------- 1 file changed, 121 insertions(+), 136 deletions(-) (limited to 'src/Collapse/include') diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index 0d5f37a4..7e3e5a62 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -44,19 +44,15 @@ typedef std::size_t Vertex; using Edge = std::pair; // 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 EdgeFilt = std::pair; +using Filtered_edge = std::pair; -using MapVertexToIndex = std::unordered_map; +using Map_vertex_to_index = std::unordered_map; -using sparseRowMatrix = Eigen::SparseMatrix; +using Sparse_row_matrix = Eigen::SparseMatrix; using doubleVector = std::vector; -using boolVector = std::vector; - -using EdgeFiltVector = std::vector; using Filtered_sorted_edge_list = std::vector>; -using u_edge_to_idx_map = std::unordered_map>; //! Class SparseMsMatrix /*! @@ -65,37 +61,34 @@ using u_edge_to_idx_map = std::unordered_map row_to_vertex; + std::unordered_map row_to_vertex_; // Vertices stored as an unordered_set - std::unordered_set vertices; + std::unordered_set vertices_; // Unordered set of removed edges. (to enforce removal from the matrix) - std::unordered_set> u_set_removed_redges; + std::unordered_set> u_set_removed_redges_; // Unordered set of dominated edges. (to inforce removal from the matrix) - std::unordered_set> u_set_dominated_redges; + std::unordered_set> u_set_dominated_redges_; // Map from egde to its index - u_edge_to_idx_map edge_to_index_map; + std::unordered_map> edge_to_index_map_; // Boolean vector to indicate if the index is critical or not. - boolVector critical_edge_indicator; // critical indicator + std::vector critical_edge_indicator_; // critical indicator // Boolean vector to indicate if the index is critical or not. - boolVector dominated_edge_indicator; // domination indicator + std::vector dominated_edge_indicator_; // domination indicator - //! Stores the Map between verticesrow_to_vertex and row indices row_to_vertex -> row-index. + //! Stores the Map between vertices_row_to_vertex_ and row indices row_to_vertex_ -> row-index. /*! - \code - MapVertexToIndex = std::unordered_map - \endcode - So, if the original simplex tree had vertices 0,1,4,5
- row_to_vertex would store :
+ So, if the original simplex tree had vertices_ 0,1,4,5
+ row_to_vertex_ would store :
\verbatim Values = | 0 | 1 | 4 | 5 | Indices = 0 1 2 3 \endverbatim - And vertex_to_row would be a map like the following :
+ And vertex_to_row_ would be a map like the following :
\verbatim 0 -> 0 1 -> 1 @@ -103,71 +96,68 @@ class Flag_complex_sparse_matrix { 5 -> 3 \endverbatim */ - MapVertexToIndex vertex_to_row; + std::unordered_map vertex_to_row_; //! Stores the Sparse matrix of double values representing the Original Simplicial Complex. /*! \code - sparseRowMatrix = Eigen::SparseMatrix ; + Sparse_row_matrix = Eigen::SparseMatrix ; \endcode ; */ - sparseRowMatrix sparse_row_adjacency_matrix; // This is row-major version of the same sparse-matrix, to facilitate easy access + Sparse_row_matrix sparse_row_adjacency_matrix_; // This is row-major version of the same sparse-matrix, to facilitate easy access // to elements when traversing the matrix row-wise. //! Stores true for dominated rows and false for undominated rows. /*! Initialised to a vector of length equal to the value of the variable rows with all false values. - Subsequent removal of dominated vertices is reflected by concerned entries changing to true in this vector. + Subsequent removal of dominated vertices_ is reflected by concerned entries changing to true in this vector. */ - boolVector domination_indicator; //(domination indicator) + std::vector domination_indicator_; //(domination indicator) // Vector of filtered edges, for edge-collapse, the indices of the edges are the row-indices. - EdgeFiltVector f_edge_vector; + std::vector f_edge_vector_; // Stores the indices from the sorted filtered edge vector. // std::set recurCriticalCoreIndcs; - //! 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). */ std::size_t rows; - bool edgeCollapsed; - // Edge e is the actual edge (u,v). Not the row ids in the matrixs bool check_edge_domination(Edge e) { auto u = std::get<0>(e); auto v = std::get<1>(e); - auto rw_u = vertex_to_row[u]; - auto rw_v = vertex_to_row[v]; + auto rw_u = vertex_to_row_[u]; + auto rw_v = vertex_to_row_[v]; auto rw_e = std::make_pair(rw_u, rw_v); #ifdef DEBUG_TRACES std::cout << "The edge {" << u << ", " << v << "} is going for domination check." << std::endl; #endif // DEBUG_TRACES - auto commonNeighbours = closed_common_neighbours_row_index(rw_e); + auto common_neighbours = closed_common_neighbours_row_index(rw_e); #ifdef DEBUG_TRACES std::cout << "And its common neighbours are." << std::endl; - for (doubleVector::iterator it = commonNeighbours.begin(); it!=commonNeighbours.end(); it++) { - std::cout << row_to_vertex[*it] << ", " ; + for (auto neighbour : common_neighbours) { + std::cout << row_to_vertex_[neighbour] << ", " ; } std::cout<< std::endl; #endif // DEBUG_TRACES - if (commonNeighbours.size() > 2) { - if (commonNeighbours.size() == 3) + if (common_neighbours.size() > 2) { + if (common_neighbours.size() == 3) return true; else - for (doubleVector::iterator it = commonNeighbours.begin(); it != commonNeighbours.end(); it++) { - auto rw_c = *it; // Typecasting + for (auto rw_c : common_neighbours) { if (rw_c != rw_u and rw_c != rw_v) { auto neighbours_c = closed_neighbours_row_index(rw_c); // If neighbours_c contains the common neighbours. - if (std::includes(neighbours_c.begin(), neighbours_c.end(), commonNeighbours.begin(), - commonNeighbours.end())) + if (std::includes(neighbours_c.begin(), neighbours_c.end(), common_neighbours.begin(), + common_neighbours.end())) return true; } } @@ -178,34 +168,33 @@ class Flag_complex_sparse_matrix { // The edge should be sorted by the indices and indices are original bool check_domination_indicator(Edge e) { - return dominated_edge_indicator[edge_to_index_map[e]]; + return dominated_edge_indicator_[edge_to_index_map_[e]]; } std::set three_clique_indices(std::size_t crit) { std::set edge_indices; - Edge e = std::get<0>(f_edge_vector[crit]); + Edge e = std::get<0>(f_edge_vector_[crit]); Vertex u = std::get<0>(e); Vertex v = std::get<1>(e); #ifdef DEBUG_TRACES std::cout << "The current critical edge to re-check criticality with filt value is : f {" << u << "," << v - << "} = " << std::get<1>(f_edge_vector[crit]) << std::endl; + << "} = " << std::get<1>(f_edge_vector_[crit]) << std::endl; #endif // DEBUG_TRACES - auto rw_u = vertex_to_row[u]; - auto rw_v = vertex_to_row[v]; + auto rw_u = vertex_to_row_[u]; + auto rw_v = vertex_to_row_[v]; auto rw_critical_edge = std::make_pair(rw_u, rw_v); - doubleVector commonNeighbours = closed_common_neighbours_row_index(rw_critical_edge); + doubleVector common_neighbours = closed_common_neighbours_row_index(rw_critical_edge); - if (commonNeighbours.size() > 2) { - for (doubleVector::iterator it = commonNeighbours.begin(); it != commonNeighbours.end(); it++) { - auto rw_c = *it; + if (common_neighbours.size() > 2) { + for (auto rw_c : common_neighbours) { if (rw_c != rw_u and rw_c != rw_v) { - auto e_with_new_nbhr_v = std::minmax(u, row_to_vertex[rw_c]); - auto e_with_new_nbhr_u = std::minmax(v, row_to_vertex[rw_c]); - edge_indices.emplace(edge_to_index_map[e_with_new_nbhr_v]); - edge_indices.emplace(edge_to_index_map[e_with_new_nbhr_u]); + auto e_with_new_nbhr_v = std::minmax(u, row_to_vertex_[rw_c]); + auto e_with_new_nbhr_u = std::minmax(v, row_to_vertex_[rw_c]); + edge_indices.emplace(edge_to_index_map_[e_with_new_nbhr_v]); + edge_indices.emplace(edge_to_index_map_[e_with_new_nbhr_u]); } } } @@ -221,19 +210,19 @@ class Flag_complex_sparse_matrix { std::set effectedIndcs = three_clique_indices(indx); if (effectedIndcs.size() > 0) { for (auto idx = indx - 1; idx > 0; idx--) { - Edge e = std::get<0>(f_edge_vector[idx]); + Edge e = std::get<0>(f_edge_vector_[idx]); Vertex u = std::get<0>(e); Vertex v = std::get<1>(e); // If idx is not critical so it should be proceses, otherwise it stays in the graph // prev // code : recurCriticalCoreIndcs.find(idx) == recurCriticalCoreIndcs.end() - if (not critical_edge_indicator[idx]) { + if (not critical_edge_indicator_[idx]) { // If idx is affected if (effectedIndcs.find(idx) != effectedIndcs.end()) { if (not check_edge_domination(e)) { #ifdef DEBUG_TRACES std::cout << "The curent index became critical " << idx << std::endl; #endif // DEBUG_TRACES - critical_edge_indicator[idx] = true; + critical_edge_indicator_[idx] = true; filtered_edge_insert({u, v}, filt); std::set inner_effected_indcs = three_clique_indices(idx); for (auto inr_idx = inner_effected_indcs.rbegin(); inr_idx != inner_effected_indcs.rend(); inr_idx++) { @@ -245,15 +234,15 @@ class Flag_complex_sparse_matrix { std::get<1>(e) << "}; " << filt << std::endl; #endif // DEBUG_TRACES } else - u_set_dominated_redges.emplace(std::minmax(vertex_to_row[u], vertex_to_row[v])); + u_set_dominated_redges_.emplace(std::minmax(vertex_to_row_[u], vertex_to_row_[v])); } else // Idx is not affected hence dominated. - u_set_dominated_redges.emplace(std::minmax(vertex_to_row[u], vertex_to_row[v])); + u_set_dominated_redges_.emplace(std::minmax(vertex_to_row_[u], vertex_to_row_[v])); } } } effectedIndcs.clear(); - u_set_dominated_redges.clear(); + u_set_dominated_redges_.clear(); } // Returns list of non-zero columns of the particular indx. @@ -263,19 +252,19 @@ class Flag_complex_sparse_matrix { Vertex u = indx; Vertex v; #ifdef DEBUG_TRACES - std::cout << "The neighbours of the vertex: " << row_to_vertex[u] << " are. " << std::endl; + std::cout << "The neighbours of the vertex: " << row_to_vertex_[u] << " are. " << std::endl; #endif // DEBUG_TRACES - if (not domination_indicator[indx]) { + if (not domination_indicator_[indx]) { // Iterate over the non-zero columns - for (sparseRowMatrix::InnerIterator it(sparse_row_adjacency_matrix, indx); it; ++it) { + for (Sparse_row_matrix::InnerIterator it(sparse_row_adjacency_matrix_, indx); it; ++it) { v = it.index(); // If the vertex v is not dominated and the edge {u,v} is still in the matrix - if (not domination_indicator[v] and u_set_removed_redges.find(std::minmax(u, v)) == u_set_removed_redges.end() and - u_set_dominated_redges.find(std::minmax(u, v)) == u_set_dominated_redges.end()) { + if (not domination_indicator_[v] and u_set_removed_redges_.find(std::minmax(u, v)) == u_set_removed_redges_.end() and + u_set_dominated_redges_.find(std::minmax(u, v)) == u_set_dominated_redges_.end()) { // inner index, here it is equal to it.columns() non_zero_indices.push_back(it.index()); #ifdef DEBUG_TRACES - std::cout << row_to_vertex[it.index()] << ", " ; + std::cout << row_to_vertex_[it.index()] << ", " ; #endif // DEBUG_TRACES } } @@ -301,35 +290,70 @@ class Flag_complex_sparse_matrix { return common; } + + void insert_vertex(const Vertex& vertex, double 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. + sparse_row_adjacency_matrix_.insert(rows, rows) = filt_val; + domination_indicator_.push_back(false); + vertex_to_row_.insert(std::make_pair(vertex, rows)); + row_to_vertex_.insert(std::make_pair(rows, vertex)); + rows++; + } + } + + void insert_new_edges(const Vertex& u, const Vertex& v, double filt_val) + { + // The edge must not be added before, it should be a new edge. + insert_vertex(u, filt_val); + if (u != v) { + insert_vertex(v, filt_val); +#ifdef DEBUG_TRACES + std::cout << "Insertion of the edge begins " << u <<", " << v << std::endl; +#endif // DEBUG_TRACES + + auto rw_u = vertex_to_row_.find(u); + auto rw_v = vertex_to_row_.find(v); +#ifdef DEBUG_TRACES + std::cout << "Inserting the edge " << u <<", " << v << std::endl; +#endif // DEBUG_TRACES + sparse_row_adjacency_matrix_.insert(rw_u->second, rw_v->second) = filt_val; + sparse_row_adjacency_matrix_.insert(rw_v->second, rw_u->second) = filt_val; + } +#ifdef DEBUG_TRACES + else { + std::cout << "Already a member simplex, skipping..." << std::endl; + } +#endif // DEBUG_TRACES + } public: //! Main Constructor /*! Argument is an instance of Filtered_sorted_edge_list.
This is THE function that initialises all data members to appropriate values.
- row_to_vertex, vertex_to_row, rows, cols, sparse_row_adjacency_matrix are initialised here. - domination_indicator are initialised by init() function which is + row_to_vertex_, vertex_to_row_, rows, cols, sparse_row_adjacency_matrix_ are initialised here. + domination_indicator_ are initialised by init() function which is called at the begining of this.
*/ Flag_complex_sparse_matrix(const Filtered_sorted_edge_list& edge_t) - : rows(0), - edgeCollapsed(false) { + : rows(0) { for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { Vertex u = std::get<1>(edge_t[bgn_idx]); Vertex 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); + f_edge_vector_.push_back({{u, v}, std::get<0>(edge_t[bgn_idx])}); + vertices_.emplace(u); + vertices_.emplace(v); } } template Flag_complex_sparse_matrix(const OneSkeletonGraph& one_skeleton_graph) - : rows(0), - edgeCollapsed(false) { - // Insert all vertices - for (auto v_it = boost::vertices(one_skeleton_graph); v_it.first != v_it.second; ++v_it.first) { - vertices.emplace(*(v_it.first)); + : rows(0) { + // Insert all vertices_ + for (auto v_it = boost::vertices_(one_skeleton_graph); v_it.first != v_it.second; ++v_it.first) { + vertices_.emplace(*(v_it.first)); } // Insert all edges for (auto edge_it = boost::edges(one_skeleton_graph); @@ -337,18 +361,18 @@ class Flag_complex_sparse_matrix { auto edge = *(edge_it.first); Vertex u = source(edge, one_skeleton_graph); Vertex v = target(edge, one_skeleton_graph); - f_edge_vector.push_back({{u, v}, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge)}); + f_edge_vector_.push_back({{u, v}, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge)}); } // Sort edges - auto sort_by_filtration = [](const EdgeFilt& edge_a, const EdgeFilt& edge_b) -> bool + auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool { return (get<1>(edge_a) < get<1>(edge_b)); }; #ifdef GUDHI_USE_TBB - tbb::parallel_sort(f_edge_vector.begin(), f_edge_vector.end(), sort_by_filtration); + tbb::parallel_sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); #else - std::stable_sort(f_edge_vector.begin(), f_edge_vector.end(), sort_by_filtration); + std::stable_sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); #endif } @@ -357,15 +381,15 @@ class Flag_complex_sparse_matrix { void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { std::size_t endIdx = 0; - u_set_removed_redges.clear(); - u_set_dominated_redges.clear(); - critical_edge_indicator.clear(); + u_set_removed_redges_.clear(); + u_set_dominated_redges_.clear(); + critical_edge_indicator_.clear(); - // Initializing sparse_row_adjacency_matrix, This is a row-major sparse matrix. - sparse_row_adjacency_matrix = sparseRowMatrix(vertices.size(), vertices.size()); + // Initializing sparse_row_adjacency_matrix_, This is a row-major sparse matrix. + sparse_row_adjacency_matrix_ = Sparse_row_matrix(vertices_.size(), vertices_.size()); - while (endIdx < f_edge_vector.size()) { - EdgeFilt fec = f_edge_vector[endIdx]; + while (endIdx < f_edge_vector_.size()) { + Filtered_edge fec = f_edge_vector_[endIdx]; Edge e = std::get<0>(fec); Vertex u = std::get<0>(e); Vertex v = std::get<1>(e); @@ -374,62 +398,23 @@ class Flag_complex_sparse_matrix { // Inserts the edge in the sparse matrix to update the graph (G_i) insert_new_edges(u, v, filt); - edge_to_index_map.emplace(std::minmax(u, v), endIdx); - critical_edge_indicator.push_back(false); - dominated_edge_indicator.push_back(false); + edge_to_index_map_.emplace(std::minmax(u, v), endIdx); + critical_edge_indicator_.push_back(false); + dominated_edge_indicator_.push_back(false); if (not check_edge_domination(e)) { - critical_edge_indicator[endIdx] = true; - dominated_edge_indicator[endIdx] = false; + critical_edge_indicator_[endIdx] = true; + dominated_edge_indicator_[endIdx] = false; filtered_edge_insert({u, v}, filt); if (endIdx > 1) set_edge_critical(endIdx, filt, filtered_edge_insert); } else - dominated_edge_indicator[endIdx] = true; + dominated_edge_indicator_[endIdx] = true; endIdx++; } - - edgeCollapsed = true; - } - - void insert_vertex(const Vertex& vertex, double 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. - sparse_row_adjacency_matrix.insert(rows, rows) = filt_val; - domination_indicator.push_back(false); - vertex_to_row.insert(std::make_pair(vertex, rows)); - row_to_vertex.insert(std::make_pair(rows, vertex)); - rows++; - } - } - - void insert_new_edges(const Vertex& u, const Vertex& v, double filt_val) - { - // The edge must not be added before, it should be a new edge. - insert_vertex(u, filt_val); - if (u != v) { - insert_vertex(v, filt_val); -#ifdef DEBUG_TRACES - std::cout << "Insertion of the edge begins " << u <<", " << v << std::endl; -#endif // DEBUG_TRACES - - auto rw_u = vertex_to_row.find(u); - auto rw_v = vertex_to_row.find(v); -#ifdef DEBUG_TRACES - std::cout << "Inserting the edge " << u <<", " << v << std::endl; -#endif // DEBUG_TRACES - sparse_row_adjacency_matrix.insert(rw_u->second, rw_v->second) = filt_val; - sparse_row_adjacency_matrix.insert(rw_v->second, rw_u->second) = filt_val; - } -#ifdef DEBUG_TRACES - else { - std::cout << "Already a member simplex, skipping..." << std::endl; - } -#endif // DEBUG_TRACES } - std::size_t num_vertices() const { return vertices.size(); } + std::size_t num_vertices() const { return vertices_.size(); } }; -- cgit v1.2.3