From fcd06dde50637028a2028adff84e5bb2b2236178 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 18 Jun 2020 07:31:45 +0200 Subject: Code review: rename Flag_complex_sparse_matrix as edge_collapser and filtered_edge_collapse method as process_edges --- .../include/gudhi/Flag_complex_edge_collapser.h | 358 +++++++++++++++++++++ 1 file changed, 358 insertions(+) create mode 100644 src/Collapse/include/gudhi/Flag_complex_edge_collapser.h (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h new file mode 100644 index 00000000..32438c3b --- /dev/null +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -0,0 +1,358 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Siddharth Pritam + * + * Copyright (C) 2020 Inria + * + * Modification(s): + * - 2020/03 Vincent Rouvreau: integration to the gudhi library + * - YYYY/MM Author: Description of the modification + */ + +#ifndef FLAG_COMPLEX_EDGE_COLLAPSER_H_ +#define FLAG_COMPLEX_EDGE_COLLAPSER_H_ + +#include +#include + +#include +#include + +#include + +#ifdef GUDHI_USE_TBB +#include +#endif + +#include +#include // for std::pair +#include +#include +#include +#include +#include // for std::tie +#include // for std::includes +#include // for std::inserter + +namespace Gudhi { + +namespace collapse { + +/** + * \class Flag_complex_edge_collapser + * \brief Flag complex sparse matrix data structure. + * + * \ingroup collapse + * + * \details + * This class stores a Flag complex + * in an Eigen sparse matrix. + * + * \tparam Vertex type must be a signed integer type. It admits a total order <. + * \tparam Filtration type for the value of the filtration function. Must be comparable with <. + */ +template +class Flag_complex_edge_collapser { + public: + /** \brief Re-define Vertex as Vertex_handle type to ease the interface with compute_proximity_graph. */ + using Vertex_handle = Vertex; + /** \brief Re-define Filtration as Filtration_value type to ease the interface with compute_proximity_graph. */ + using Filtration_value = Filtration; + /** \brief 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 Edge = std::pair; + + private: + // internal numbering of vertices and edges + using IVertex = std::size_t; + using Edge_index = std::size_t; + using IEdge = std::pair; + + // The sparse matrix data type + // (Eigen::SparseMatrix has slow insertions) + using Sparse_vector = Eigen::SparseVector; + using Sparse_row_matrix = std::vector; + + // A range of row indices + using IVertex_vector = std::vector; + + public: + /** \brief Filtered_edge is a type to store an edge with its filtration value. */ + using Filtered_edge = std::pair; + /** \brief Proximity_graph is a type that can be used to construct easily a Flag_complex_edge_collapser. */ + using Proximity_graph = Gudhi::Proximity_graph; + + private: + // Map from row index to its vertex handle + std::vector row_to_vertex_; + + // Index of the current edge in the backwards walk. Edges <= current_backward are part of the temporary graph, + // while edges > current_backward are removed unless critical_edge_indicator_. + Edge_index current_backward = -1; + + // Map from IEdge to its index + std::unordered_map> iedge_to_index_map_; + + // Boolean vector to indicate if the edge is critical. + std::vector critical_edge_indicator_; + + // Map from vertex handle to its row index + std::unordered_map vertex_to_row_; + + // Stores the Sparse matrix of Filtration values representing the original graph. + // The matrix rows and columns are indexed by IVertex. + Sparse_row_matrix sparse_row_adjacency_matrix_; + + // The input, a vector of filtered edges. + std::vector f_edge_vector_; + + // Edge e is the actual edge (u,v), with Vertex_handle u and v, not IVertex. + bool edge_is_dominated(const Edge& edge) const + { + Vertex_handle u = std::get<0>(edge); + Vertex_handle v = std::get<1>(edge); + + const IVertex rw_u = vertex_to_row_.at(u); + const IVertex rw_v = vertex_to_row_.at(v); +#ifdef DEBUG_TRACES + std::cout << "The edge {" << u << ", " << v << "} is going for domination check." << std::endl; +#endif // DEBUG_TRACES + auto common_neighbours = open_common_neighbours_row_index(rw_u, rw_v); +#ifdef DEBUG_TRACES + std::cout << "And its common neighbours are." << std::endl; + for (auto neighbour : common_neighbours) { + std::cout << row_to_vertex_[neighbour] << ", " ; + } + std::cout<< std::endl; +#endif // DEBUG_TRACES + if (common_neighbours.size() == 1) + return true; + else + for (auto rw_c : common_neighbours) { + auto neighbours_c = neighbours_row_index(rw_c, true); + // If neighbours_c contains the common neighbours. + if (std::includes(neighbours_c.begin(), neighbours_c.end(), + common_neighbours.begin(), common_neighbours.end())) + return true; + } + return false; + } + + // Returns the edges connecting u and v (extremities of crit) to their common neighbors (not themselves) + std::set three_clique_indices(Edge_index crit) { + std::set edge_indices; + + Edge edge = std::get<0>(f_edge_vector_[crit]); + Vertex_handle u = std::get<0>(edge); + Vertex_handle v = std::get<1>(edge); + +#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; +#endif // DEBUG_TRACES + auto rw_u = vertex_to_row_[u]; + auto rw_v = vertex_to_row_[v]; + + IVertex_vector common_neighbours = open_common_neighbours_row_index(rw_u, rw_v); + + for (auto rw_c : common_neighbours) { + IEdge e_with_new_nbhr_v = std::minmax(rw_u, rw_c); + IEdge e_with_new_nbhr_u = std::minmax(rw_v, rw_c); + edge_indices.emplace(iedge_to_index_map_[e_with_new_nbhr_v]); + edge_indices.emplace(iedge_to_index_map_[e_with_new_nbhr_u]); + } + return edge_indices; + } + + // Detect and set all edges that are becoming critical + template + void set_edge_critical(Edge_index indx, Filtration_value filt, FilteredEdgeOutput filtered_edge_output) { +#ifdef DEBUG_TRACES + std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << + std::endl; +#endif // DEBUG_TRACES + std::set effected_indices = three_clique_indices(indx); + // Cannot use boost::adaptors::reverse in such dynamic cases apparently + for (auto it = effected_indices.rbegin(); it != effected_indices.rend(); ++it) { + current_backward = *it; + Edge edge = std::get<0>(f_edge_vector_[current_backward]); + Vertex_handle u = std::get<0>(edge); + Vertex_handle v = std::get<1>(edge); + // If current_backward is not critical so it should be processed, otherwise it stays in the graph + if (!critical_edge_indicator_[current_backward]) { + if (!edge_is_dominated(edge)) { +#ifdef DEBUG_TRACES + std::cout << "The curent index became critical " << current_backward << std::endl; +#endif // DEBUG_TRACES + critical_edge_indicator_[current_backward] = true; + filtered_edge_output({u, v}, filt); + std::set inner_effected_indcs = three_clique_indices(current_backward); + for (auto inr_idx : inner_effected_indcs) { + if(inr_idx < current_backward) // && !critical_edge_indicator_[inr_idx] + effected_indices.emplace(inr_idx); + } +#ifdef DEBUG_TRACES + std::cout << "The following edge is critical with filt value: {" << u << "," << v << "}; " + << filt << std::endl; +#endif // DEBUG_TRACES + } + } + } + // Clear the implicit "removed from graph" data structure + current_backward = -1; + } + + // Returns list of neighbors of a particular vertex. + IVertex_vector neighbours_row_index(IVertex rw_u, bool closed) const + { + IVertex_vector neighbors; + neighbors.reserve(sparse_row_adjacency_matrix_[rw_u].nonZeros()); // too much, but who cares +#ifdef DEBUG_TRACES + std::cout << "The neighbours of the vertex: " << row_to_vertex_[rw_u] << " are. " << std::endl; +#endif // DEBUG_TRACES + // Iterate over the neighbors + for (typename Sparse_vector::InnerIterator it(sparse_row_adjacency_matrix_[rw_u]); it; ++it) { + IVertex rw_v = it.index(); + if (!closed && rw_u == rw_v) continue; + Edge_index ei; + // If the vertex v is not dominated and the edge {u,v} is still in the matrix + if ((closed && rw_u == rw_v) || + (ei = it.value()) <= current_backward || + critical_edge_indicator_[ei]) { + neighbors.push_back(rw_v); +#ifdef DEBUG_TRACES + std::cout << row_to_vertex_[rw_v] << ", " ; +#endif // DEBUG_TRACES + } + } +#ifdef DEBUG_TRACES + std::cout << std::endl; +#endif // DEBUG_TRACES + return neighbors; + } + + // Returns the list of open neighbours of the edge :{u,v}. + IVertex_vector open_common_neighbours_row_index(IVertex rw_u, IVertex rw_v) const + { + IVertex_vector non_zero_indices_u = neighbours_row_index(rw_u, false); + IVertex_vector non_zero_indices_v = neighbours_row_index(rw_v, false); + IVertex_vector common; + common.reserve(std::min(non_zero_indices_u.size(), non_zero_indices_v.size())); + std::set_intersection(non_zero_indices_u.begin(), non_zero_indices_u.end(), non_zero_indices_v.begin(), + non_zero_indices_v.end(), std::back_inserter(common)); + + return common; + } + + // Insert a vertex in the data structure + IVertex insert_vertex(Vertex_handle vertex) { + auto n = row_to_vertex_.size(); + auto result = vertex_to_row_.emplace(vertex, n); + // If it was not already inserted - Value won't be updated by emplace if it is already present + if (result.second) { + // Expand the matrix. The size of rows is irrelevant. + sparse_row_adjacency_matrix_.emplace_back((std::numeric_limits::max)()); + // Initializing the diagonal element of the adjency matrix corresponding to rw_b. + sparse_row_adjacency_matrix_[n].insert(n) = -1; // not an edge + // Must be done after reading its size() + row_to_vertex_.push_back(vertex); + } + return result.first->second; + } + + // Insert an edge in the data structure + // @exception std::invalid_argument In debug mode, if u == v + IEdge insert_new_edge(Vertex_handle u, Vertex_handle v, Edge_index idx) + { + GUDHI_CHECK((u != v), std::invalid_argument("Flag_complex_edge_collapser::insert_new_edge with u == v")); + // The edge must not be added before, it should be a new edge. + IVertex rw_u = insert_vertex(u); + IVertex rw_v = insert_vertex(v); +#ifdef DEBUG_TRACES + std::cout << "Inserting the edge " << u <<", " << v << std::endl; +#endif // DEBUG_TRACES + sparse_row_adjacency_matrix_[rw_u].insert(rw_v) = idx; + sparse_row_adjacency_matrix_[rw_v].insert(rw_u) = idx; + return std::minmax(rw_u, rw_v); + } + + public: + /** \brief Flag_complex_edge_collapser constructor from a range of filtered edges. + * + * @param[in] filtered_edge_range Range of filtered edges. Filtered edges must be in + * `Flag_complex_edge_collapser::Filtered_edge`. + * + * There is no need the range to be sorted, as it will be performed in + * `Flag_complex_edge_collapser::process_edges`. + */ + template + Flag_complex_edge_collapser(const Filtered_edge_range& filtered_edge_range) + : f_edge_vector_(filtered_edge_range.begin(), filtered_edge_range.end()) { } + + /** \brief Flag_complex_edge_collapser constructor from a proximity graph, cf. `Gudhi::compute_proximity_graph`. + * + * @param[in] one_skeleton_graph The one skeleton graph. The graph must be in + * `Flag_complex_edge_collapser::Proximity_graph`. + * + * The constructor is computing and filling a vector of `Flag_complex_edge_collapser::Filtered_edge` + */ + Flag_complex_edge_collapser(const Proximity_graph& one_skeleton_graph) { + // Insert all edges + for (auto edge_it = boost::edges(one_skeleton_graph); + edge_it.first != edge_it.second; ++edge_it.first) { + auto edge = *(edge_it.first); + Vertex_handle u = source(edge, one_skeleton_graph); + 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)}); + } + } + + /** \brief Performs edge collapse in a increasing sequence of the filtration value. + * + * \tparam FilteredEdgeOutput is a functor that furnishes `({Vertex_handle u, Vertex_handle v}, Filtration_value f)` + * that will get called on the output edges, in non-decreasing order of filtration. + */ + template + void process_edges(FilteredEdgeOutput filtered_edge_output) { + // Sort edges + 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); +#else + std::sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); +#endif + + for (Edge_index endIdx = 0; endIdx < f_edge_vector_.size(); endIdx++) { + Filtered_edge fec = f_edge_vector_[endIdx]; + 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); + + // Inserts the edge in the sparse matrix to update the graph (G_i) + IEdge ie = insert_new_edge(u, v, endIdx); + + iedge_to_index_map_.emplace(ie, endIdx); + critical_edge_indicator_.push_back(false); + + if (!edge_is_dominated(edge)) { + critical_edge_indicator_[endIdx] = true; + filtered_edge_output({u, v}, filt); + if (endIdx > 1) + set_edge_critical(endIdx, filt, filtered_edge_output); + } + } + } + +}; + +} // namespace collapse + +} // namespace Gudhi + +#endif // FLAG_COMPLEX_EDGE_COLLAPSER_H_ -- cgit v1.2.3 From b525bb68fa0980d4f54d20b7b719a7ec8891afe9 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 18 Jun 2020 10:06:24 +0200 Subject: code review: graph not hardcoded. Implies ctor from filtered edges to be modified --- .../example/edge_collapse_basic_example.cpp | 2 +- .../example/edge_collapse_conserve_persistence.cpp | 2 +- .../include/gudhi/Flag_complex_edge_collapser.h | 41 +++++++++++++++------- src/Collapse/test/collapse_unit_test.cpp | 4 +-- ...tance_matrix_edge_collapse_rips_persistence.cpp | 2 +- .../point_cloud_edge_collapse_rips_persistence.cpp | 2 +- 6 files changed, 34 insertions(+), 19 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index 333bc231..568115f5 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -26,7 +26,7 @@ int main() { {{0, 2}, 2.}, {{1, 3}, 2.}}; - Flag_complex_edge_collapser edge_collapser(graph); + Flag_complex_edge_collapser edge_collapser(graph.begin(), graph.end()); Filtered_edge_list collapse_edges; // Retrieve collapse edges from the output iterator diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index 701ea1af..b28af456 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -28,7 +28,7 @@ using Point = std::vector; using Vector_of_points = std::vector; using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; -using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; +using Proximity_graph = Gudhi::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 32438c3b..6afeaefc 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -54,9 +54,9 @@ namespace collapse { template class Flag_complex_edge_collapser { public: - /** \brief Re-define Vertex as Vertex_handle type to ease the interface with compute_proximity_graph. */ + /** \brief Re-define Vertex as Vertex_handle type to ease the interface with `Gudhi::Proximity_graph`. */ using Vertex_handle = Vertex; - /** \brief Re-define Filtration as Filtration_value type to ease the interface with compute_proximity_graph. */ + /** \brief Re-define Filtration as Filtration_value type to ease the interface with `Gudhi::Proximity_graph`. */ using Filtration_value = Filtration; /** \brief 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. @@ -80,8 +80,6 @@ class Flag_complex_edge_collapser { public: /** \brief Filtered_edge is a type to store an edge with its filtration value. */ using Filtered_edge = std::pair; - /** \brief Proximity_graph is a type that can be used to construct easily a Flag_complex_edge_collapser. */ - using Proximity_graph = Gudhi::Proximity_graph; private: // Map from row index to its vertex handle @@ -280,24 +278,41 @@ class Flag_complex_edge_collapser { public: /** \brief Flag_complex_edge_collapser constructor from a range of filtered edges. * - * @param[in] filtered_edge_range Range of filtered edges. Filtered edges must be in + * @param[in] begin Iterator on the first element of a filtered edges range. Filtered edges must be in + * `Flag_complex_edge_collapser::Filtered_edge`. + * + * @param[in] end Iterator on the last element of a filtered edges range. Filtered edges must be in * `Flag_complex_edge_collapser::Filtered_edge`. * * There is no need the range to be sorted, as it will be performed in * `Flag_complex_edge_collapser::process_edges`. */ - template - Flag_complex_edge_collapser(const Filtered_edge_range& filtered_edge_range) - : f_edge_vector_(filtered_edge_range.begin(), filtered_edge_range.end()) { } + template + Flag_complex_edge_collapser(Filtered_edge_iterator begin, Filtered_edge_iterator end) + : f_edge_vector_(begin, end) { } - /** \brief Flag_complex_edge_collapser constructor from a proximity graph, cf. `Gudhi::compute_proximity_graph`. + /** \brief Inserts all edges given by a OneSkeletonGraph into a vector of + * `Flag_complex_edge_collapser::Filtered_edge`. + * OneSkeletonGraph must be a model of + * boost::EdgeListGraph + * and boost::PropertyGraph. + * + * The edge filtration value is accessible through the property tag + * edge_filtration_t. * - * @param[in] one_skeleton_graph The one skeleton graph. The graph must be in - * `Flag_complex_edge_collapser::Proximity_graph`. + * boost::graph_traits::vertex_descriptor + * must be Vertex_handle. + * boost::graph_traits::directed_category + * can be directed_tag (the fastest, the least RAM use), undirected_tag or even + * bidirected_tag. * - * The constructor is computing and filling a vector of `Flag_complex_edge_collapser::Filtered_edge` + * If an edge appears with multiplicity, the function will arbitrarily pick one representative to read the filtration + * value. + * + * `Gudhi::Proximity_graph` is a good candidate for OneSkeletonGraph. */ - Flag_complex_edge_collapser(const Proximity_graph& one_skeleton_graph) { + template + Flag_complex_edge_collapser(const OneSkeletonGraph& one_skeleton_graph) { // Insert all edges for (auto edge_it = boost::edges(one_skeleton_graph); edge_it.first != edge_it.second; ++edge_it.first) { diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index e45dc339..3733ba13 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -49,7 +49,7 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F } std::cout << "COLLAPSE - keep edges: " << std::endl; - Flag_complex_edge_collapser edge_collapser(filtered_edges); + Flag_complex_edge_collapser edge_collapser(filtered_edges.begin(), filtered_edges.end()); Filtered_edge_list collapse_edges; edge_collapser.process_edges( [&collapse_edges](std::pair edge, Filtration_value filtration) { @@ -164,7 +164,7 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { {1., 1.} }; Filtration_value threshold = std::numeric_limits::infinity(); - using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; + using Proximity_graph = Gudhi::Proximity_graph; Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, threshold, Gudhi::Euclidean_distance()); diff --git a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp index ae9ff32b..378d64e6 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -21,7 +21,7 @@ using Filtration_value = Simplex_tree::Filtration_value; using Vertex_handle = Simplex_tree::Vertex_handle; using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; -using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; +using Proximity_graph = Gudhi::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; diff --git a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp index d2d31013..fcf858a0 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -29,7 +29,7 @@ using Point = std::vector; using Vector_of_points = std::vector; using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; -using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; +using Proximity_graph = Gudhi::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; -- cgit v1.2.3 From 08307b231e8fe2b044ade409b924f56b3eb7ebfe Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 18 Jun 2020 14:35:44 +0200 Subject: Code review: replace push_back with emplace_back --- .../example/edge_collapse_basic_example.cpp | 2 +- .../example/edge_collapse_conserve_persistence.cpp | 6 +++--- .../include/gudhi/Flag_complex_edge_collapser.h | 8 ++++---- src/Collapse/test/collapse_unit_test.cpp | 22 +++++++++++----------- 4 files changed, 19 insertions(+), 19 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index 17ed04a2..ac21e96f 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -32,7 +32,7 @@ int main() { // Retrieve collapse edges from the output iterator edge_collapser.process_edges( [&remaining_edges](std::pair edge, Filtration_value filtration) { - remaining_edges.push_back({edge, filtration}); + remaining_edges.emplace_back(Filtered_edge(edge, filtration)); }); for (Filtered_edge filtered_edge_from_collapse : remaining_edges) { diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index b28af456..8e03fa86 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -71,9 +71,9 @@ std::vector get_persistence_pairs(Simplex_tree& st, int ambien auto persistent_pairs = pcoh.get_persistent_pairs(); std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); for (auto pair : persistent_pairs) { - ppairs.push_back({st.dimension(get<0>(pair)), - st.filtration(get<0>(pair)), - st.filtration(get<1>(pair)) }); + ppairs.emplace_back(Persistence_pair(st.dimension(get<0>(pair)), + st.filtration(get<0>(pair)), + st.filtration(get<1>(pair)) )); } return ppairs; } diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 6afeaefc..02460efb 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -218,7 +218,7 @@ class Flag_complex_edge_collapser { if ((closed && rw_u == rw_v) || (ei = it.value()) <= current_backward || critical_edge_indicator_[ei]) { - neighbors.push_back(rw_v); + neighbors.emplace_back(rw_v); #ifdef DEBUG_TRACES std::cout << row_to_vertex_[rw_v] << ", " ; #endif // DEBUG_TRACES @@ -254,7 +254,7 @@ class Flag_complex_edge_collapser { // Initializing the diagonal element of the adjency matrix corresponding to rw_b. sparse_row_adjacency_matrix_[n].insert(n) = -1; // not an edge // Must be done after reading its size() - row_to_vertex_.push_back(vertex); + row_to_vertex_.emplace_back(vertex); } return result.first->second; } @@ -319,7 +319,7 @@ class Flag_complex_edge_collapser { auto edge = *(edge_it.first); Vertex_handle u = source(edge, one_skeleton_graph); 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)}); + f_edge_vector_.emplace_back(Filtered_edge({u, v}, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge))); } } @@ -353,7 +353,7 @@ class Flag_complex_edge_collapser { IEdge ie = insert_new_edge(u, v, endIdx); iedge_to_index_map_.emplace(ie, endIdx); - critical_edge_indicator_.push_back(false); + critical_edge_indicator_.emplace_back(false); if (!edge_is_dominated(edge)) { critical_edge_indicator_[endIdx] = true; diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 6ca49299..a6d3ca1c 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -54,7 +54,7 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F edge_collapser.process_edges( [&remaining_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - remaining_edges.push_back({edge, filtration}); + remaining_edges.emplace_back(Filtered_edge(edge, filtration)); }); std::cout << "AFTER COLLAPSE - Total number of edges: " << remaining_edges.size() << std::endl; BOOST_CHECK(remaining_edges.size() <= filtered_edges.size()); @@ -96,8 +96,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| // o---o // 0 3 - edges.push_back({{0, 2}, 2.}); - edges.push_back({{1, 3}, 2.}); + edges.emplace_back(Filtered_edge({0, 2}, 2.)); + edges.emplace_back(Filtered_edge({1, 3}, 2.)); trace_and_check_collapse(edges, {{{1, 3}, 2.}}); // 1 2 4 @@ -107,9 +107,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| | // o---o---o // 0 3 5 - edges.push_back({{2, 4}, 3.}); - edges.push_back({{4, 5}, 3.}); - edges.push_back({{5, 3}, 3.}); + edges.emplace_back(Filtered_edge({2, 4}, 3.)); + edges.emplace_back(Filtered_edge({4, 5}, 3.)); + edges.emplace_back(Filtered_edge({5, 3}, 3.)); trace_and_check_collapse(edges, {{{1, 3}, 2.}}); // 1 2 4 @@ -119,8 +119,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.push_back({{2, 5}, 4.}); - edges.push_back({{4, 3}, 4.}); + edges.emplace_back(Filtered_edge({2, 5}, 4.)); + edges.emplace_back(Filtered_edge({4, 3}, 4.)); trace_and_check_collapse(edges, {{{1, 3}, 2.}, {{4, 3}, 4.}}); // 1 2 4 @@ -130,8 +130,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.push_back({{1, 5}, 5.}); - edges.push_back({{0, 4}, 5.}); + edges.emplace_back(Filtered_edge({1, 5}, 5.)); + edges.emplace_back(Filtered_edge({0, 4}, 5.)); trace_and_check_collapse(edges, {{{1, 3}, 2.}, {{4, 3}, 4.}, {{0, 4}, 5.}}); } @@ -173,7 +173,7 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { edge_collapser.process_edges( [&remaining_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - remaining_edges.push_back({edge, filtration}); + remaining_edges.emplace_back(Filtered_edge(edge, filtration)); }); BOOST_CHECK(remaining_edges.size() == 5); -- cgit v1.2.3 From 7e92bb3aeddd0cdd32a867ca7a827ed3ed93dbb4 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 18 Jun 2020 22:56:43 +0200 Subject: Code review: Use a flat (u, v, filt) instead of (pair(u, v), filt) --- .../example/edge_collapse_basic_example.cpp | 22 ++++--- .../example/edge_collapse_conserve_persistence.cpp | 4 +- .../include/gudhi/Flag_complex_edge_collapser.h | 49 +++++++-------- src/Collapse/test/collapse_unit_test.cpp | 70 ++++++++++++---------- ...tance_matrix_edge_collapse_rips_persistence.cpp | 7 +-- .../point_cloud_edge_collapse_rips_persistence.cpp | 7 +-- 6 files changed, 74 insertions(+), 85 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index ac21e96f..d374fef2 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -10,7 +10,6 @@ int main() { using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; using Filtered_edge = Flag_complex_edge_collapser::Filtered_edge; using Filtered_edge_list = std::vector; - using Edge = Flag_complex_edge_collapser::Edge; // 1 2 // o---o @@ -19,26 +18,25 @@ int main() { // |/ \| // o---o // 0 3 - Filtered_edge_list graph = {{{0, 1}, 1.}, - {{1, 2}, 1.}, - {{2, 3}, 1.}, - {{3, 0}, 1.}, - {{0, 2}, 2.}, - {{1, 3}, 2.}}; + Filtered_edge_list graph = {{0, 1, 1.}, + {1, 2, 1.}, + {2, 3, 1.}, + {3, 0, 1.}, + {0, 2, 2.}, + {1, 3, 2.}}; Flag_complex_edge_collapser edge_collapser(graph.begin(), graph.end()); Filtered_edge_list remaining_edges; // Retrieve collapse edges from the output iterator edge_collapser.process_edges( - [&remaining_edges](std::pair edge, Filtration_value filtration) { - remaining_edges.emplace_back(Filtered_edge(edge, filtration)); + [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { + remaining_edges.emplace_back(Filtered_edge(u, v, filtration)); }); for (Filtered_edge filtered_edge_from_collapse : remaining_edges) { - Edge edge_from_collapse = std::get<0>(filtered_edge_from_collapse); - std::cout << "fn[" << std::get<0>(edge_from_collapse) << ", " << std::get<1>(edge_from_collapse) << "] = " - << std::get<1>(filtered_edge_from_collapse) << std::endl; + std::cout << "fn[" << std::get<0>(filtered_edge_from_collapse) << ", " << std::get<1>(filtered_edge_from_collapse) + << "] = " << std::get<2>(filtered_edge_from_collapse) << std::endl; } return 0; diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index 0a5d9241..69755fc9 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -117,9 +117,9 @@ int main(int argc, char* argv[]) { stree_from_collapse.insert_simplex({vertex}, 0.); } edge_collapser.process_edges( - [&stree_from_collapse](const std::vector& edge, Filtration_value filtration) { + [&stree_from_collapse](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { // insert the edge - stree_from_collapse.insert_simplex(edge, filtration); + stree_from_collapse.insert_simplex({u, v}, filtration); }); std::vector persistence_intervals_from_collapse = get_persistence_intervals(stree_from_collapse, ambient_dim); diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 02460efb..9fa2d7c9 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -58,10 +58,6 @@ class Flag_complex_edge_collapser { using Vertex_handle = Vertex; /** \brief Re-define Filtration as Filtration_value type to ease the interface with `Gudhi::Proximity_graph`. */ using Filtration_value = Filtration; - /** \brief 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 Edge = std::pair; private: // internal numbering of vertices and edges @@ -79,7 +75,7 @@ class Flag_complex_edge_collapser { public: /** \brief Filtered_edge is a type to store an edge with its filtration value. */ - using Filtered_edge = std::pair; + using Filtered_edge = std::tuple; private: // Map from row index to its vertex handle @@ -105,12 +101,9 @@ class Flag_complex_edge_collapser { // The input, a vector of filtered edges. std::vector f_edge_vector_; - // Edge e is the actual edge (u,v), with Vertex_handle u and v, not IVertex. - bool edge_is_dominated(const Edge& edge) const + // Edge is the actual edge (u,v), with Vertex_handle u and v, not IVertex. + bool edge_is_dominated(Vertex_handle u, Vertex_handle v) const { - Vertex_handle u = std::get<0>(edge); - Vertex_handle v = std::get<1>(edge); - const IVertex rw_u = vertex_to_row_.at(u); const IVertex rw_v = vertex_to_row_.at(v); #ifdef DEBUG_TRACES @@ -141,13 +134,12 @@ class Flag_complex_edge_collapser { std::set three_clique_indices(Edge_index crit) { std::set edge_indices; - Edge edge = std::get<0>(f_edge_vector_[crit]); - Vertex_handle u = std::get<0>(edge); - Vertex_handle v = std::get<1>(edge); + Vertex_handle u = std::get<0>(f_edge_vector_[crit]); + Vertex_handle v = std::get<1>(f_edge_vector_[crit]); #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<2>(f_edge_vector_[crit]) << std::endl; #endif // DEBUG_TRACES auto rw_u = vertex_to_row_[u]; auto rw_v = vertex_to_row_[v]; @@ -174,17 +166,16 @@ class Flag_complex_edge_collapser { // Cannot use boost::adaptors::reverse in such dynamic cases apparently for (auto it = effected_indices.rbegin(); it != effected_indices.rend(); ++it) { current_backward = *it; - Edge edge = std::get<0>(f_edge_vector_[current_backward]); - Vertex_handle u = std::get<0>(edge); - Vertex_handle v = std::get<1>(edge); + Vertex_handle u = std::get<0>(f_edge_vector_[current_backward]); + Vertex_handle v = std::get<1>(f_edge_vector_[current_backward]); // If current_backward is not critical so it should be processed, otherwise it stays in the graph if (!critical_edge_indicator_[current_backward]) { - if (!edge_is_dominated(edge)) { + if (!edge_is_dominated(u, v)) { #ifdef DEBUG_TRACES std::cout << "The curent index became critical " << current_backward << std::endl; #endif // DEBUG_TRACES critical_edge_indicator_[current_backward] = true; - filtered_edge_output({u, v}, filt); + filtered_edge_output(u, v, filt); std::set inner_effected_indcs = three_clique_indices(current_backward); for (auto inr_idx : inner_effected_indcs) { if(inr_idx < current_backward) // && !critical_edge_indicator_[inr_idx] @@ -319,21 +310,22 @@ class Flag_complex_edge_collapser { auto edge = *(edge_it.first); Vertex_handle u = source(edge, one_skeleton_graph); Vertex_handle v = target(edge, one_skeleton_graph); - f_edge_vector_.emplace_back(Filtered_edge({u, v}, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge))); + f_edge_vector_.emplace_back(Filtered_edge(u, v, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge))); } } /** \brief Performs edge collapse in a increasing sequence of the filtration value. * - * \tparam FilteredEdgeOutput is a functor that furnishes `({Vertex_handle u, Vertex_handle v}, Filtration_value f)` - * that will get called on the output edges, in non-decreasing order of filtration. + * \tparam filtered_edge_output is a functor that is called on the output edges, in non-decreasing order of + * filtration, as filtered_edge_output(u, v, f) where u and v are Vertex_handle representing the extremities of the + * edge, and f is its new Filtration_value. */ template void process_edges(FilteredEdgeOutput filtered_edge_output) { // Sort edges auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool { - return (get<1>(edge_a) < get<1>(edge_b)); + return (get<2>(edge_a) < get<2>(edge_b)); }; #ifdef GUDHI_USE_TBB @@ -344,10 +336,9 @@ class Flag_complex_edge_collapser { for (Edge_index endIdx = 0; endIdx < f_edge_vector_.size(); endIdx++) { Filtered_edge fec = f_edge_vector_[endIdx]; - 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); + Vertex_handle u = std::get<0>(fec); + Vertex_handle v = std::get<1>(fec); + Filtration_value filt = std::get<2>(fec); // Inserts the edge in the sparse matrix to update the graph (G_i) IEdge ie = insert_new_edge(u, v, endIdx); @@ -355,9 +346,9 @@ class Flag_complex_edge_collapser { iedge_to_index_map_.emplace(ie, endIdx); critical_edge_indicator_.emplace_back(false); - if (!edge_is_dominated(edge)) { + if (!edge_is_dominated(u, v)) { critical_edge_indicator_[endIdx] = true; - filtered_edge_output({u, v}, filt); + filtered_edge_output(u, v, filt); if (endIdx > 1) set_edge_critical(endIdx, filt, filtered_edge_output); } diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index a6d3ca1c..67f1a732 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -44,33 +44,31 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F std::cout << "BEFORE COLLAPSE - Total number of edges: " << filtered_edges.size() << std::endl; BOOST_CHECK(filtered_edges.size() > 0); for (auto filtered_edge : filtered_edges) { - auto edge = std::get<0>(filtered_edge); - std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << std::get<1>(filtered_edge) << std::endl; + std::cout << "f[" << std::get<0>(filtered_edge) << ", " << std::get<1>(filtered_edge) << "] = " + << std::get<2>(filtered_edge) << std::endl; } std::cout << "COLLAPSE - keep edges: " << std::endl; Flag_complex_edge_collapser edge_collapser(filtered_edges.begin(), filtered_edges.end()); Filtered_edge_list remaining_edges; edge_collapser.process_edges( - [&remaining_edges](std::pair edge, Filtration_value filtration) { - std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - remaining_edges.emplace_back(Filtered_edge(edge, filtration)); + [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { + std::cout << "f[" << u << ", " << v << "] = " << filtration << std::endl; + remaining_edges.emplace_back(Filtered_edge(u, v, filtration)); }); std::cout << "AFTER COLLAPSE - Total number of edges: " << remaining_edges.size() << std::endl; BOOST_CHECK(remaining_edges.size() <= filtered_edges.size()); for (auto filtered_edge_from_collapse : remaining_edges) { - auto edge_from_collapse = std::get<0>(filtered_edge_from_collapse); - std::cout << "f[" << std::get<0>(edge_from_collapse) << ", " << std::get<1>(edge_from_collapse) << "] = " - << std::get<1>(filtered_edge_from_collapse) << std::endl; + std::cout << "f[" << std::get<0>(filtered_edge_from_collapse) << ", " << std::get<1>(filtered_edge_from_collapse) + << "] = " << std::get<2>(filtered_edge_from_collapse) << std::endl; // Check each edge from collapse is in the input BOOST_CHECK(find_edge_in_list(filtered_edge_from_collapse, filtered_edges)); } std::cout << "CHECK COLLAPSE - Total number of removed edges: " << removed_edges.size() << std::endl; for (auto removed_filtered_edge : removed_edges) { - auto removed_edge = std::get<0>(removed_filtered_edge); - std::cout << "f[" << std::get<0>(removed_edge) << ", " << std::get<1>(removed_edge) << "] = " - << std::get<1>(removed_filtered_edge) << std::endl; + std::cout << "f[" << std::get<0>(removed_filtered_edge) << ", " << std::get<1>(removed_filtered_edge) << "] = " + << std::get<2>(removed_filtered_edge) << std::endl; // Check each removed edge from collapse is in the input BOOST_CHECK(!find_edge_in_list(removed_filtered_edge, remaining_edges)); } @@ -86,7 +84,10 @@ BOOST_AUTO_TEST_CASE(collapse) { // | | // o---o // 0 3 - Filtered_edge_list edges {{{0, 1}, 1.}, {{1, 2}, 1.}, {{2, 3}, 1.}, {{3, 0}, 1.}}; + Filtered_edge_list edges {{0, 1, 1.}, + {1, 2, 1.}, + {2, 3, 1.}, + {3, 0, 1.}}; trace_and_check_collapse(edges, {}); // 1 2 @@ -96,9 +97,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| // o---o // 0 3 - edges.emplace_back(Filtered_edge({0, 2}, 2.)); - edges.emplace_back(Filtered_edge({1, 3}, 2.)); - trace_and_check_collapse(edges, {{{1, 3}, 2.}}); + edges.emplace_back(Filtered_edge(0, 2, 2.)); + edges.emplace_back(Filtered_edge(1, 3, 2.)); + trace_and_check_collapse(edges, {{1, 3, 2.}}); // 1 2 4 // o---o---o @@ -107,10 +108,10 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| | // o---o---o // 0 3 5 - edges.emplace_back(Filtered_edge({2, 4}, 3.)); - edges.emplace_back(Filtered_edge({4, 5}, 3.)); - edges.emplace_back(Filtered_edge({5, 3}, 3.)); - trace_and_check_collapse(edges, {{{1, 3}, 2.}}); + edges.emplace_back(Filtered_edge(2, 4, 3.)); + edges.emplace_back(Filtered_edge(4, 5, 3.)); + edges.emplace_back(Filtered_edge(5, 3, 3.)); + trace_and_check_collapse(edges, {{1, 3, 2.}}); // 1 2 4 // o---o---o @@ -119,9 +120,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.emplace_back(Filtered_edge({2, 5}, 4.)); - edges.emplace_back(Filtered_edge({4, 3}, 4.)); - trace_and_check_collapse(edges, {{{1, 3}, 2.}, {{4, 3}, 4.}}); + edges.emplace_back(Filtered_edge(2, 5, 4.)); + edges.emplace_back(Filtered_edge(4, 3, 4.)); + trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}}); // 1 2 4 // o---o---o @@ -130,9 +131,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.emplace_back(Filtered_edge({1, 5}, 5.)); - edges.emplace_back(Filtered_edge({0, 4}, 5.)); - trace_and_check_collapse(edges, {{{1, 3}, 2.}, {{4, 3}, 4.}, {{0, 4}, 5.}}); + edges.emplace_back(Filtered_edge(1, 5, 5.)); + edges.emplace_back(Filtered_edge(0, 4, 5.)); + trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}, {0, 4, 5.}}); } BOOST_AUTO_TEST_CASE(collapse_from_array) { @@ -144,8 +145,13 @@ BOOST_AUTO_TEST_CASE(collapse_from_array) { // |/ \| // o---o // 0 3 - std::array f_edge_array = {{{{0, 1}, 1.}, {{1, 2}, 1.}, {{2, 3}, 1.}, {{3, 0}, 1.}, {{0, 2}, 2.}, {{1, 3}, 2.}}}; - trace_and_check_collapse(f_edge_array, {{{1, 3}, 2.}}); + std::array f_edge_array = {{{0, 1, 1.}, + {1, 2, 1.}, + {2, 3, 1.}, + {3, 0, 1.}, + {0, 2, 2.}, + {1, 3, 2.}}}; + trace_and_check_collapse(f_edge_array, {{1, 3, 2.}}); } @@ -171,9 +177,9 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { Flag_complex_edge_collapser edge_collapser(proximity_graph); Filtered_edge_list remaining_edges; edge_collapser.process_edges( - [&remaining_edges](std::pair edge, Filtration_value filtration) { - std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - remaining_edges.emplace_back(Filtered_edge(edge, filtration)); + [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { + std::cout << "f[" << u << ", " << v << "] = " << filtration << std::endl; + remaining_edges.emplace_back(Filtered_edge(u, v, filtration)); }); BOOST_CHECK(remaining_edges.size() == 5); @@ -181,9 +187,9 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { std::size_t filtration_is_diagonal_length_nb = 0; float epsilon = std::numeric_limits::epsilon(); for (auto filtered_edge : remaining_edges) { - if (std::get<1>(filtered_edge) == 1.) + if (std::get<2>(filtered_edge) == 1.) filtration_is_edge_length_nb++; - if (std::fabs(std::get<1>(filtered_edge) - std::sqrt(2.)) <= epsilon) + if (std::fabs(std::get<2>(filtered_edge) - std::sqrt(2.)) <= epsilon) filtration_is_diagonal_length_nb++; } BOOST_CHECK(filtration_is_edge_length_nb == 4); diff --git a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp index 378d64e6..88cd7b54 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -98,12 +98,9 @@ int main(int argc, char* argv[]) { stree.insert_simplex({vertex}, 0.); } edge_collapser.process_edges( - [&stree](std::vector edge, Filtration_value filtration) { - // insert the 2 vertices with a 0. filtration value just like a Rips - stree.insert_simplex({edge[0]}, 0.); - stree.insert_simplex({edge[1]}, 0.); + [&stree](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { // insert the edge - stree.insert_simplex(edge, filtration); + stree.insert_simplex({u, v}, filtration); }); stree.expansion(dim_max); diff --git a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp index fcf858a0..69e83597 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -85,12 +85,9 @@ int main(int argc, char* argv[]) { stree.insert_simplex({vertex}, 0.); } edge_collapser.process_edges( - [&stree](const std::vector& edge, Filtration_value filtration) { - // insert the 2 vertices with a 0. filtration value just like a Rips - stree.insert_simplex({edge[0]}, 0.); - stree.insert_simplex({edge[1]}, 0.); + [&stree](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { // insert the edge - stree.insert_simplex(edge, filtration); + stree.insert_simplex({u, v}, filtration); }); stree.expansion(dim_max); -- cgit v1.2.3 From 716085ac81cd90e3a0f51d2ad416e50b6a5e6fe7 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 18 Jun 2020 23:16:12 +0200 Subject: Code review: modify last element with final aka. std::end --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 9fa2d7c9..220330a7 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -269,11 +269,11 @@ class Flag_complex_edge_collapser { public: /** \brief Flag_complex_edge_collapser constructor from a range of filtered edges. * - * @param[in] begin Iterator on the first element of a filtered edges range. Filtered edges must be in - * `Flag_complex_edge_collapser::Filtered_edge`. + * @param[in] begin Iterator on the first element of a filtered edges range, aka. `std::begin`. Filtered edges must + * be in `Flag_complex_edge_collapser::Filtered_edge`. * - * @param[in] end Iterator on the last element of a filtered edges range. Filtered edges must be in - * `Flag_complex_edge_collapser::Filtered_edge`. + * @param[in] end Iterator on the final element of a filtered edges range, aka. `std::end`. Filtered edges must be + * in `Flag_complex_edge_collapser::Filtered_edge`. * * There is no need the range to be sorted, as it will be performed in * `Flag_complex_edge_collapser::process_edges`. -- cgit v1.2.3 From 1fdaa406b6b0b85e409bd97090098ed5846c078c Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 22 Jun 2020 23:17:58 +0200 Subject: Don't explicitly copy the neighbors to a vector each time --- .../include/gudhi/Flag_complex_edge_collapser.h | 78 ++++++++++++++-------- 1 file changed, 49 insertions(+), 29 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 220330a7..09986d08 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -17,6 +17,7 @@ #include #include +#include #include @@ -70,6 +71,48 @@ class Flag_complex_edge_collapser { using Sparse_vector = Eigen::SparseVector; using Sparse_row_matrix = std::vector; + // Range of neighbors of a vertex + template + struct Neighbours { + class iterator : public boost::iterator_facade + { + public: + iterator():ptr(nullptr){} + iterator(Neighbours const*p):ptr(p){find_valid();} + private: + friend class boost::iterator_core_access; + Neighbours const*ptr; + void increment(){ + ++ptr->it; + find_valid(); + } + void find_valid(){ + auto& it = ptr->it; + do { + if(!it) { ptr=nullptr; break; } + if(IVertex(it.index()) == ptr->u) { + if(closed) break; + else continue; + } + Edge_index e = it.value(); + if(e <= ptr->ec->current_backward || ptr->ec->critical_edge_indicator_[e]) break; + } while(++it, true); + } + bool equal(iterator const& other) const { return ptr == other.ptr; } + IVertex dereference() const { return ptr->it.index(); } + }; + typedef iterator const_iterator; + mutable typename Sparse_vector::InnerIterator it; + Flag_complex_edge_collapser const*ec; + IVertex u; + iterator begin() const { return this; } + iterator end() const { return {}; } + explicit Neighbours(Flag_complex_edge_collapser const*p,IVertex u):it(p->sparse_row_adjacency_matrix_[u]),ec(p),u(u){} + }; + // A range of row indices using IVertex_vector = std::vector; @@ -121,7 +164,7 @@ class Flag_complex_edge_collapser { return true; else for (auto rw_c : common_neighbours) { - auto neighbours_c = neighbours_row_index(rw_c, true); + auto neighbours_c = neighbours_row_index(rw_c); // If neighbours_c contains the common neighbours. if (std::includes(neighbours_c.begin(), neighbours_c.end(), common_neighbours.begin(), common_neighbours.end())) @@ -193,41 +236,18 @@ class Flag_complex_edge_collapser { } // Returns list of neighbors of a particular vertex. - IVertex_vector neighbours_row_index(IVertex rw_u, bool closed) const + template + auto neighbours_row_index(IVertex rw_u) const { - IVertex_vector neighbors; - neighbors.reserve(sparse_row_adjacency_matrix_[rw_u].nonZeros()); // too much, but who cares -#ifdef DEBUG_TRACES - std::cout << "The neighbours of the vertex: " << row_to_vertex_[rw_u] << " are. " << std::endl; -#endif // DEBUG_TRACES - // Iterate over the neighbors - for (typename Sparse_vector::InnerIterator it(sparse_row_adjacency_matrix_[rw_u]); it; ++it) { - IVertex rw_v = it.index(); - if (!closed && rw_u == rw_v) continue; - Edge_index ei; - // If the vertex v is not dominated and the edge {u,v} is still in the matrix - if ((closed && rw_u == rw_v) || - (ei = it.value()) <= current_backward || - critical_edge_indicator_[ei]) { - neighbors.emplace_back(rw_v); -#ifdef DEBUG_TRACES - std::cout << row_to_vertex_[rw_v] << ", " ; -#endif // DEBUG_TRACES - } - } -#ifdef DEBUG_TRACES - std::cout << std::endl; -#endif // DEBUG_TRACES - return neighbors; + return Neighbours(this, rw_u); } // Returns the list of open neighbours of the edge :{u,v}. IVertex_vector open_common_neighbours_row_index(IVertex rw_u, IVertex rw_v) const { - IVertex_vector non_zero_indices_u = neighbours_row_index(rw_u, false); - IVertex_vector non_zero_indices_v = neighbours_row_index(rw_v, false); + auto non_zero_indices_u = neighbours_row_index(rw_u); + auto non_zero_indices_v = neighbours_row_index(rw_v); IVertex_vector common; - common.reserve(std::min(non_zero_indices_u.size(), non_zero_indices_v.size())); std::set_intersection(non_zero_indices_u.begin(), non_zero_indices_u.end(), non_zero_indices_v.begin(), non_zero_indices_v.end(), std::back_inserter(common)); -- cgit v1.2.3 From e4e55054945ec25bba613bf9051b9dde0b09357e Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Tue, 23 Jun 2020 00:00:58 +0200 Subject: Fix uses of emplace_back --- .../example/edge_collapse_basic_example.cpp | 2 +- .../example/edge_collapse_conserve_persistence.cpp | 6 +++--- .../include/gudhi/Flag_complex_edge_collapser.h | 6 +++--- src/Collapse/test/collapse_unit_test.cpp | 24 +++++++++++----------- 4 files changed, 19 insertions(+), 19 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index d374fef2..8e7ca3b1 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -31,7 +31,7 @@ int main() { // Retrieve collapse edges from the output iterator edge_collapser.process_edges( [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { - remaining_edges.emplace_back(Filtered_edge(u, v, filtration)); + remaining_edges.emplace_back(u, v, filtration); }); for (Filtered_edge filtered_edge_from_collapse : remaining_edges) { diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index 69755fc9..d78a4d54 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -68,9 +68,9 @@ std::vector get_persistence_intervals(Simplex_tree& st, in auto persistent_pairs = pcoh.get_persistent_pairs(); std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); for (auto pair : persistent_pairs) { - persistence_intervals.emplace_back(Persistence_interval(st.dimension(get<0>(pair)), - st.filtration(get<0>(pair)), - st.filtration(get<1>(pair)) )); + persistence_intervals.emplace_back(st.dimension(get<0>(pair)), + st.filtration(get<0>(pair)), + st.filtration(get<1>(pair))); } return persistence_intervals; } diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 09986d08..29850382 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -265,7 +265,7 @@ class Flag_complex_edge_collapser { // Initializing the diagonal element of the adjency matrix corresponding to rw_b. sparse_row_adjacency_matrix_[n].insert(n) = -1; // not an edge // Must be done after reading its size() - row_to_vertex_.emplace_back(vertex); + row_to_vertex_.push_back(vertex); } return result.first->second; } @@ -330,7 +330,7 @@ class Flag_complex_edge_collapser { auto edge = *(edge_it.first); Vertex_handle u = source(edge, one_skeleton_graph); Vertex_handle v = target(edge, one_skeleton_graph); - f_edge_vector_.emplace_back(Filtered_edge(u, v, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge))); + f_edge_vector_.emplace_back(u, v, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge)); } } @@ -364,7 +364,7 @@ class Flag_complex_edge_collapser { IEdge ie = insert_new_edge(u, v, endIdx); iedge_to_index_map_.emplace(ie, endIdx); - critical_edge_indicator_.emplace_back(false); + critical_edge_indicator_.push_back(false); if (!edge_is_dominated(u, v)) { critical_edge_indicator_[endIdx] = true; diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 67f1a732..108f77e4 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -54,7 +54,7 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F edge_collapser.process_edges( [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { std::cout << "f[" << u << ", " << v << "] = " << filtration << std::endl; - remaining_edges.emplace_back(Filtered_edge(u, v, filtration)); + remaining_edges.emplace_back(u, v, filtration); }); std::cout << "AFTER COLLAPSE - Total number of edges: " << remaining_edges.size() << std::endl; BOOST_CHECK(remaining_edges.size() <= filtered_edges.size()); @@ -97,8 +97,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| // o---o // 0 3 - edges.emplace_back(Filtered_edge(0, 2, 2.)); - edges.emplace_back(Filtered_edge(1, 3, 2.)); + edges.emplace_back(0, 2, 2.); + edges.emplace_back(1, 3, 2.); trace_and_check_collapse(edges, {{1, 3, 2.}}); // 1 2 4 @@ -108,9 +108,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| | // o---o---o // 0 3 5 - edges.emplace_back(Filtered_edge(2, 4, 3.)); - edges.emplace_back(Filtered_edge(4, 5, 3.)); - edges.emplace_back(Filtered_edge(5, 3, 3.)); + edges.emplace_back(2, 4, 3.); + edges.emplace_back(4, 5, 3.); + edges.emplace_back(5, 3, 3.); trace_and_check_collapse(edges, {{1, 3, 2.}}); // 1 2 4 @@ -120,8 +120,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.emplace_back(Filtered_edge(2, 5, 4.)); - edges.emplace_back(Filtered_edge(4, 3, 4.)); + edges.emplace_back(2, 5, 4.); + edges.emplace_back(4, 3, 4.); trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}}); // 1 2 4 @@ -131,8 +131,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.emplace_back(Filtered_edge(1, 5, 5.)); - edges.emplace_back(Filtered_edge(0, 4, 5.)); + edges.emplace_back(1, 5, 5.); + edges.emplace_back(0, 4, 5.); trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}, {0, 4, 5.}}); } @@ -179,7 +179,7 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { edge_collapser.process_edges( [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { std::cout << "f[" << u << ", " << v << "] = " << filtration << std::endl; - remaining_edges.emplace_back(Filtered_edge(u, v, filtration)); + remaining_edges.emplace_back(u, v, filtration); }); BOOST_CHECK(remaining_edges.size() == 5); @@ -194,4 +194,4 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { } BOOST_CHECK(filtration_is_edge_length_nb == 4); BOOST_CHECK(filtration_is_diagonal_length_nb == 1); -} \ No newline at end of file +} -- cgit v1.2.3 From ddd12a6caab2040d7e8e6573c71f9da4a90bb346 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 25 Jun 2020 11:11:22 +0200 Subject: Code review: remove 'boost::' in front of edges and get method --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 220330a7..331a82f9 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -305,12 +305,12 @@ class Flag_complex_edge_collapser { template Flag_complex_edge_collapser(const OneSkeletonGraph& one_skeleton_graph) { // Insert all edges - for (auto edge_it = boost::edges(one_skeleton_graph); + for (auto edge_it = edges(one_skeleton_graph); edge_it.first != edge_it.second; ++edge_it.first) { auto edge = *(edge_it.first); Vertex_handle u = source(edge, one_skeleton_graph); Vertex_handle v = target(edge, one_skeleton_graph); - f_edge_vector_.emplace_back(Filtered_edge(u, v, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge))); + f_edge_vector_.emplace_back(Filtered_edge(u, v, get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge))); } } -- cgit v1.2.3 From 12ff6eda212250a55492338b2a53ef774dd1829b Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 25 Jun 2020 11:24:05 +0200 Subject: Doc review: link on recent boost doc --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index bf23d8f8..61932427 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -305,8 +305,8 @@ class Flag_complex_edge_collapser { /** \brief Inserts all edges given by a OneSkeletonGraph into a vector of * `Flag_complex_edge_collapser::Filtered_edge`. * OneSkeletonGraph must be a model of - * boost::EdgeListGraph - * and boost::PropertyGraph. + * boost::EdgeListGraph + * and boost::PropertyGraph. * * The edge filtration value is accessible through the property tag * edge_filtration_t. -- cgit v1.2.3 From 2610ce8092a3935e228065884bcbd70d910b40cd Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 25 Jun 2020 11:27:20 +0200 Subject: Doc review: no duplicated edges --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 61932427..44190997 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -317,8 +317,7 @@ class Flag_complex_edge_collapser { * can be directed_tag (the fastest, the least RAM use), undirected_tag or even * bidirected_tag. * - * If an edge appears with multiplicity, the function will arbitrarily pick one representative to read the filtration - * value. + * It is required to have no duplicated edges in the graph. * * `Gudhi::Proximity_graph` is a good candidate for OneSkeletonGraph. */ -- cgit v1.2.3 From b522b330b10d11f0da640b8bba7ee689dea774d7 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 25 Jun 2020 17:10:36 +0200 Subject: Remove interface with boost graphs and use boost transform for data from graphs --- .../example/edge_collapse_basic_example.cpp | 2 +- .../example/edge_collapse_conserve_persistence.cpp | 10 ++++- .../include/gudhi/Flag_complex_edge_collapser.h | 46 +++------------------- src/Collapse/test/collapse_unit_test.cpp | 13 +++++- ...tance_matrix_edge_collapse_rips_persistence.cpp | 9 ++++- .../point_cloud_edge_collapse_rips_persistence.cpp | 9 ++++- 6 files changed, 43 insertions(+), 46 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index 8e7ca3b1..69ce329e 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -25,7 +25,7 @@ int main() { {0, 2, 2.}, {1, 3, 2.}}; - Flag_complex_edge_collapser edge_collapser(graph.begin(), graph.end()); + Flag_complex_edge_collapser edge_collapser(graph); Filtered_edge_list remaining_edges; // Retrieve collapse edges from the output iterator diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index d78a4d54..e6672d25 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -15,6 +15,8 @@ #include #include +#include + #include // for std::pair #include #include @@ -109,7 +111,13 @@ int main(int argc, char* argv[]) { int ambient_dim = point_vector[0].size(); // ***** Simplex tree from a flag complex built after collapse ***** - Flag_complex_edge_collapser edge_collapser(proximity_graph); + Flag_complex_edge_collapser edge_collapser( + boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ + return std::make_tuple(source(edge, proximity_graph), + target(edge, proximity_graph), + get(Gudhi::edge_filtration_t(), proximity_graph, edge)); + }) + ); Simplex_tree stree_from_collapse; for (Vertex_handle vertex = 0; static_cast(vertex) < point_vector.size(); vertex++) { diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 44190997..9cd57d7e 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -289,49 +289,15 @@ class Flag_complex_edge_collapser { public: /** \brief Flag_complex_edge_collapser constructor from a range of filtered edges. * - * @param[in] begin Iterator on the first element of a filtered edges range, aka. `std::begin`. Filtered edges must - * be in `Flag_complex_edge_collapser::Filtered_edge`. - * - * @param[in] end Iterator on the final element of a filtered edges range, aka. `std::end`. Filtered edges must be - * in `Flag_complex_edge_collapser::Filtered_edge`. - * - * There is no need the range to be sorted, as it will be performed in + * @param[in] edges Range of Filtered edges range.There is no need the range to be sorted, as it will be performed in * `Flag_complex_edge_collapser::process_edges`. - */ - template - Flag_complex_edge_collapser(Filtered_edge_iterator begin, Filtered_edge_iterator end) - : f_edge_vector_(begin, end) { } - - /** \brief Inserts all edges given by a OneSkeletonGraph into a vector of - * `Flag_complex_edge_collapser::Filtered_edge`. - * OneSkeletonGraph must be a model of - * boost::EdgeListGraph - * and boost::PropertyGraph. * - * The edge filtration value is accessible through the property tag - * edge_filtration_t. - * - * boost::graph_traits::vertex_descriptor - * must be Vertex_handle. - * boost::graph_traits::directed_category - * can be directed_tag (the fastest, the least RAM use), undirected_tag or even - * bidirected_tag. - * - * It is required to have no duplicated edges in the graph. - * - * `Gudhi::Proximity_graph` is a good candidate for OneSkeletonGraph. + * \tparam FilteredEdgeRange must be a range for which std::begin and std::end return iterators on a + * `Flag_complex_edge_collapser::Filtered_edge`. */ - template - Flag_complex_edge_collapser(const OneSkeletonGraph& one_skeleton_graph) { - // Insert all edges - for (auto edge_it = edges(one_skeleton_graph); - edge_it.first != edge_it.second; ++edge_it.first) { - auto edge = *(edge_it.first); - Vertex_handle u = source(edge, one_skeleton_graph); - Vertex_handle v = target(edge, one_skeleton_graph); - f_edge_vector_.emplace_back(u, v, get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge)); - } - } + template + Flag_complex_edge_collapser(FilteredEdgeRange edges) + : f_edge_vector_(std::begin(edges), std::end(edges)) { } /** \brief Performs edge collapse in a increasing sequence of the filtration value. * diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 108f77e4..b5ad09c5 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -13,6 +13,7 @@ #define BOOST_TEST_MODULE "collapse" #include #include +#include #include #include @@ -49,7 +50,7 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F } std::cout << "COLLAPSE - keep edges: " << std::endl; - Flag_complex_edge_collapser edge_collapser(filtered_edges.begin(), filtered_edges.end()); + Flag_complex_edge_collapser edge_collapser(filtered_edges); Filtered_edge_list remaining_edges; edge_collapser.process_edges( [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { @@ -174,7 +175,15 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, threshold, Gudhi::Euclidean_distance()); - Flag_complex_edge_collapser edge_collapser(proximity_graph); + + Flag_complex_edge_collapser edge_collapser( + boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ + return std::make_tuple(source(edge, proximity_graph), + target(edge, proximity_graph), + get(Gudhi::edge_filtration_t(), proximity_graph, edge)); + }) + ); + Filtered_edge_list remaining_edges; edge_collapser.process_edges( [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { diff --git a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp index 88cd7b54..bd9c0152 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -15,6 +15,7 @@ #include #include +#include using Simplex_tree = Gudhi::Simplex_tree; using Filtration_value = Simplex_tree::Filtration_value; @@ -90,7 +91,13 @@ int main(int argc, char* argv[]) { }); // Now we will perform filtered edge collapse to sparsify the edge list edge_t. - Flag_complex_edge_collapser edge_collapser(proximity_graph); + Flag_complex_edge_collapser edge_collapser( + boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ + return std::make_tuple(source(edge, proximity_graph), + target(edge, proximity_graph), + get(Gudhi::edge_filtration_t(), proximity_graph, edge)); + }) + ); Simplex_tree stree; for (Vertex_handle vertex = 0; static_cast(vertex) < distances.size(); vertex++) { diff --git a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp index 69e83597..4e14d7a8 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -16,6 +16,7 @@ #include #include +#include #include // for std::pair #include @@ -77,7 +78,13 @@ int main(int argc, char* argv[]) { exit(-1); } - Flag_complex_edge_collapser edge_collapser(proximity_graph); + Flag_complex_edge_collapser edge_collapser( + boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ + return std::make_tuple(source(edge, proximity_graph), + target(edge, proximity_graph), + get(Gudhi::edge_filtration_t(), proximity_graph, edge)); + }) + ); Simplex_tree stree; for (Vertex_handle vertex = 0; static_cast(vertex) < point_vector.size(); vertex++) { -- cgit v1.2.3 From 945c7a6ccd23abd0c854777eebda762dea450490 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 26 Jun 2020 12:08:32 +0200 Subject: Free function, doc and basic example --- src/Collapse/doc/intro_edge_collapse.h | 6 ++-- .../example/edge_collapse_basic_example.cpp | 15 +++----- .../include/gudhi/Flag_complex_edge_collapser.h | 40 ++++++++++++++++++---- 3 files changed, 40 insertions(+), 21 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h index 2b272a9e..81edd79f 100644 --- a/src/Collapse/doc/intro_edge_collapse.h +++ b/src/Collapse/doc/intro_edge_collapse.h @@ -76,9 +76,9 @@ namespace collapse { * * \subsection edgecollapseexample Basic edge collapse * - * This example builds the `Flag_complex_edge_collapser` from a proximity graph represented as a list of - * `Flag_complex_edge_collapser::Filtered_edge`. - * Then it collapses edges and displays a new list of `Flag_complex_edge_collapser::Filtered_edge` (with less edges) + * This example calls `Gudhi::collapse::flag_complex_collapse_edges()` from a proximity graph represented as a list of + * `Filtered_edge`. + * Then it collapses edges and displays a new list of `Filtered_edge` (with less edges) * that will preserve the persistence homology computation. * * \include Collapse/edge_collapse_basic_example.cpp diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index 69ce329e..1b3dc1b5 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -2,13 +2,13 @@ #include #include +#include int main() { // Type definitions using Filtration_value = float; using Vertex_handle = short; - using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; - using Filtered_edge = Flag_complex_edge_collapser::Filtered_edge; + using Filtered_edge = std::tuple; using Filtered_edge_list = std::vector; // 1 2 @@ -25,16 +25,9 @@ int main() { {0, 2, 2.}, {1, 3, 2.}}; - Flag_complex_edge_collapser edge_collapser(graph); + auto remaining_edges = Gudhi::collapse::flag_complex_collapse_edges(graph); - Filtered_edge_list remaining_edges; - // Retrieve collapse edges from the output iterator - edge_collapser.process_edges( - [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { - remaining_edges.emplace_back(u, v, filtration); - }); - - for (Filtered_edge filtered_edge_from_collapse : remaining_edges) { + for (auto filtered_edge_from_collapse : remaining_edges) { std::cout << "fn[" << std::get<0>(filtered_edge_from_collapse) << ", " << std::get<1>(filtered_edge_from_collapse) << "] = " << std::get<2>(filtered_edge_from_collapse) << std::endl; } diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 9cd57d7e..981ec88d 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -12,11 +12,9 @@ #ifndef FLAG_COMPLEX_EDGE_COLLAPSER_H_ #define FLAG_COMPLEX_EDGE_COLLAPSER_H_ -#include #include #include -#include #include #include @@ -39,12 +37,11 @@ namespace Gudhi { namespace collapse { -/** +/** \private + * * \class Flag_complex_edge_collapser * \brief Flag complex sparse matrix data structure. * - * \ingroup collapse - * * \details * This class stores a Flag complex * in an Eigen sparse matrix. @@ -296,7 +293,7 @@ class Flag_complex_edge_collapser { * `Flag_complex_edge_collapser::Filtered_edge`. */ template - Flag_complex_edge_collapser(FilteredEdgeRange edges) + Flag_complex_edge_collapser(const FilteredEdgeRange& edges) : f_edge_vector_(std::begin(edges), std::end(edges)) { } /** \brief Performs edge collapse in a increasing sequence of the filtration value. @@ -310,7 +307,7 @@ class Flag_complex_edge_collapser { // Sort edges auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool { - return (get<2>(edge_a) < get<2>(edge_b)); + return (std::get<2>(edge_a) < std::get<2>(edge_b)); }; #ifdef GUDHI_USE_TBB @@ -342,6 +339,35 @@ class Flag_complex_edge_collapser { }; +/** \brief Constructs a Flag complex from edges as an input, collapse edges and returns remaining edges. + * + * \fn auto Gudhi::collapse::flag_complex_collapse_edges(FilteredEdgeRange const& edges) + * + * \tparam FilteredEdgeRange furnishes `std::begin` and `std::end` methods and returns an iterator on a + * FilteredEdge of type `std::tuple` + * + * \ingroup edge_collapse + * + */ +template auto flag_complex_collapse_edges(const FilteredEdgeRange& edges) { + auto first_edge_itr = std::begin(edges); + auto first_vertex = std::get<0>(*first_edge_itr); + auto first_filt = std::get<2>(*first_edge_itr); + using Vertex_handle = decltype(first_vertex); + using Filtration_value = decltype(first_filt); + using Edge_collapser = Flag_complex_edge_collapser; + std::vector remaining_edges; + if (first_edge_itr != std::end(edges)) { + Edge_collapser edge_collapser(edges); + edge_collapser.process_edges( + [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { + // insert the edge + remaining_edges.emplace_back(u, v, filtration); + }); + } + return remaining_edges; +} + } // namespace collapse } // namespace Gudhi -- cgit v1.2.3 From 230bbe960ef51496acae94451a269d8e1fd32817 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 1 Jul 2020 08:06:39 +0200 Subject: Code review: use of std::decay --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 981ec88d..860b7aa5 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -32,6 +32,7 @@ #include // for std::tie #include // for std::includes #include // for std::inserter +#include // for std::decay namespace Gudhi { @@ -351,10 +352,8 @@ class Flag_complex_edge_collapser { */ template auto flag_complex_collapse_edges(const FilteredEdgeRange& edges) { auto first_edge_itr = std::begin(edges); - auto first_vertex = std::get<0>(*first_edge_itr); - auto first_filt = std::get<2>(*first_edge_itr); - using Vertex_handle = decltype(first_vertex); - using Filtration_value = decltype(first_filt); + using Vertex_handle = std::decay_t(*first_edge_itr))>; + using Filtration_value = std::decay_t(*first_edge_itr))>; using Edge_collapser = Flag_complex_edge_collapser; std::vector remaining_edges; if (first_edge_itr != std::end(edges)) { -- cgit v1.2.3 From 589a086317070c8a873051a5ca45cc56815ff53e Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com> Date: Tue, 30 Jun 2020 23:09:17 -0700 Subject: Doc review: commit suggestion Co-authored-by: Marc Glisse --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 860b7aa5..e26f32f7 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -340,7 +340,7 @@ class Flag_complex_edge_collapser { }; -/** \brief Constructs a Flag complex from edges as an input, collapse edges and returns remaining edges. +/** \brief Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent homology and returns the remaining edges as a range. * * \fn auto Gudhi::collapse::flag_complex_collapse_edges(FilteredEdgeRange const& edges) * -- cgit v1.2.3 From 3bce2a71ab4a0fabb96fce56f32b605def0897a6 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com> Date: Tue, 30 Jun 2020 23:10:29 -0700 Subject: Doc review: commit suggestion Co-authored-by: Marc Glisse --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index e26f32f7..60d75211 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -345,7 +345,7 @@ class Flag_complex_edge_collapser { * \fn auto Gudhi::collapse::flag_complex_collapse_edges(FilteredEdgeRange const& edges) * * \tparam FilteredEdgeRange furnishes `std::begin` and `std::end` methods and returns an iterator on a - * FilteredEdge of type `std::tuple` + * FilteredEdge of type `std::tuple` where Vertex_handle is the index of a vertex. * * \ingroup edge_collapse * -- cgit v1.2.3 From d8c5a1b263b5c008b7f41dc7f1cd18e185cd92ea Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 1 Jul 2020 10:34:54 +0200 Subject: Doc review: Add some documentation for the free function --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 60d75211..07575b3b 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -340,13 +340,20 @@ class Flag_complex_edge_collapser { }; -/** \brief Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent homology and returns the remaining edges as a range. +/** \brief Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent + * homology and returns the remaining edges as a range. * * \fn auto Gudhi::collapse::flag_complex_collapse_edges(FilteredEdgeRange const& edges) + * + * \param[in] edges Range of Filtered edges.There is no need the range to be sorted, as it will be performed. * * \tparam FilteredEdgeRange furnishes `std::begin` and `std::end` methods and returns an iterator on a - * FilteredEdge of type `std::tuple` where Vertex_handle is the index of a vertex. + * FilteredEdge of type `std::tuple` where `Vertex_handle` is the type + * of a vertex index and `Filtration_value` is the type of an edge filtration value. * + * \return Remaining edges after collapse of type + * `std::vector>`. + * * \ingroup edge_collapse * */ -- cgit v1.2.3 From cf5deb9997ee0da5253d40cc2d2382fa2ca758ec Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 1 Jul 2020 10:37:14 +0200 Subject: Remove Flag_complex_edge_collapser documentation. Only use the free function one --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 1 - 1 file changed, 1 deletion(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 07575b3b..01be8f03 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -40,7 +40,6 @@ namespace collapse { /** \private * - * \class Flag_complex_edge_collapser * \brief Flag complex sparse matrix data structure. * * \details -- cgit v1.2.3 From f7876ea08e810c57f90e0233fffbd91d57f6d037 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 1 Jul 2020 22:09:58 +0200 Subject: doc review: fix some errors --- biblio/bibliography.bib | 28 +++++++++++++--------- .../include/gudhi/Flag_complex_edge_collapser.h | 6 ++--- src/common/doc/main_page.md | 2 +- 3 files changed, 20 insertions(+), 16 deletions(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 4e716986..ad8ce50a 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1279,15 +1279,21 @@ year = "2011" bibsource = {dblp computer science bibliography, https://dblp.org} } -@unpublished{edgecollapsesocg2020, - title = {{Edge Collapse and Persistence of Flag Complexes}}, - author = {Boissonnat, Jean-Daniel and Pritam, Siddharth}, - url = {https://hal.inria.fr/hal-02395227}, - note = {working paper or preprint}, - year = {2019}, - month = Dec, - keywords = {Persistent homology ; Strong Collapse ; Computational geometry ; Topological Data Analysis ; Computational Topology}, - pdf = {https://hal.inria.fr/hal-02395227/file/socg2020_paper_152.pdf}, - hal_id = {hal-02395227}, - hal_version = {v1}, +@InProceedings{edgecollapsesocg2020, + author = {Jean-Daniel Boissonnat and Siddharth Pritam}, + title = {{Edge Collapse and Persistence of Flag Complexes}}, + booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, + pages = {19:1--19:15}, + series = {Leibniz International Proceedings in Informatics (LIPIcs)}, + ISBN = {978-3-95977-143-6}, + ISSN = {1868-8969}, + year = {2020}, + volume = {164}, + editor = {Sergio Cabello and Danny Z. Chen}, + publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, + address = {Dagstuhl, Germany}, + URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12177}, + URN = {urn:nbn:de:0030-drops-121777}, + doi = {10.4230/LIPIcs.SoCG.2020.19}, + annote = {Keywords: Computational Topology, Topological Data Analysis, Edge Collapse, Simple Collapse, Persistent homology} } diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 01be8f03..d1a47b75 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -342,16 +342,14 @@ class Flag_complex_edge_collapser { /** \brief Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent * homology and returns the remaining edges as a range. * - * \fn auto Gudhi::collapse::flag_complex_collapse_edges(FilteredEdgeRange const& edges) - * * \param[in] edges Range of Filtered edges.There is no need the range to be sorted, as it will be performed. * * \tparam FilteredEdgeRange furnishes `std::begin` and `std::end` methods and returns an iterator on a * FilteredEdge of type `std::tuple` where `Vertex_handle` is the type * of a vertex index and `Filtration_value` is the type of an edge filtration value. * - * \return Remaining edges after collapse of type - * `std::vector>`. + * \return Remaining edges after collapse as a range of + * ``. * * \ingroup edge_collapse * diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index 740a3e52..e19af537 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -235,7 +235,7 @@ Author: Siddharth Pritam
- Introduced in: GUDHI 2.4.0
+ Introduced in: GUDHI 3.3.0
Copyright: MIT
Requires: \ref eigen -- cgit v1.2.3 From eedb34f25d76cb3dc7ccb6b59a60217a26eedfcd Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 1 Jul 2020 22:18:54 +0200 Subject: Bad fix --- src/Collapse/include/gudhi/Flag_complex_edge_collapser.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Collapse/include/gudhi/Flag_complex_edge_collapser.h') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index d1a47b75..b6b7f7c1 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -349,7 +349,7 @@ class Flag_complex_edge_collapser { * of a vertex index and `Filtration_value` is the type of an edge filtration value. * * \return Remaining edges after collapse as a range of - * ``. + * `std::tuple`. * * \ingroup edge_collapse * -- cgit v1.2.3