diff options
Diffstat (limited to 'src/Collapse')
6 files changed, 74 insertions, 85 deletions
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<Vertex_handle, Filtration_value>; using Filtered_edge = Flag_complex_edge_collapser::Filtered_edge; using Filtered_edge_list = std::vector<Filtered_edge>; - 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<Vertex_handle, Vertex_handle> 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<Vertex_handle>& 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_interval> 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<Vertex_handle, Vertex_handle>; 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<Edge, Filtration_value>; + using Filtered_edge = std::tuple<Vertex_handle, Vertex_handle, Filtration_value>; 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<Filtered_edge> 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<Edge_index> three_clique_indices(Edge_index crit) { std::set<Edge_index> 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<Edge_index> 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<typename FilteredEdgeOutput> 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<Vertex_handle, Vertex_handle> 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<Filtered_edge, 6> 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<Filtered_edge, 6> 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<Vertex_handle, Vertex_handle> 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<Filtration_value>::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<Vertex_handle> 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<Vertex_handle>& 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); |