From 6e6b8c78350d1d8352242512ce537327934276cb Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 3 Apr 2020 09:49:54 +0200 Subject: Add doc and start tests --- src/Collapse/test/collapse_unit_test.cpp | 94 ++++++++++++++++++++++++++++++++ 1 file changed, 94 insertions(+) create mode 100644 src/Collapse/test/collapse_unit_test.cpp (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp new file mode 100644 index 00000000..c2f08e57 --- /dev/null +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -0,0 +1,94 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2020 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#include +#include +#include +#include +#include // std::pair, std::make_pair +#include // float comparison +#include +#include // greater +#include // std::tie + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "collapse" +#include +#include + +// ^ +// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. +#include "gudhi/FlagComplexSpMatrix.h" +#include "gudhi/Rips_edge_list.h" + +using namespace Gudhi; + +// Types definition +using Vector_of_points = std::vector>; + +using Simplex_tree = Gudhi::Simplex_tree; +using Filtration_value = double; +using Rips_complex = Gudhi::rips_complex::Rips_complex; +using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; +using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; +using Distance_matrix = std::vector>; + + +BOOST_AUTO_TEST_CASE(collapse) { + typedef size_t Vertex_handle; + typedef std::vector> Filtered_sorted_edge_list; + + std::size_t number_of_points; + std::string off_file_points; + std::string filediag; + int dim_max; + int p; + double min_persistence; + + Map map_empty; + + Distance_matrix sparse_distances; + + + Vector_of_points point_vector {{0., 0.},{0., 1.},{1., 0.},{1., 1.}}; + + int dimension = point_vector[0].dimension(); + number_of_points = point_vector.size(); + std::cout << "Successfully read " << number_of_points << " point_vector.\n"; + std::cout << "Ambient dimension is " << dimension << ".\n"; + + std::cout << "Point Set Generated." << std::endl; + + double threshold = 1.; + Filtered_sorted_edge_list edge_t; + std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; + + Rips_edge_list Rips_edge_list_from_file(point_vector, threshold, Gudhi::Euclidean_distance()); + Rips_edge_list_from_file.create_edges(edge_t); + + std::cout << "Sorted edge list computed" << std::endl; + std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl; + + if (edge_t.size() <= 0) { + std::cerr << "Total number of egdes are zero." << std::endl; + exit(-1); + } + + // Now we will perform filtered edge collapse to sparsify the edge list edge_t. + std::cout << "Filtered edge collapse begins" << std::endl; + FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t); + std::cout << "Matrix instansiated" << std::endl; + Filtered_sorted_edge_list collapse_edges; + collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); + +} + + -- cgit v1.2.3 From 9a42ecf2f7134ff46cabd7775eea1cbf62fdef63 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 3 Apr 2020 18:57:05 +0200 Subject: First test version --- src/Collapse/test/collapse_unit_test.cpp | 57 ++++++++++++++++---------------- 1 file changed, 29 insertions(+), 28 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index c2f08e57..508d5aa9 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -27,19 +27,22 @@ // /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. #include "gudhi/FlagComplexSpMatrix.h" #include "gudhi/Rips_edge_list.h" +#include "gudhi/graph_simplicial_complex.h" +#include "gudhi/distance_functions.h" using namespace Gudhi; // Types definition using Vector_of_points = std::vector>; -using Simplex_tree = Gudhi::Simplex_tree; +//using Simplex_tree = Gudhi::Simplex_tree; using Filtration_value = double; -using Rips_complex = Gudhi::rips_complex::Rips_complex; -using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; +using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; +/*using Rips_complex = Gudhi::rips_complex::Rips_complex; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; -using Distance_matrix = std::vector>; +*/ +using Distance_matrix = std::vector>; BOOST_AUTO_TEST_CASE(collapse) { @@ -49,9 +52,6 @@ BOOST_AUTO_TEST_CASE(collapse) { std::size_t number_of_points; std::string off_file_points; std::string filediag; - int dim_max; - int p; - double min_persistence; Map map_empty; @@ -60,34 +60,35 @@ BOOST_AUTO_TEST_CASE(collapse) { Vector_of_points point_vector {{0., 0.},{0., 1.},{1., 0.},{1., 1.}}; - int dimension = point_vector[0].dimension(); + int dimension = point_vector[0].size(); number_of_points = point_vector.size(); std::cout << "Successfully read " << number_of_points << " point_vector.\n"; std::cout << "Ambient dimension is " << dimension << ".\n"; std::cout << "Point Set Generated." << std::endl; - double threshold = 1.; - Filtered_sorted_edge_list edge_t; - std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; - - Rips_edge_list Rips_edge_list_from_file(point_vector, threshold, Gudhi::Euclidean_distance()); - Rips_edge_list_from_file.create_edges(edge_t); - - std::cout << "Sorted edge list computed" << std::endl; - std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl; - - if (edge_t.size() <= 0) { - std::cerr << "Total number of egdes are zero." << std::endl; - exit(-1); + for (double threshold = 1. ; threshold <= 2.; threshold +=1.) { + Filtered_sorted_edge_list edge_t; + std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; + + Rips_edge_list Rips_edge_list_from_file(point_vector, threshold, Gudhi::Euclidean_distance()); + Rips_edge_list_from_file.create_edges(edge_t); + + std::cout << "Sorted edge list computed" << std::endl; + std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl; + + if (edge_t.size() <= 0) { + std::cerr << "Total number of egdes are zero." << std::endl; + exit(-1); + } + + // Now we will perform filtered edge collapse to sparsify the edge list edge_t. + std::cout << "Filtered edge collapse begins" << std::endl; + FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t); + std::cout << "Matrix instansiated" << std::endl; + Filtered_sorted_edge_list collapse_edges; + collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); } - - // Now we will perform filtered edge collapse to sparsify the edge list edge_t. - std::cout << "Filtered edge collapse begins" << std::endl; - FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t); - std::cout << "Matrix instansiated" << std::endl; - Filtered_sorted_edge_list collapse_edges; - collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); } -- cgit v1.2.3 From c23490a73bca4208af68f741d1e3e0a505f22411 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Sat, 4 Apr 2020 10:11:13 +0200 Subject: Test basic examples --- src/Collapse/test/collapse_unit_test.cpp | 149 +++++++++++++++++++++---------- 1 file changed, 104 insertions(+), 45 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 508d5aa9..b4bc0fc0 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -30,66 +30,125 @@ #include "gudhi/graph_simplicial_complex.h" #include "gudhi/distance_functions.h" -using namespace Gudhi; +//using namespace Gudhi; // Types definition -using Vector_of_points = std::vector>; +//using Vector_of_points = std::vector>; //using Simplex_tree = Gudhi::Simplex_tree; -using Filtration_value = double; -using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; +//using Filtration_value = double; +//using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; /*using Rips_complex = Gudhi::rips_complex::Rips_complex; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; */ -using Distance_matrix = std::vector>; - - -BOOST_AUTO_TEST_CASE(collapse) { - typedef size_t Vertex_handle; - typedef std::vector> Filtered_sorted_edge_list; - - std::size_t number_of_points; - std::string off_file_points; - std::string filediag; +//using Distance_matrix = std::vector>; - Map map_empty; - - Distance_matrix sparse_distances; +using Filtration_value = double; +using Vertex_handle = size_t; +using Filtered_edge = std::tuple; +using Filtered_sorted_edge_list = std::vector>; + +bool find_edge_in_list(const Filtered_edge& edge, const Filtered_sorted_edge_list& edge_list) { + for (auto edge_from_list : edge_list) { + if (edge_from_list == edge) + return true; + } + return false; +} +void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filtered_sorted_edge_list& removed_edges) { + std::cout << "BEFORE COLLAPSE - Total number of edges: " << edges.size() << std::endl; + BOOST_CHECK(edges.size() > 0); + for (auto edge : edges) { + std::cout << "f[" << std::get<1>(edge) << ", " << std::get<2>(edge) << "] = " << std::get<0>(edge) << std::endl; + } - Vector_of_points point_vector {{0., 0.},{0., 1.},{1., 0.},{1., 1.}}; + FlagComplexSpMatrix flag_complex_sparse_matrix(5, edges); + auto collapse_edges = flag_complex_sparse_matrix.filtered_edge_collapse(); + std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; + BOOST_CHECK(collapse_edges.size() <= edges.size()); + for (auto edge_from_collapse : collapse_edges) { + std::cout << "f[" << std::get<1>(edge_from_collapse) << ", " << std::get<2>(edge_from_collapse) << "] = " + << std::get<0>(edge_from_collapse) << std::endl; + // Check each edge from collapse is in the input + BOOST_CHECK(find_edge_in_list(edge_from_collapse, edges)); + } - int dimension = point_vector[0].size(); - number_of_points = point_vector.size(); - std::cout << "Successfully read " << number_of_points << " point_vector.\n"; - std::cout << "Ambient dimension is " << dimension << ".\n"; + for (auto removed_edge : removed_edges) { + std::cout << "f[" << std::get<1>(removed_edge) << ", " << std::get<2>(removed_edge) << "] = " + << std::get<0>(removed_edge) << std::endl; + // Check each removed edge from collapse is in the input + BOOST_CHECK(!find_edge_in_list(removed_edge, collapse_edges)); + } - std::cout << "Point Set Generated." << std::endl; +} - for (double threshold = 1. ; threshold <= 2.; threshold +=1.) { - Filtered_sorted_edge_list edge_t; - std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; - - Rips_edge_list Rips_edge_list_from_file(point_vector, threshold, Gudhi::Euclidean_distance()); - Rips_edge_list_from_file.create_edges(edge_t); - - std::cout << "Sorted edge list computed" << std::endl; - std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl; - - if (edge_t.size() <= 0) { - std::cerr << "Total number of egdes are zero." << std::endl; - exit(-1); - } +BOOST_AUTO_TEST_CASE(collapse) { + /* + 1 2 + o---o + | | + | | + | | + o---o + 0 3 + */ + Filtered_sorted_edge_list edges {{1., 0, 1}, {1., 1, 2}, {1., 2, 3}, {1., 3, 0}}; + trace_and_check_collapse(edges, {}); - // Now we will perform filtered edge collapse to sparsify the edge list edge_t. - std::cout << "Filtered edge collapse begins" << std::endl; - FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t); - std::cout << "Matrix instansiated" << std::endl; - Filtered_sorted_edge_list collapse_edges; - collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); - } - + /* + 1 2 + o---o + |\ /| + | x | + |/ \| + o---o + 0 3 + */ + edges.push_back({2., 0, 2}); + edges.push_back({2., 1, 3}); + trace_and_check_collapse(edges, {{2., 1, 3}}); + + /* + 1 2 4 + o---o---o + |\ /| | + | x | | + |/ \| | + o---o---o + 0 3 5 + */ + edges.push_back({3., 2, 4}); + edges.push_back({3., 4, 5}); + edges.push_back({3., 5, 3}); + trace_and_check_collapse(edges, {{2., 1, 3}}); + + /* + 1 2 4 + o---o---o + |\ /|\ /| + | x | x | + |/ \|/ \| + o---o---o + 0 3 5 + */ + edges.push_back({4., 2, 5}); + edges.push_back({4., 4, 3}); + trace_and_check_collapse(edges, {{2., 1, 3}, {4., 2, 5}, {4., 4, 3}}); + + /* + 1 2 4 + o---o---o + |\ /|\ /| + | x | x | + [0,4] and [1,5] + |/ \|/ \| + o---o---o + 0 3 5 + */ + edges.push_back({5., 1, 5}); + edges.push_back({5., 0, 4}); + trace_and_check_collapse(edges, {{2., 1, 3}, {4., 2, 5}, {4., 4, 3}, {5., 0, 4}}); } -- cgit v1.2.3 From a129158212bf63d04c341711d194414ad135baf4 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Mon, 6 Apr 2020 08:37:48 +0200 Subject: Some cleanup --- src/Collapse/include/gudhi/FlagComplexSpMatrix.h | 89 +++++++++++------------- src/Collapse/test/collapse_unit_test.cpp | 1 + 2 files changed, 43 insertions(+), 47 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/FlagComplexSpMatrix.h b/src/Collapse/include/gudhi/FlagComplexSpMatrix.h index ea43b986..32a6ad5c 100644 --- a/src/Collapse/include/gudhi/FlagComplexSpMatrix.h +++ b/src/Collapse/include/gudhi/FlagComplexSpMatrix.h @@ -148,7 +148,7 @@ class FlagComplexSpMatrix { EdgeFiltQueue filteredEgdeIter; // Vector of filtered edges, for edge-collapse, the indices of the edges are the row-indices. - EdgeFiltVector fEgdeVector; + EdgeFiltVector f_edge_vector; // List of non-dominated edges, the indices of the edges are the vertex lables!!. Filtered_sorted_edge_list criticalCoreEdges; @@ -212,14 +212,13 @@ class FlagComplexSpMatrix { std::set three_clique_indices(std::size_t crit) { std::set edge_indices; - EdgeFilt fe = fEgdeVector.at(crit); - Edge e = std::get<0>(fe); + Edge e = std::get<0>(f_edge_vector[crit]); Vertex u = std::get<0>(e); Vertex v = std::get<1>(e); #ifdef DEBUG_TRACES std::cout << "The current critical edge to re-check criticality with filt value is : f {" << u << "," << v - << "} = " << std::get<1>(fe) << std::endl; + << "} = " << std::get<1>(f_edge_vector[crit]) << std::endl; #endif // DEBUG_TRACES auto rw_u = vertexToRow[u]; auto rw_v = vertexToRow[v]; @@ -249,8 +248,7 @@ class FlagComplexSpMatrix { std::set effectedIndcs = three_clique_indices(indx); if (effectedIndcs.size() > 0) { for (auto idx = indx - 1; idx > 0; idx--) { - EdgeFilt fec = fEgdeVector.at(idx); - Edge e = std::get<0>(fec); + Edge e = std::get<0>(f_edge_vector[idx]); Vertex u = std::get<0>(e); Vertex v = std::get<1>(e); // If idx is not critical so it should be proceses, otherwise it stays in the graph // prev @@ -285,45 +283,6 @@ class FlagComplexSpMatrix { u_set_dominated_redges.clear(); } - void critical_core_edges() { - std::size_t totEdges = fEgdeVector.size(); - - std::size_t endIdx = 0; - - u_set_removed_redges.clear(); - u_set_dominated_redges.clear(); - critical_edge_indicator.clear(); - - while (endIdx < totEdges) { - EdgeFilt fec = fEgdeVector.at(endIdx); - - // Inserts the edge in the sparse matrix to update the graph (G_i) - insert_new_edges(std::get<0>(std::get<0>(fec)), std::get<1>(std::get<0>(fec)), std::get<1>(fec)); - - Edge e = std::get<0>(fec); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); - edge_to_index_map.emplace(std::minmax(u, v), endIdx); - critical_edge_indicator.push_back(false); - dominated_edge_indicator.push_back(false); - - if (not check_edge_domination(e)) { - critical_edge_indicator.at(endIdx) = true; - dominated_edge_indicator.at(endIdx) = false; - criticalCoreEdges.push_back({std::get<1>(fec), u, v}); - if (endIdx > 1) set_edge_critical(endIdx, std::get<1>(fec)); - - } else - dominated_edge_indicator.at(endIdx) = true; - endIdx++; - } - -#ifdef DEBUG_TRACES - std::cout << "The total number of critical edges is: " << criticalCoreEdges.size() << std::endl; - std::cout << "The total number of non-critical edges is: " << totEdges - criticalCoreEdges.size() << std::endl; -#endif // DEBUG_TRACES - } - // Returns list of non-zero columns of the particular indx. doubleVector closed_neighbours_row_index(double indx) { @@ -381,14 +340,50 @@ class FlagComplexSpMatrix { sparseRowAdjMatrix = sparseRowMatrix(num_vertices, num_vertices); for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { - fEgdeVector.push_back( + f_edge_vector.push_back( {{std::get<1>(edge_t.at(bgn_idx)), std::get<2>(edge_t.at(bgn_idx))}, std::get<0>(edge_t.at(bgn_idx))}); } } // Performs edge collapse in a decreasing sequence of the filtration value. Filtered_sorted_edge_list filtered_edge_collapse() { - critical_core_edges(); + std::size_t totEdges = f_edge_vector.size(); + + std::size_t endIdx = 0; + + u_set_removed_redges.clear(); + u_set_dominated_redges.clear(); + critical_edge_indicator.clear(); + + while (endIdx < totEdges) { + EdgeFilt fec = f_edge_vector[endIdx]; + Edge e = std::get<0>(fec); + Vertex u = std::get<0>(e); + Vertex v = std::get<1>(e); + double filt = std::get<1>(fec); + + // Inserts the edge in the sparse matrix to update the graph (G_i) + insert_new_edges(u, v, filt); + + edge_to_index_map.emplace(std::minmax(u, v), endIdx); + critical_edge_indicator.push_back(false); + dominated_edge_indicator.push_back(false); + + if (not check_edge_domination(e)) { + critical_edge_indicator.at(endIdx) = true; + dominated_edge_indicator.at(endIdx) = false; + criticalCoreEdges.push_back({filt, u, v}); + if (endIdx > 1) + set_edge_critical(endIdx, filt); + } else + dominated_edge_indicator.at(endIdx) = true; + endIdx++; + } + +#ifdef DEBUG_TRACES + std::cout << "The total number of critical edges is: " << criticalCoreEdges.size() << std::endl; + std::cout << "The total number of non-critical edges is: " << totEdges - criticalCoreEdges.size() << std::endl; +#endif // DEBUG_TRACES edgeCollapsed = true; return criticalCoreEdges; } diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index b4bc0fc0..427c315e 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -75,6 +75,7 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt BOOST_CHECK(find_edge_in_list(edge_from_collapse, edges)); } + std::cout << "CHECK COLLAPSE - Total number of removed edges: " << removed_edges.size() << std::endl; for (auto removed_edge : removed_edges) { std::cout << "f[" << std::get<1>(removed_edge) << ", " << std::get<2>(removed_edge) << "] = " << std::get<0>(removed_edge) << std::endl; -- cgit v1.2.3 From 178a04c446400a501a7c40d8b6bcfadc542ce6bc Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Mon, 6 Apr 2020 08:43:07 +0200 Subject: Some rename --- src/Collapse/include/gudhi/FlagComplexSpMatrix.h | 434 --------------------- .../include/gudhi/Flag_complex_sparse_matrix.h | 432 ++++++++++++++++++++ src/Collapse/test/collapse_unit_test.cpp | 4 +- ...tance_matrix_edge_collapse_rips_persistence.cpp | 4 +- .../point_cloud_edge_collapse_rips_persistence.cpp | 4 +- 5 files changed, 438 insertions(+), 440 deletions(-) delete mode 100644 src/Collapse/include/gudhi/FlagComplexSpMatrix.h create mode 100644 src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/FlagComplexSpMatrix.h b/src/Collapse/include/gudhi/FlagComplexSpMatrix.h deleted file mode 100644 index 32a6ad5c..00000000 --- a/src/Collapse/include/gudhi/FlagComplexSpMatrix.h +++ /dev/null @@ -1,434 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siddharth Pritam - * - * Copyright (C) 2018 INRIA Sophia Antipolis (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - -*/ -#pragma once - -#include -#include -// #include - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include -#include - -#include - -typedef std::size_t Vertex; -using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first - // element being the smaller i.e {2,3} not {3,2}. However this is at the level - // of row indices on actual vertex lables -using EdgeFilt = std::pair; -using edge_list = std::vector; - -using MapVertexToIndex = std::unordered_map; -using Map = std::unordered_map; - -using sparseRowMatrix = Eigen::SparseMatrix; -using rowInnerIterator = sparseRowMatrix::InnerIterator; - -using doubleVector = std::vector; -using vertexVector = std::vector; -using boolVector = std::vector; - -using doubleQueue = std::queue; - -using EdgeFiltQueue = std::queue; -using EdgeFiltVector = std::vector; - -typedef std::vector> Filtered_sorted_edge_list; -typedef std::unordered_map> u_edge_map; -typedef std::unordered_map> u_edge_to_idx_map; - -//! Class SparseMsMatrix -/*! - The class for storing the Vertices v/s MaxSimplices Sparse Matrix and performing collapses operations using the N^2() - Algorithm. -*/ -class FlagComplexSpMatrix { - private: - std::unordered_map rowToVertex; - - // Vertices strored as an unordered_set - std::unordered_set vertices; - - // Unordered set of removed edges. (to enforce removal from the matrix) - std::unordered_set> u_set_removed_redges; - - // Unordered set of dominated edges. (to inforce removal from the matrix) - std::unordered_set> u_set_dominated_redges; - - // Map from egde to its index - u_edge_to_idx_map edge_to_index_map; - // Boolean vector to indicate if the index is critical or not. - boolVector critical_edge_indicator; // critical indicator - - // Boolean vector to indicate if the index is critical or not. - boolVector dominated_edge_indicator; // domination indicator - - //! Stores the Map between verticesrowToVertex and row indices rowToVertex -> row-index. - /*! - \code - MapVertexToIndex = std::unordered_map - \endcode - So, if the original simplex tree had vertices 0,1,4,5
- rowToVertex would store :
- \verbatim - Values = | 0 | 1 | 4 | 5 | - Indices = 0 1 2 3 - \endverbatim - And vertexToRow would be a map like the following :
- \verbatim - 0 -> 0 - 1 -> 1 - 4 -> 2 - 5 -> 3 - \endverbatim - */ - MapVertexToIndex vertexToRow; - - //! Stores the Sparse matrix of double values representing the Original Simplicial Complex. - /*! - \code - sparseRowMatrix = Eigen::SparseMatrix ; - \endcode - ; - */ - - sparseRowMatrix* sparse_colpsd_adj_Matrix; // Stores the collapsed sparse matrix representaion. - sparseRowMatrix sparseRowAdjMatrix; // This is row-major version of the same sparse-matrix, to facilitate easy access - // to elements when traversing the matrix row-wise. - - //! Stores true for dominated rows and false for undominated rows. - /*! - Initialised to a vector of length equal to the value of the variable rows with all false values. - Subsequent removal of dominated vertices is reflected by concerned entries changing to true in this vector. - */ - boolVector vertDomnIndicator; //(domination indicator) - - boolVector contractionIndicator; //(contraction indicator) - - //! Stores the indices of the rows to-be checked for domination in the current iteration. - /*! - Initialised with all rows for the first iteration. - Subsequently once a dominated row is found, its non-dominated neighbhour indices are inserted. - */ - // doubleQueue rowIterator; - - doubleQueue rowIterator; - - // Queue of filtered edges, for edge-collapse, the indices of the edges are the row-indices. - EdgeFiltQueue filteredEgdeIter; - - // Vector of filtered edges, for edge-collapse, the indices of the edges are the row-indices. - EdgeFiltVector f_edge_vector; - - // List of non-dominated edges, the indices of the edges are the vertex lables!!. - Filtered_sorted_edge_list criticalCoreEdges; - // Stores the indices from the sorted filtered edge vector. - // std::set recurCriticalCoreIndcs; - - //! Stores the number of vertices in the original Simplicial Complex. - /*! - This stores the count of vertices (which is also the number of rows in the Matrix). - */ - std::size_t rows; - - std::size_t numOneSimplices; - - bool edgeCollapsed; - - // Edge e is the actual edge (u,v). Not the row ids in the matrixs - bool check_edge_domination(Edge e) - { - auto u = std::get<0>(e); - auto v = std::get<1>(e); - - auto rw_u = vertexToRow[u]; - auto rw_v = vertexToRow[v]; - auto rw_e = std::make_pair(rw_u, rw_v); -#ifdef DEBUG_TRACES - std::cout << "The edge {" << u << ", " << v << "} is going for domination check." << std::endl; -#endif // DEBUG_TRACES - auto commonNeighbours = closed_common_neighbours_row_index(rw_e); -#ifdef DEBUG_TRACES - std::cout << "And its common neighbours are." << std::endl; - for (doubleVector::iterator it = commonNeighbours.begin(); it!=commonNeighbours.end(); it++) { - std::cout << rowToVertex[*it] << ", " ; - } - std::cout<< std::endl; -#endif // DEBUG_TRACES - if (commonNeighbours.size() > 2) { - if (commonNeighbours.size() == 3) - return true; - else - for (doubleVector::iterator it = commonNeighbours.begin(); it != commonNeighbours.end(); it++) { - auto rw_c = *it; // Typecasting - if (rw_c != rw_u and rw_c != rw_v) { - auto neighbours_c = closed_neighbours_row_index(rw_c); - // If neighbours_c contains the common neighbours. - if (std::includes(neighbours_c.begin(), neighbours_c.end(), commonNeighbours.begin(), - commonNeighbours.end())) - return true; - } - } - } - return false; - } - - // The edge should be sorted by the indices and indices are original - bool check_domination_indicator(Edge e) - { - return dominated_edge_indicator[edge_to_index_map[e]]; - } - - std::set three_clique_indices(std::size_t crit) { - std::set edge_indices; - - Edge e = std::get<0>(f_edge_vector[crit]); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); - -#ifdef DEBUG_TRACES - std::cout << "The current critical edge to re-check criticality with filt value is : f {" << u << "," << v - << "} = " << std::get<1>(f_edge_vector[crit]) << std::endl; -#endif // DEBUG_TRACES - auto rw_u = vertexToRow[u]; - auto rw_v = vertexToRow[v]; - auto rw_critical_edge = std::make_pair(rw_u, rw_v); - - doubleVector commonNeighbours = closed_common_neighbours_row_index(rw_critical_edge); - - if (commonNeighbours.size() > 2) { - for (doubleVector::iterator it = commonNeighbours.begin(); it != commonNeighbours.end(); it++) { - auto rw_c = *it; - if (rw_c != rw_u and rw_c != rw_v) { - auto e_with_new_nbhr_v = std::minmax(u, rowToVertex[rw_c]); - auto e_with_new_nbhr_u = std::minmax(v, rowToVertex[rw_c]); - edge_indices.emplace(edge_to_index_map[e_with_new_nbhr_v]); - edge_indices.emplace(edge_to_index_map[e_with_new_nbhr_u]); - } - } - } - return edge_indices; - } - - void set_edge_critical(std::size_t indx, double filt) { -#ifdef DEBUG_TRACES - std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << - std::endl; -#endif // DEBUG_TRACES - std::set effectedIndcs = three_clique_indices(indx); - if (effectedIndcs.size() > 0) { - for (auto idx = indx - 1; idx > 0; idx--) { - Edge e = std::get<0>(f_edge_vector[idx]); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); - // If idx is not critical so it should be proceses, otherwise it stays in the graph // prev - // code : recurCriticalCoreIndcs.find(idx) == recurCriticalCoreIndcs.end() - if (not critical_edge_indicator.at(idx)) { - // If idx is affected - if (effectedIndcs.find(idx) != effectedIndcs.end()) { - if (not check_edge_domination(e)) { -#ifdef DEBUG_TRACES - std::cout << "The curent index became critical " << idx << std::endl; -#endif // DEBUG_TRACES - critical_edge_indicator.at(idx) = true; - criticalCoreEdges.push_back({filt, u, v}); - std::set inner_effected_indcs = three_clique_indices(idx); - for (auto inr_idx = inner_effected_indcs.rbegin(); inr_idx != inner_effected_indcs.rend(); inr_idx++) { - if (*inr_idx < idx) effectedIndcs.emplace(*inr_idx); - } - inner_effected_indcs.clear(); -#ifdef DEBUG_TRACES - std::cout << "The following edge is critical with filt value: {" << std::get<0>(e) << "," << - std::get<1>(e) << "}; " << filt << std::endl; -#endif // DEBUG_TRACES - } else - u_set_dominated_redges.emplace(std::minmax(vertexToRow[u], vertexToRow[v])); - } else - // Idx is not affected hence dominated. - u_set_dominated_redges.emplace(std::minmax(vertexToRow[u], vertexToRow[v])); - } - } - } - effectedIndcs.clear(); - u_set_dominated_redges.clear(); - } - - // Returns list of non-zero columns of the particular indx. - doubleVector closed_neighbours_row_index(double indx) - { - doubleVector nonZeroIndices; - Vertex u = indx; - Vertex v; - // std::cout << "The neighbours of the vertex: " << rowToVertex[u] << " are. " << std::endl; - if (not vertDomnIndicator[indx]) { - // Iterate over the non-zero columns - for (rowInnerIterator it(sparseRowAdjMatrix, indx); it; ++it) { - v = it.index(); - // If the vertex v is not dominated and the edge {u,v} is still in the matrix - if (not vertDomnIndicator[v] and u_set_removed_redges.find(std::minmax(u, v)) == u_set_removed_redges.end() and - u_set_dominated_redges.find(std::minmax(u, v)) == u_set_dominated_redges.end()) { - // inner index, here it is equal to it.columns() - nonZeroIndices.push_back(it.index()); - // std::cout << rowToVertex[it.index()] << ", " ; - } - } - // std::cout << std::endl; - } - return nonZeroIndices; - } - - doubleVector closed_common_neighbours_row_index(Edge e) // Returns the list of closed neighbours of the edge :{u,v}. - { - doubleVector common; - doubleVector nonZeroIndices_u; - doubleVector nonZeroIndices_v; - double u = std::get<0>(e); - double v = std::get<1>(e); - - nonZeroIndices_u = closed_neighbours_row_index(u); - nonZeroIndices_v = closed_neighbours_row_index(v); - std::set_intersection(nonZeroIndices_u.begin(), nonZeroIndices_u.end(), nonZeroIndices_v.begin(), - nonZeroIndices_v.end(), std::inserter(common, common.begin())); - - return common; - } - - public: - //! Main Constructor - /*! - Argument is an instance of Filtered_sorted_edge_list.
- This is THE function that initialises all data members to appropriate values.
- rowToVertex, vertexToRow, rows, cols, sparseRowAdjMatrix are initialised here. - vertDomnIndicator ,rowIterator are initialised by init() function which is - called at the begining of this.
- */ - FlagComplexSpMatrix(const size_t& num_vertices, const Filtered_sorted_edge_list& edge_t) - : rows(0), - numOneSimplices(0), - edgeCollapsed(false) { - // Initializing sparseRowAdjMatrix, This is a row-major sparse matrix. - sparseRowAdjMatrix = sparseRowMatrix(num_vertices, num_vertices); - - for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { - f_edge_vector.push_back( - {{std::get<1>(edge_t.at(bgn_idx)), std::get<2>(edge_t.at(bgn_idx))}, std::get<0>(edge_t.at(bgn_idx))}); - } - } - - // Performs edge collapse in a decreasing sequence of the filtration value. - Filtered_sorted_edge_list filtered_edge_collapse() { - std::size_t totEdges = f_edge_vector.size(); - - std::size_t endIdx = 0; - - u_set_removed_redges.clear(); - u_set_dominated_redges.clear(); - critical_edge_indicator.clear(); - - while (endIdx < totEdges) { - EdgeFilt fec = f_edge_vector[endIdx]; - Edge e = std::get<0>(fec); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); - double filt = std::get<1>(fec); - - // Inserts the edge in the sparse matrix to update the graph (G_i) - insert_new_edges(u, v, filt); - - edge_to_index_map.emplace(std::minmax(u, v), endIdx); - critical_edge_indicator.push_back(false); - dominated_edge_indicator.push_back(false); - - if (not check_edge_domination(e)) { - critical_edge_indicator.at(endIdx) = true; - dominated_edge_indicator.at(endIdx) = false; - criticalCoreEdges.push_back({filt, u, v}); - if (endIdx > 1) - set_edge_critical(endIdx, filt); - } else - dominated_edge_indicator.at(endIdx) = true; - endIdx++; - } - -#ifdef DEBUG_TRACES - std::cout << "The total number of critical edges is: " << criticalCoreEdges.size() << std::endl; - std::cout << "The total number of non-critical edges is: " << totEdges - criticalCoreEdges.size() << std::endl; -#endif // DEBUG_TRACES - edgeCollapsed = true; - return criticalCoreEdges; - } - - void insert_vertex(const Vertex& vertex, double filt_val) { - auto rw = vertexToRow.find(vertex); - if (rw == vertexToRow.end()) { - // Initializing the diagonal element of the adjency matrix corresponding to rw_b. - sparseRowAdjMatrix.insert(rows, rows) = filt_val; - vertDomnIndicator.push_back(false); - contractionIndicator.push_back(false); - rowIterator.push(rows); - vertexToRow.insert(std::make_pair(vertex, rows)); - rowToVertex.insert(std::make_pair(rows, vertex)); - vertices.emplace(vertex); - rows++; - } - } - - void insert_new_edges(const Vertex& u, const Vertex& v, double filt_val) - { - // The edge must not be added before, it should be a new edge. - insert_vertex(u, filt_val); - if (u != v) { - insert_vertex(v, filt_val); -#ifdef DEBUG_TRACES - std::cout << "Insertion of the edge begins " << u <<", " << v << std::endl; -#endif // DEBUG_TRACES - - auto rw_u = vertexToRow.find(u); - auto rw_v = vertexToRow.find(v); -#ifdef DEBUG_TRACES - std::cout << "Inserting the edge " << u <<", " << v << std::endl; -#endif // DEBUG_TRACES - sparseRowAdjMatrix.insert(rw_u->second, rw_v->second) = filt_val; - sparseRowAdjMatrix.insert(rw_v->second, rw_u->second) = filt_val; - numOneSimplices++; - } -#ifdef DEBUG_TRACES - else { - std::cout << "Already a member simplex, skipping..." << std::endl; - } -#endif // DEBUG_TRACES - } - - std::size_t num_vertices() const { return vertices.size(); } - -}; \ No newline at end of file diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h new file mode 100644 index 00000000..7bbe86c4 --- /dev/null +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -0,0 +1,432 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Siddharth Pritam + * + * Copyright (C) 2018 INRIA Sophia Antipolis (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + +*/ +#pragma once + +#include +#include +// #include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include + +typedef std::size_t Vertex; +using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first + // element being the smaller i.e {2,3} not {3,2}. However this is at the level + // of row indices on actual vertex lables +using EdgeFilt = std::pair; +using edge_list = std::vector; + +using MapVertexToIndex = std::unordered_map; +using Map = std::unordered_map; + +using sparseRowMatrix = Eigen::SparseMatrix; +using rowInnerIterator = sparseRowMatrix::InnerIterator; + +using doubleVector = std::vector; +using vertexVector = std::vector; +using boolVector = std::vector; + +using doubleQueue = std::queue; + +using EdgeFiltQueue = std::queue; +using EdgeFiltVector = std::vector; + +typedef std::vector> Filtered_sorted_edge_list; +typedef std::unordered_map> u_edge_map; +typedef std::unordered_map> u_edge_to_idx_map; + +//! Class SparseMsMatrix +/*! + The class for storing the Vertices v/s MaxSimplices Sparse Matrix and performing collapses operations using the N^2() + Algorithm. +*/ +class Flag_complex_sparse_matrix { + private: + std::unordered_map rowToVertex; + + // Vertices strored as an unordered_set + std::unordered_set vertices; + + // Unordered set of removed edges. (to enforce removal from the matrix) + std::unordered_set> u_set_removed_redges; + + // Unordered set of dominated edges. (to inforce removal from the matrix) + std::unordered_set> u_set_dominated_redges; + + // Map from egde to its index + u_edge_to_idx_map edge_to_index_map; + // Boolean vector to indicate if the index is critical or not. + boolVector critical_edge_indicator; // critical indicator + + // Boolean vector to indicate if the index is critical or not. + boolVector dominated_edge_indicator; // domination indicator + + //! Stores the Map between verticesrowToVertex and row indices rowToVertex -> row-index. + /*! + \code + MapVertexToIndex = std::unordered_map + \endcode + So, if the original simplex tree had vertices 0,1,4,5
+ rowToVertex would store :
+ \verbatim + Values = | 0 | 1 | 4 | 5 | + Indices = 0 1 2 3 + \endverbatim + And vertexToRow would be a map like the following :
+ \verbatim + 0 -> 0 + 1 -> 1 + 4 -> 2 + 5 -> 3 + \endverbatim + */ + MapVertexToIndex vertexToRow; + + //! Stores the Sparse matrix of double values representing the Original Simplicial Complex. + /*! + \code + sparseRowMatrix = Eigen::SparseMatrix ; + \endcode + ; + */ + + sparseRowMatrix* sparse_colpsd_adj_Matrix; // Stores the collapsed sparse matrix representaion. + sparseRowMatrix sparseRowAdjMatrix; // This is row-major version of the same sparse-matrix, to facilitate easy access + // to elements when traversing the matrix row-wise. + + //! Stores true for dominated rows and false for undominated rows. + /*! + Initialised to a vector of length equal to the value of the variable rows with all false values. + Subsequent removal of dominated vertices is reflected by concerned entries changing to true in this vector. + */ + boolVector vertDomnIndicator; //(domination indicator) + + boolVector contractionIndicator; //(contraction indicator) + + //! Stores the indices of the rows to-be checked for domination in the current iteration. + /*! + Initialised with all rows for the first iteration. + Subsequently once a dominated row is found, its non-dominated neighbhour indices are inserted. + */ + // doubleQueue rowIterator; + + doubleQueue rowIterator; + + // Queue of filtered edges, for edge-collapse, the indices of the edges are the row-indices. + EdgeFiltQueue filteredEgdeIter; + + // Vector of filtered edges, for edge-collapse, the indices of the edges are the row-indices. + EdgeFiltVector f_edge_vector; + + // List of non-dominated edges, the indices of the edges are the vertex lables!!. + Filtered_sorted_edge_list criticalCoreEdges; + // Stores the indices from the sorted filtered edge vector. + // std::set recurCriticalCoreIndcs; + + //! Stores the number of vertices in the original Simplicial Complex. + /*! + This stores the count of vertices (which is also the number of rows in the Matrix). + */ + std::size_t rows; + + std::size_t numOneSimplices; + + bool edgeCollapsed; + + // Edge e is the actual edge (u,v). Not the row ids in the matrixs + bool check_edge_domination(Edge e) + { + auto u = std::get<0>(e); + auto v = std::get<1>(e); + + auto rw_u = vertexToRow[u]; + auto rw_v = vertexToRow[v]; + auto rw_e = std::make_pair(rw_u, rw_v); +#ifdef DEBUG_TRACES + std::cout << "The edge {" << u << ", " << v << "} is going for domination check." << std::endl; +#endif // DEBUG_TRACES + auto commonNeighbours = closed_common_neighbours_row_index(rw_e); +#ifdef DEBUG_TRACES + std::cout << "And its common neighbours are." << std::endl; + for (doubleVector::iterator it = commonNeighbours.begin(); it!=commonNeighbours.end(); it++) { + std::cout << rowToVertex[*it] << ", " ; + } + std::cout<< std::endl; +#endif // DEBUG_TRACES + if (commonNeighbours.size() > 2) { + if (commonNeighbours.size() == 3) + return true; + else + for (doubleVector::iterator it = commonNeighbours.begin(); it != commonNeighbours.end(); it++) { + auto rw_c = *it; // Typecasting + if (rw_c != rw_u and rw_c != rw_v) { + auto neighbours_c = closed_neighbours_row_index(rw_c); + // If neighbours_c contains the common neighbours. + if (std::includes(neighbours_c.begin(), neighbours_c.end(), commonNeighbours.begin(), + commonNeighbours.end())) + return true; + } + } + } + return false; + } + + // The edge should be sorted by the indices and indices are original + bool check_domination_indicator(Edge e) + { + return dominated_edge_indicator[edge_to_index_map[e]]; + } + + std::set three_clique_indices(std::size_t crit) { + std::set edge_indices; + + Edge e = std::get<0>(f_edge_vector[crit]); + Vertex u = std::get<0>(e); + Vertex v = std::get<1>(e); + +#ifdef DEBUG_TRACES + std::cout << "The current critical edge to re-check criticality with filt value is : f {" << u << "," << v + << "} = " << std::get<1>(f_edge_vector[crit]) << std::endl; +#endif // DEBUG_TRACES + auto rw_u = vertexToRow[u]; + auto rw_v = vertexToRow[v]; + auto rw_critical_edge = std::make_pair(rw_u, rw_v); + + doubleVector commonNeighbours = closed_common_neighbours_row_index(rw_critical_edge); + + if (commonNeighbours.size() > 2) { + for (doubleVector::iterator it = commonNeighbours.begin(); it != commonNeighbours.end(); it++) { + auto rw_c = *it; + if (rw_c != rw_u and rw_c != rw_v) { + auto e_with_new_nbhr_v = std::minmax(u, rowToVertex[rw_c]); + auto e_with_new_nbhr_u = std::minmax(v, rowToVertex[rw_c]); + edge_indices.emplace(edge_to_index_map[e_with_new_nbhr_v]); + edge_indices.emplace(edge_to_index_map[e_with_new_nbhr_u]); + } + } + } + return edge_indices; + } + + void set_edge_critical(std::size_t indx, double filt) { +#ifdef DEBUG_TRACES + std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << + std::endl; +#endif // DEBUG_TRACES + std::set effectedIndcs = three_clique_indices(indx); + if (effectedIndcs.size() > 0) { + for (auto idx = indx - 1; idx > 0; idx--) { + Edge e = std::get<0>(f_edge_vector[idx]); + Vertex u = std::get<0>(e); + Vertex v = std::get<1>(e); + // If idx is not critical so it should be proceses, otherwise it stays in the graph // prev + // code : recurCriticalCoreIndcs.find(idx) == recurCriticalCoreIndcs.end() + if (not critical_edge_indicator.at(idx)) { + // If idx is affected + if (effectedIndcs.find(idx) != effectedIndcs.end()) { + if (not check_edge_domination(e)) { +#ifdef DEBUG_TRACES + std::cout << "The curent index became critical " << idx << std::endl; +#endif // DEBUG_TRACES + critical_edge_indicator.at(idx) = true; + criticalCoreEdges.push_back({filt, u, v}); + std::set inner_effected_indcs = three_clique_indices(idx); + for (auto inr_idx = inner_effected_indcs.rbegin(); inr_idx != inner_effected_indcs.rend(); inr_idx++) { + if (*inr_idx < idx) effectedIndcs.emplace(*inr_idx); + } + inner_effected_indcs.clear(); +#ifdef DEBUG_TRACES + std::cout << "The following edge is critical with filt value: {" << std::get<0>(e) << "," << + std::get<1>(e) << "}; " << filt << std::endl; +#endif // DEBUG_TRACES + } else + u_set_dominated_redges.emplace(std::minmax(vertexToRow[u], vertexToRow[v])); + } else + // Idx is not affected hence dominated. + u_set_dominated_redges.emplace(std::minmax(vertexToRow[u], vertexToRow[v])); + } + } + } + effectedIndcs.clear(); + u_set_dominated_redges.clear(); + } + + // Returns list of non-zero columns of the particular indx. + doubleVector closed_neighbours_row_index(double indx) + { + doubleVector nonZeroIndices; + Vertex u = indx; + Vertex v; + // std::cout << "The neighbours of the vertex: " << rowToVertex[u] << " are. " << std::endl; + if (not vertDomnIndicator[indx]) { + // Iterate over the non-zero columns + for (rowInnerIterator it(sparseRowAdjMatrix, indx); it; ++it) { + v = it.index(); + // If the vertex v is not dominated and the edge {u,v} is still in the matrix + if (not vertDomnIndicator[v] and u_set_removed_redges.find(std::minmax(u, v)) == u_set_removed_redges.end() and + u_set_dominated_redges.find(std::minmax(u, v)) == u_set_dominated_redges.end()) { + // inner index, here it is equal to it.columns() + nonZeroIndices.push_back(it.index()); + // std::cout << rowToVertex[it.index()] << ", " ; + } + } + // std::cout << std::endl; + } + return nonZeroIndices; + } + + doubleVector closed_common_neighbours_row_index(Edge e) // Returns the list of closed neighbours of the edge :{u,v}. + { + doubleVector common; + doubleVector nonZeroIndices_u; + doubleVector nonZeroIndices_v; + double u = std::get<0>(e); + double v = std::get<1>(e); + + nonZeroIndices_u = closed_neighbours_row_index(u); + nonZeroIndices_v = closed_neighbours_row_index(v); + std::set_intersection(nonZeroIndices_u.begin(), nonZeroIndices_u.end(), nonZeroIndices_v.begin(), + nonZeroIndices_v.end(), std::inserter(common, common.begin())); + + return common; + } + + public: + //! Main Constructor + /*! + Argument is an instance of Filtered_sorted_edge_list.
+ This is THE function that initialises all data members to appropriate values.
+ rowToVertex, vertexToRow, rows, cols, sparseRowAdjMatrix are initialised here. + vertDomnIndicator ,rowIterator are initialised by init() function which is + called at the begining of this.
+ */ + Flag_complex_sparse_matrix(const size_t& num_vertices, const Filtered_sorted_edge_list& edge_t) + : rows(0), + numOneSimplices(0), + edgeCollapsed(false) { + // Initializing sparseRowAdjMatrix, This is a row-major sparse matrix. + sparseRowAdjMatrix = sparseRowMatrix(num_vertices, num_vertices); + + for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { + f_edge_vector.push_back( + {{std::get<1>(edge_t.at(bgn_idx)), std::get<2>(edge_t.at(bgn_idx))}, std::get<0>(edge_t.at(bgn_idx))}); + } + } + + // Performs edge collapse in a decreasing sequence of the filtration value. + Filtered_sorted_edge_list filtered_edge_collapse() { + std::size_t endIdx = 0; + + u_set_removed_redges.clear(); + u_set_dominated_redges.clear(); + critical_edge_indicator.clear(); + + while (endIdx < f_edge_vector.size()) { + EdgeFilt fec = f_edge_vector[endIdx]; + Edge e = std::get<0>(fec); + Vertex u = std::get<0>(e); + Vertex v = std::get<1>(e); + double filt = std::get<1>(fec); + + // Inserts the edge in the sparse matrix to update the graph (G_i) + insert_new_edges(u, v, filt); + + edge_to_index_map.emplace(std::minmax(u, v), endIdx); + critical_edge_indicator.push_back(false); + dominated_edge_indicator.push_back(false); + + if (not check_edge_domination(e)) { + critical_edge_indicator.at(endIdx) = true; + dominated_edge_indicator.at(endIdx) = false; + criticalCoreEdges.push_back({filt, u, v}); + if (endIdx > 1) + set_edge_critical(endIdx, filt); + } else + dominated_edge_indicator.at(endIdx) = true; + endIdx++; + } + +#ifdef DEBUG_TRACES + std::cout << "The total number of critical edges is: " << criticalCoreEdges.size() << std::endl; + std::cout << "The total number of non-critical edges is: " << f_edge_vector.size() - criticalCoreEdges.size() << std::endl; +#endif // DEBUG_TRACES + edgeCollapsed = true; + return criticalCoreEdges; + } + + void insert_vertex(const Vertex& vertex, double filt_val) { + auto rw = vertexToRow.find(vertex); + if (rw == vertexToRow.end()) { + // Initializing the diagonal element of the adjency matrix corresponding to rw_b. + sparseRowAdjMatrix.insert(rows, rows) = filt_val; + vertDomnIndicator.push_back(false); + contractionIndicator.push_back(false); + rowIterator.push(rows); + vertexToRow.insert(std::make_pair(vertex, rows)); + rowToVertex.insert(std::make_pair(rows, vertex)); + vertices.emplace(vertex); + rows++; + } + } + + void insert_new_edges(const Vertex& u, const Vertex& v, double filt_val) + { + // The edge must not be added before, it should be a new edge. + insert_vertex(u, filt_val); + if (u != v) { + insert_vertex(v, filt_val); +#ifdef DEBUG_TRACES + std::cout << "Insertion of the edge begins " << u <<", " << v << std::endl; +#endif // DEBUG_TRACES + + auto rw_u = vertexToRow.find(u); + auto rw_v = vertexToRow.find(v); +#ifdef DEBUG_TRACES + std::cout << "Inserting the edge " << u <<", " << v << std::endl; +#endif // DEBUG_TRACES + sparseRowAdjMatrix.insert(rw_u->second, rw_v->second) = filt_val; + sparseRowAdjMatrix.insert(rw_v->second, rw_u->second) = filt_val; + numOneSimplices++; + } +#ifdef DEBUG_TRACES + else { + std::cout << "Already a member simplex, skipping..." << std::endl; + } +#endif // DEBUG_TRACES + } + + std::size_t num_vertices() const { return vertices.size(); } + +}; \ No newline at end of file diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 427c315e..67f35e89 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -25,7 +25,7 @@ // ^ // /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. -#include "gudhi/FlagComplexSpMatrix.h" +#include "gudhi/Flag_complex_sparse_matrix.h" #include "gudhi/Rips_edge_list.h" #include "gudhi/graph_simplicial_complex.h" #include "gudhi/distance_functions.h" @@ -64,7 +64,7 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt std::cout << "f[" << std::get<1>(edge) << ", " << std::get<2>(edge) << "] = " << std::get<0>(edge) << std::endl; } - FlagComplexSpMatrix flag_complex_sparse_matrix(5, edges); + Flag_complex_sparse_matrix flag_complex_sparse_matrix(5, edges); auto collapse_edges = flag_complex_sparse_matrix.filtered_edge_collapse(); std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; BOOST_CHECK(collapse_edges.size() <= edges.size()); 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 63c91ebc..75eb6d67 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include #include @@ -131,7 +131,7 @@ int main(int argc, char* argv[]) { // Now we will perform filtered edge collapse to sparsify the edge list edge_t. std::cout << "Filtered edge collapse begins" << std::endl; - FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t); + Flag_complex_sparse_matrix mat_filt_edge_coll(number_of_points, edge_t); std::cout << "Matrix instansiated" << std::endl; Filtered_sorted_edge_list collapse_edges; collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); 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 af08477c..b316391b 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include #include @@ -115,7 +115,7 @@ int main(int argc, char* argv[]) { // Now we will perform filtered edge collapse to sparsify the edge list edge_t. std::cout << "Filtered edge collapse begins" << std::endl; - FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t); + Flag_complex_sparse_matrix mat_filt_edge_coll(number_of_points, edge_t); std::cout << "Matrix instansiated" << std::endl; Filtered_sorted_edge_list collapse_edges; collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); -- cgit v1.2.3 From 076cc203005373ddcb58055af3db604240157601 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Mon, 6 Apr 2020 15:01:38 +0200 Subject: remove num_vertices from flag complex sparse matrix constructor as demanded by Marc in strong complex review. Some cleanup --- .../include/gudhi/Flag_complex_sparse_matrix.h | 24 ++++++++++------------ src/Collapse/test/collapse_unit_test.cpp | 22 +++----------------- ...tance_matrix_edge_collapse_rips_persistence.cpp | 2 +- .../point_cloud_edge_collapse_rips_persistence.cpp | 2 +- 4 files changed, 16 insertions(+), 34 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index 57151371..786a970a 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -62,7 +62,7 @@ class Flag_complex_sparse_matrix { private: std::unordered_map row_to_vertex; - // Vertices strored as an unordered_set + // Vertices stored as an unordered_set std::unordered_set vertices; // Unordered set of removed edges. (to enforce removal from the matrix) @@ -132,8 +132,6 @@ class Flag_complex_sparse_matrix { */ std::size_t rows; - std::size_t numOneSimplices; - bool edgeCollapsed; // Edge e is the actual edge (u,v). Not the row ids in the matrixs @@ -309,16 +307,15 @@ class Flag_complex_sparse_matrix { domination_indicator are initialised by init() function which is called at the begining of this.
*/ - Flag_complex_sparse_matrix(const size_t& num_vertices, const Filtered_sorted_edge_list& edge_t) + Flag_complex_sparse_matrix(const Filtered_sorted_edge_list& edge_t) : rows(0), - numOneSimplices(0), edgeCollapsed(false) { - // Initializing sparse_row_adjacency_matrix, This is a row-major sparse matrix. - sparse_row_adjacency_matrix = sparseRowMatrix(num_vertices, num_vertices); - for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { - f_edge_vector.push_back( - {{std::get<1>(edge_t.at(bgn_idx)), std::get<2>(edge_t.at(bgn_idx))}, std::get<0>(edge_t.at(bgn_idx))}); + Vertex u = std::get<1>(edge_t.at(bgn_idx)); + Vertex v = std::get<2>(edge_t.at(bgn_idx)); + f_edge_vector.push_back({{u, v}, std::get<0>(edge_t.at(bgn_idx))}); + vertices.emplace(u); + vertices.emplace(v); } } @@ -330,6 +327,9 @@ class Flag_complex_sparse_matrix { u_set_dominated_redges.clear(); critical_edge_indicator.clear(); + // Initializing sparse_row_adjacency_matrix, This is a row-major sparse matrix. + sparse_row_adjacency_matrix = sparseRowMatrix(vertices.size(), vertices.size()); + while (endIdx < f_edge_vector.size()) { EdgeFilt fec = f_edge_vector[endIdx]; Edge e = std::get<0>(fec); @@ -371,7 +371,6 @@ class Flag_complex_sparse_matrix { domination_indicator.push_back(false); vertex_to_row.insert(std::make_pair(vertex, rows)); row_to_vertex.insert(std::make_pair(rows, vertex)); - vertices.emplace(vertex); rows++; } } @@ -393,7 +392,6 @@ class Flag_complex_sparse_matrix { #endif // DEBUG_TRACES sparse_row_adjacency_matrix.insert(rw_u->second, rw_v->second) = filt_val; sparse_row_adjacency_matrix.insert(rw_v->second, rw_u->second) = filt_val; - numOneSimplices++; } #ifdef DEBUG_TRACES else { @@ -406,4 +404,4 @@ class Flag_complex_sparse_matrix { }; -#endif // FLAG_COMPLEX_SPARSE_MATRIX_H_ \ No newline at end of file +#endif // FLAG_COMPLEX_SPARSE_MATRIX_H_ diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 67f35e89..4857580c 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -23,27 +23,11 @@ #include #include -// ^ -// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. #include "gudhi/Flag_complex_sparse_matrix.h" #include "gudhi/Rips_edge_list.h" #include "gudhi/graph_simplicial_complex.h" #include "gudhi/distance_functions.h" -//using namespace Gudhi; - -// Types definition -//using Vector_of_points = std::vector>; - -//using Simplex_tree = Gudhi::Simplex_tree; -//using Filtration_value = double; -//using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; -/*using Rips_complex = Gudhi::rips_complex::Rips_complex; -using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; -using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; -*/ -//using Distance_matrix = std::vector>; - using Filtration_value = double; using Vertex_handle = size_t; using Filtered_edge = std::tuple; @@ -64,7 +48,7 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt std::cout << "f[" << std::get<1>(edge) << ", " << std::get<2>(edge) << "] = " << std::get<0>(edge) << std::endl; } - Flag_complex_sparse_matrix flag_complex_sparse_matrix(5, edges); + Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); auto collapse_edges = flag_complex_sparse_matrix.filtered_edge_collapse(); std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; BOOST_CHECK(collapse_edges.size() <= edges.size()); @@ -136,7 +120,7 @@ BOOST_AUTO_TEST_CASE(collapse) { */ edges.push_back({4., 2, 5}); edges.push_back({4., 4, 3}); - trace_and_check_collapse(edges, {{2., 1, 3}, {4., 2, 5}, {4., 4, 3}}); + trace_and_check_collapse(edges, {{2., 1, 3}, {4., 4, 3}}); /* 1 2 4 @@ -149,7 +133,7 @@ BOOST_AUTO_TEST_CASE(collapse) { */ edges.push_back({5., 1, 5}); edges.push_back({5., 0, 4}); - trace_and_check_collapse(edges, {{2., 1, 3}, {4., 2, 5}, {4., 4, 3}, {5., 0, 4}}); + trace_and_check_collapse(edges, {{2., 1, 3}, {4., 4, 3}, {5., 0, 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 75eb6d67..7f5a9454 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -131,7 +131,7 @@ int main(int argc, char* argv[]) { // Now we will perform filtered edge collapse to sparsify the edge list edge_t. std::cout << "Filtered edge collapse begins" << std::endl; - Flag_complex_sparse_matrix mat_filt_edge_coll(number_of_points, edge_t); + Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); std::cout << "Matrix instansiated" << std::endl; Filtered_sorted_edge_list collapse_edges; collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); 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 b316391b..e3290b7a 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -115,7 +115,7 @@ int main(int argc, char* argv[]) { // Now we will perform filtered edge collapse to sparsify the edge list edge_t. std::cout << "Filtered edge collapse begins" << std::endl; - Flag_complex_sparse_matrix mat_filt_edge_coll(number_of_points, edge_t); + Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); std::cout << "Matrix instansiated" << std::endl; Filtered_sorted_edge_list collapse_edges; collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); -- cgit v1.2.3 From 9654c177078fc598c8a8424dd67d0742bf0defb9 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 9 Apr 2020 21:46:42 +0200 Subject: Use an output iterator for edge collapse return instead of storing it --- .../include/gudhi/Flag_complex_sparse_matrix.h | 20 +++----- src/Collapse/test/collapse_unit_test.cpp | 6 ++- ...tance_matrix_edge_collapse_rips_persistence.cpp | 46 ++++------------- .../point_cloud_edge_collapse_rips_persistence.cpp | 59 ++++++---------------- 4 files changed, 37 insertions(+), 94 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index d7014f2f..033c27a3 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -55,7 +55,6 @@ using boolVector = std::vector; using EdgeFiltVector = std::vector; typedef std::vector> Filtered_sorted_edge_list; -typedef std::unordered_map> u_edge_map; typedef std::unordered_map> u_edge_to_idx_map; //! Class SparseMsMatrix @@ -126,8 +125,6 @@ class Flag_complex_sparse_matrix { // Vector of filtered edges, for edge-collapse, the indices of the edges are the row-indices. EdgeFiltVector f_edge_vector; - // List of non-dominated edges, the indices of the edges are the vertex lables!!. - Filtered_sorted_edge_list critical_core_edges; // Stores the indices from the sorted filtered edge vector. // std::set recurCriticalCoreIndcs; @@ -214,7 +211,8 @@ class Flag_complex_sparse_matrix { return edge_indices; } - void set_edge_critical(std::size_t indx, double filt) { + template + void set_edge_critical(std::size_t indx, double filt, FilteredEdgeInsertion filtered_edge_insert) { #ifdef DEBUG_TRACES std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << std::endl; @@ -235,7 +233,7 @@ class Flag_complex_sparse_matrix { std::cout << "The curent index became critical " << idx << std::endl; #endif // DEBUG_TRACES critical_edge_indicator.at(idx) = true; - critical_core_edges.push_back({filt, u, v}); + filtered_edge_insert({u, v}, filt); std::set inner_effected_indcs = three_clique_indices(idx); for (auto inr_idx = inner_effected_indcs.rbegin(); inr_idx != inner_effected_indcs.rend(); inr_idx++) { if (*inr_idx < idx) effectedIndcs.emplace(*inr_idx); @@ -354,7 +352,8 @@ class Flag_complex_sparse_matrix { } // Performs edge collapse in a decreasing sequence of the filtration value. - Filtered_sorted_edge_list filtered_edge_collapse() { + template + void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { std::size_t endIdx = 0; u_set_removed_redges.clear(); @@ -381,20 +380,15 @@ class Flag_complex_sparse_matrix { if (not check_edge_domination(e)) { critical_edge_indicator.at(endIdx) = true; dominated_edge_indicator.at(endIdx) = false; - critical_core_edges.push_back({filt, u, v}); + filtered_edge_insert({u, v}, filt); if (endIdx > 1) - set_edge_critical(endIdx, filt); + set_edge_critical(endIdx, filt, filtered_edge_insert); } else dominated_edge_indicator.at(endIdx) = true; endIdx++; } -#ifdef DEBUG_TRACES - std::cout << "The total number of critical edges is: " << critical_core_edges.size() << std::endl; - std::cout << "The total number of non-critical edges is: " << f_edge_vector.size() - critical_core_edges.size() << std::endl; -#endif // DEBUG_TRACES edgeCollapsed = true; - return critical_core_edges; } void insert_vertex(const Vertex& vertex, double filt_val) { diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 4857580c..29f33219 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -49,7 +49,11 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt } Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); - auto collapse_edges = flag_complex_sparse_matrix.filtered_edge_collapse(); + Filtered_sorted_edge_list collapse_edges; + flag_complex_sparse_matrix.filtered_edge_collapse( + [&collapse_edges](std::pair edge, double filtration) { + collapse_edges.push_back({std::get<0>(edge), std::get<1>(edge), filtration}); + }); std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; BOOST_CHECK(collapse_edges.size() <= edges.size()); for (auto edge_from_collapse : collapse_edges) { 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 7f5a9454..98a90892 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -1,5 +1,4 @@ #include -#include #include #include #include @@ -17,7 +16,6 @@ using Vector_of_points = std::vector; using Simplex_tree = Gudhi::Simplex_tree; using Filtration_value = double; -using Rips_complex = Gudhi::rips_complex::Rips_complex; using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -62,32 +60,6 @@ void program_options(int argc, char* const argv[], double& min_persistence, doub } } -class filt_edge_to_dist_matrix { - public: - template - filt_edge_to_dist_matrix(Distance_matrix& distance_mat, Filtered_sorted_edge_list& edge_filt, - std::size_t number_of_points) { - double inf = std::numeric_limits::max(); - doubleVector distances; - std::pair e; - for (std::size_t indx = 0; indx < number_of_points; indx++) { - for (std::size_t j = 0; j <= indx; j++) { - if (j == indx) - distances.push_back(0); - else - distances.push_back(inf); - } - distance_mat.push_back(distances); - distances.clear(); - } - - for (auto edIt = edge_filt.begin(); edIt != edge_filt.end(); edIt++) { - e = std::minmax(std::get<1>(*edIt), std::get<2>(*edIt)); - distance_mat.at(std::get<1>(e)).at(std::get<0>(e)) = std::get<0>(*edIt); - } - } -}; - void program_options(int argc, char* argv[], std::string& csv_matrix_file, std::string& filediag, Filtration_value& threshold, int& dim_max, int& p, Filtration_value& min_persistence); @@ -133,16 +105,18 @@ int main(int argc, char* argv[]) { std::cout << "Filtered edge collapse begins" << std::endl; Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); std::cout << "Matrix instansiated" << std::endl; - Filtered_sorted_edge_list collapse_edges; - collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); - filt_edge_to_dist_matrix(sparse_distances, collapse_edges, number_of_points); - std::cout << "Total number of vertices after collapse in the sparse matrix are: " << mat_filt_edge_coll.num_vertices() - << std::endl; - - Rips_complex rips_complex_after_collapse(sparse_distances, threshold); Simplex_tree stree; - rips_complex_after_collapse.create_complex(stree, dim_max); + mat_filt_edge_coll.filtered_edge_collapse( + [&stree](std::vector edge, double 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.); + // insert the edge + stree.insert_simplex(edge, filtration); + }); + + stree.expansion(dim_max); std::cout << "The complex contains " << stree.num_simplices() << " simplices after collapse. \n"; std::cout << " and has dimension " << stree.dimension() << " \n"; 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 a2840674..70d8d9c5 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -1,8 +1,6 @@ #include -#include #include #include -#include #include #include #include @@ -11,16 +9,18 @@ #include #include +#include // for std::pair +#include + // Types definition using Simplex_tree = Gudhi::Simplex_tree<>; using Filtration_value = Simplex_tree::Filtration_value; +using Vertex_handle = std::size_t; /*Simplex_tree::Vertex_handle;*/ using Point = std::vector; using Vector_of_points = std::vector; -using Rips_complex = Gudhi::rips_complex::Rips_complex; -using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; using Distance_matrix = std::vector>; @@ -29,38 +29,10 @@ using Adjacency_list = boost::adjacency_list, boost::property>; - -class filt_edge_to_dist_matrix { - public: - template - filt_edge_to_dist_matrix(Distance_matrix& distance_mat, Filtered_sorted_edge_list& edge_filt, - std::size_t number_of_points) { - double inf = std::numeric_limits::max(); - doubleVector distances; - std::pair e; - for (std::size_t indx = 0; indx < number_of_points; indx++) { - for (std::size_t j = 0; j <= indx; j++) { - if (j == indx) - distances.push_back(0); - else - distances.push_back(inf); - } - distance_mat.push_back(distances); - distances.clear(); - } - - for (auto edIt = edge_filt.begin(); edIt != edge_filt.end(); edIt++) { - e = std::minmax(std::get<1>(*edIt), std::get<2>(*edIt)); - distance_mat.at(std::get<1>(e)).at(std::get<0>(e)) = std::get<0>(*edIt); - } - } -}; - void program_options(int argc, char* argv[], std::string& off_file_points, std::string& filediag, Filtration_value& threshold, int& dim_max, int& p, Filtration_value& min_persistence); int main(int argc, char* argv[]) { - typedef size_t Vertex_handle; typedef std::vector> Filtered_sorted_edge_list; auto the_begin = std::chrono::high_resolution_clock::now(); @@ -82,8 +54,6 @@ int main(int argc, char* argv[]) { std::cout << min_persistence << ", " << threshold << ", " << dim_max << ", " << off_file_points << ", " << filediag << std::endl; - Map map_empty; - Distance_matrix sparse_distances; Gudhi::Points_off_reader off_reader(off_file_points); @@ -120,18 +90,19 @@ int main(int argc, char* argv[]) { std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; std::cout << "Matrix instansiated" << std::endl; - Filtered_sorted_edge_list collapse_edges; - collapse_edges = mat_filt_edge_coll.filtered_edge_collapse(); - filt_edge_to_dist_matrix(sparse_distances, collapse_edges, number_of_points); - std::cout << "Total number of vertices after collapse in the sparse matrix are: " << mat_filt_edge_coll.num_vertices() - << std::endl; - - // Rips_complex rips_complex_before_collapse(distances, threshold); - Rips_complex rips_complex_after_collapse(sparse_distances, threshold); Simplex_tree stree; - rips_complex_after_collapse.create_complex(stree, dim_max); - + mat_filt_edge_coll.filtered_edge_collapse( + [&stree](std::vector edge, double 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.); + // insert the edge + stree.insert_simplex(edge, filtration); + }); + + stree.expansion(dim_max); + std::cout << "The complex contains " << stree.num_simplices() << " simplices after collapse. \n"; std::cout << " and has dimension " << stree.dimension() << " \n"; -- cgit v1.2.3 From edaf9743d7b61201e1f0590576a3d2196ca1ca53 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 9 Apr 2020 22:11:26 +0200 Subject: Fix unit test --- src/Collapse/test/collapse_unit_test.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 29f33219..63fe271b 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -48,11 +48,13 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt std::cout << "f[" << std::get<1>(edge) << ", " << std::get<2>(edge) << "] = " << std::get<0>(edge) << std::endl; } + std::cout << "COLLAPSE - keep edges: " << std::endl; Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); Filtered_sorted_edge_list collapse_edges; flag_complex_sparse_matrix.filtered_edge_collapse( [&collapse_edges](std::pair edge, double filtration) { - collapse_edges.push_back({std::get<0>(edge), std::get<1>(edge), filtration}); + std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; + collapse_edges.push_back({filtration, std::get<0>(edge), std::get<1>(edge)}); }); std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; BOOST_CHECK(collapse_edges.size() <= edges.size()); -- cgit v1.2.3 From ca843d47c97e2d1be317df8611be6410e78aced4 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 9 Apr 2020 22:29:53 +0200 Subject: Remove some unused include --- src/Collapse/test/collapse_unit_test.cpp | 13 ++----------- 1 file changed, 2 insertions(+), 11 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 63fe271b..88af53e8 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -9,14 +9,8 @@ */ #include -#include -#include -#include -#include // std::pair, std::make_pair -#include // float comparison -#include -#include // greater -#include // std::tie +#include +#include #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "collapse" @@ -24,9 +18,6 @@ #include #include "gudhi/Flag_complex_sparse_matrix.h" -#include "gudhi/Rips_edge_list.h" -#include "gudhi/graph_simplicial_complex.h" -#include "gudhi/distance_functions.h" using Filtration_value = double; using Vertex_handle = size_t; -- cgit v1.2.3 From 050fde353b73da4e93aaee2beab1291cc044be42 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 10 Apr 2020 07:55:30 +0200 Subject: All in a Gudhi::collapse namespace --- src/Collapse/doc/intro_edge_collapse.h | 4 ++-- .../include/gudhi/Flag_complex_sparse_matrix.h | 19 ++++++++++++------- src/Collapse/test/collapse_unit_test.cpp | 2 +- ...distance_matrix_edge_collapse_rips_persistence.cpp | 4 +--- .../point_cloud_edge_collapse_rips_persistence.cpp | 2 +- 5 files changed, 17 insertions(+), 14 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h index b42b5e65..70c816f4 100644 --- a/src/Collapse/doc/intro_edge_collapse.h +++ b/src/Collapse/doc/intro_edge_collapse.h @@ -13,7 +13,7 @@ namespace Gudhi { -namespace edge_collapse { +namespace collapse { /** \defgroup edge_collapse Edge collapse * @@ -91,7 +91,7 @@ namespace edge_collapse { */ /** @} */ // end defgroup strong_collapse -} // namespace edge_collapse +} // namespace collapse } // namespace Gudhi diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index 4862c1b0..0d5f37a4 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -35,27 +35,28 @@ #include #include +namespace Gudhi { + +namespace collapse { + + typedef std::size_t Vertex; using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first // element being the smaller i.e {2,3} not {3,2}. However this is at the level // of row indices on actual vertex lables using EdgeFilt = std::pair; -using edge_list = std::vector; using MapVertexToIndex = std::unordered_map; -using Map = std::unordered_map; using sparseRowMatrix = Eigen::SparseMatrix; -using rowInnerIterator = sparseRowMatrix::InnerIterator; using doubleVector = std::vector; -using vertexVector = std::vector; using boolVector = std::vector; using EdgeFiltVector = std::vector; -typedef std::vector> Filtered_sorted_edge_list; -typedef std::unordered_map> u_edge_to_idx_map; +using Filtered_sorted_edge_list = std::vector>; +using u_edge_to_idx_map = std::unordered_map>; //! Class SparseMsMatrix /*! @@ -266,7 +267,7 @@ class Flag_complex_sparse_matrix { #endif // DEBUG_TRACES if (not domination_indicator[indx]) { // Iterate over the non-zero columns - for (rowInnerIterator it(sparse_row_adjacency_matrix, indx); it; ++it) { + for (sparseRowMatrix::InnerIterator it(sparse_row_adjacency_matrix, indx); it; ++it) { v = it.index(); // If the vertex v is not dominated and the edge {u,v} is still in the matrix if (not domination_indicator[v] and u_set_removed_redges.find(std::minmax(u, v)) == u_set_removed_redges.end() and @@ -432,4 +433,8 @@ class Flag_complex_sparse_matrix { }; +} // namespace collapse + +} // namespace Gudhi + #endif // FLAG_COMPLEX_SPARSE_MATRIX_H_ diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 88af53e8..8cfa7d5f 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -40,7 +40,7 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt } std::cout << "COLLAPSE - keep edges: " << std::endl; - Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); + Gudhi::collapse::Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); Filtered_sorted_edge_list collapse_edges; flag_complex_sparse_matrix.filtered_edge_collapse( [&collapse_edges](std::pair edge, double 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 98a90892..b937a8ff 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -78,8 +78,6 @@ int main(int argc, char* argv[]) { program_options(argc, argv, csv_matrix_file, filediag, threshold, dim_max, p, min_persistence); - Map map_empty; - Distance_matrix distances; Distance_matrix sparse_distances; @@ -103,7 +101,7 @@ int main(int argc, char* argv[]) { // Now we will perform filtered edge collapse to sparsify the edge list edge_t. std::cout << "Filtered edge collapse begins" << std::endl; - Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); + Gudhi::collapse::Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); std::cout << "Matrix instansiated" << std::endl; Simplex_tree stree; 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 70d8d9c5..5fa24306 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -85,7 +85,7 @@ int main(int argc, char* argv[]) { } std::cout << "Filtered edge collapse begins" << std::endl; - Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); + Gudhi::collapse::Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; -- cgit v1.2.3 From b5bb9fd2a129ab9c429a0c7c67ca4442e6e7b1b0 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Sat, 11 Apr 2020 09:21:36 +0200 Subject: Vertex_handle, Filtration_value and Row_index type --- .../include/gudhi/Flag_complex_sparse_matrix.h | 178 ++++++++++----------- src/Collapse/test/collapse_unit_test.cpp | 11 +- ...tance_matrix_edge_collapse_rips_persistence.cpp | 40 ++--- .../point_cloud_edge_collapse_rips_persistence.cpp | 31 +--- 4 files changed, 111 insertions(+), 149 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index 7e3e5a62..edf3f415 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -30,41 +30,48 @@ #include #include #include -#include - -#include -#include namespace Gudhi { namespace collapse { - -typedef std::size_t Vertex; -using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first +/** + * \class Flag_complex_sparse_matrix + * \brief Flag complex sparse matrix data structure. + * + * \ingroup collapse + * + * \details + * A class to store the vertices v/s MaxSimplices Sparse Matrix and to perform collapse operations using the N^2() + * Algorithm. + * + * \tparam Vertex_handle type must be a signed integer type. It admits a total order <. + * \tparam Filtration_value type for the value of the filtration function. Must be comparable with <. + */ +template +class Flag_complex_sparse_matrix { + private: + using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first // element being the smaller i.e {2,3} not {3,2}. However this is at the level // of row indices on actual vertex lables -using Filtered_edge = std::pair; + using Filtered_edge = std::pair; -using Map_vertex_to_index = std::unordered_map; + using Row_index = std::size_t; -using Sparse_row_matrix = Eigen::SparseMatrix; + using Map_vertex_to_index = std::unordered_map; -using doubleVector = std::vector; + using Sparse_row_matrix = Eigen::SparseMatrix; -using Filtered_sorted_edge_list = std::vector>; + using Row_indices_vector = std::vector; + + public: + using Filtered_sorted_edge_list = std::vector>; -//! Class SparseMsMatrix -/*! - The class for storing the Vertices v/s MaxSimplices Sparse Matrix and performing collapses operations using the N^2() - Algorithm. -*/ -class Flag_complex_sparse_matrix { private: - std::unordered_map row_to_vertex_; + std::unordered_map row_to_vertex_; // Vertices stored as an unordered_set - std::unordered_set vertices_; + std::unordered_set vertices_; // Unordered set of removed edges. (to enforce removal from the matrix) std::unordered_set> u_set_removed_redges_; @@ -72,8 +79,8 @@ class Flag_complex_sparse_matrix { // Unordered set of dominated edges. (to inforce removal from the matrix) std::unordered_set> u_set_dominated_redges_; - // Map from egde to its index - std::unordered_map> edge_to_index_map_; + // Map from edge to its index + std::unordered_map> edge_to_index_map_; // Boolean vector to indicate if the index is critical or not. std::vector critical_edge_indicator_; // critical indicator @@ -96,12 +103,12 @@ class Flag_complex_sparse_matrix { 5 -> 3 \endverbatim */ - std::unordered_map vertex_to_row_; + std::unordered_map vertex_to_row_; - //! Stores the Sparse matrix of double values representing the Original Simplicial Complex. + //! Stores the Sparse matrix of Filtration_value values representing the Original Simplicial Complex. /*! \code - Sparse_row_matrix = Eigen::SparseMatrix ; + Sparse_row_matrix = Eigen::SparseMatrix ; \endcode ; */ @@ -119,23 +126,21 @@ class Flag_complex_sparse_matrix { // Vector of filtered edges, for edge-collapse, the indices of the edges are the row-indices. std::vector f_edge_vector_; - // Stores the indices from the sorted filtered edge vector. - // std::set recurCriticalCoreIndcs; //! Stores the number of vertices_ in the original Simplicial Complex. /*! This stores the count of vertices_ (which is also the number of rows in the Matrix). */ - std::size_t rows; + Row_index rows; // Edge e is the actual edge (u,v). Not the row ids in the matrixs - bool check_edge_domination(Edge e) + bool check_edge_domination(Edge edge) { - auto u = std::get<0>(e); - auto v = std::get<1>(e); + Vertex_handle u = std::get<0>(edge); + Vertex_handle v = std::get<1>(edge); - auto rw_u = vertex_to_row_[u]; - auto rw_v = vertex_to_row_[v]; + Row_index rw_u = vertex_to_row_[u]; + Row_index rw_v = vertex_to_row_[v]; auto rw_e = std::make_pair(rw_u, rw_v); #ifdef DEBUG_TRACES std::cout << "The edge {" << u << ", " << v << "} is going for domination check." << std::endl; @@ -165,18 +170,12 @@ class Flag_complex_sparse_matrix { return false; } - // The edge should be sorted by the indices and indices are original - bool check_domination_indicator(Edge e) - { - return dominated_edge_indicator_[edge_to_index_map_[e]]; - } + std::set three_clique_indices(Row_index crit) { + std::set edge_indices; - std::set three_clique_indices(std::size_t crit) { - std::set edge_indices; - - Edge e = std::get<0>(f_edge_vector_[crit]); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); + 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 @@ -186,7 +185,7 @@ class Flag_complex_sparse_matrix { auto rw_v = vertex_to_row_[v]; auto rw_critical_edge = std::make_pair(rw_u, rw_v); - doubleVector common_neighbours = closed_common_neighbours_row_index(rw_critical_edge); + Row_indices_vector common_neighbours = closed_common_neighbours_row_index(rw_critical_edge); if (common_neighbours.size() > 2) { for (auto rw_c : common_neighbours) { @@ -202,36 +201,36 @@ class Flag_complex_sparse_matrix { } template - void set_edge_critical(std::size_t indx, double filt, FilteredEdgeInsertion filtered_edge_insert) { + void set_edge_critical(Row_index indx, Filtration_value filt, FilteredEdgeInsertion filtered_edge_insert) { #ifdef DEBUG_TRACES std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << std::endl; #endif // DEBUG_TRACES - std::set effectedIndcs = three_clique_indices(indx); + std::set effectedIndcs = three_clique_indices(indx); if (effectedIndcs.size() > 0) { for (auto idx = indx - 1; idx > 0; idx--) { - Edge e = std::get<0>(f_edge_vector_[idx]); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); + Edge edge = std::get<0>(f_edge_vector_[idx]); + Vertex_handle u = std::get<0>(edge); + Vertex_handle v = std::get<1>(edge); // If idx is not critical so it should be proceses, otherwise it stays in the graph // prev // code : recurCriticalCoreIndcs.find(idx) == recurCriticalCoreIndcs.end() if (not critical_edge_indicator_[idx]) { // If idx is affected if (effectedIndcs.find(idx) != effectedIndcs.end()) { - if (not check_edge_domination(e)) { + if (not check_edge_domination(edge)) { #ifdef DEBUG_TRACES std::cout << "The curent index became critical " << idx << std::endl; #endif // DEBUG_TRACES critical_edge_indicator_[idx] = true; filtered_edge_insert({u, v}, filt); - std::set inner_effected_indcs = three_clique_indices(idx); + std::set inner_effected_indcs = three_clique_indices(idx); for (auto inr_idx = inner_effected_indcs.rbegin(); inr_idx != inner_effected_indcs.rend(); inr_idx++) { if (*inr_idx < idx) effectedIndcs.emplace(*inr_idx); } inner_effected_indcs.clear(); #ifdef DEBUG_TRACES - std::cout << "The following edge is critical with filt value: {" << std::get<0>(e) << "," << - std::get<1>(e) << "}; " << filt << std::endl; + std::cout << "The following edge is critical with filt value: {" << u << "," << v << "}; " + << filt << std::endl; #endif // DEBUG_TRACES } else u_set_dominated_redges_.emplace(std::minmax(vertex_to_row_[u], vertex_to_row_[v])); @@ -245,26 +244,24 @@ class Flag_complex_sparse_matrix { u_set_dominated_redges_.clear(); } - // Returns list of non-zero columns of the particular indx. - doubleVector closed_neighbours_row_index(double indx) + // Returns list of non-zero columns of a particular indx. + Row_indices_vector closed_neighbours_row_index(Row_index rw_u) { - doubleVector non_zero_indices; - Vertex u = indx; - Vertex v; + Row_indices_vector non_zero_indices; #ifdef DEBUG_TRACES - std::cout << "The neighbours of the vertex: " << row_to_vertex_[u] << " are. " << std::endl; + std::cout << "The neighbours of the vertex: " << row_to_vertex_[rw_u] << " are. " << std::endl; #endif // DEBUG_TRACES - if (not domination_indicator_[indx]) { + if (not domination_indicator_[rw_u]) { // Iterate over the non-zero columns - for (Sparse_row_matrix::InnerIterator it(sparse_row_adjacency_matrix_, indx); it; ++it) { - v = it.index(); + for (typename Sparse_row_matrix::InnerIterator it(sparse_row_adjacency_matrix_, rw_u); it; ++it) { + Row_index rw_v = it.index(); // If the vertex v is not dominated and the edge {u,v} is still in the matrix - if (not domination_indicator_[v] and u_set_removed_redges_.find(std::minmax(u, v)) == u_set_removed_redges_.end() and - u_set_dominated_redges_.find(std::minmax(u, v)) == u_set_dominated_redges_.end()) { + if (not domination_indicator_[rw_v] and u_set_removed_redges_.find(std::minmax(rw_u, rw_v)) == u_set_removed_redges_.end() and + u_set_dominated_redges_.find(std::minmax(rw_u, rw_v)) == u_set_dominated_redges_.end()) { // inner index, here it is equal to it.columns() - non_zero_indices.push_back(it.index()); + non_zero_indices.push_back(rw_v); #ifdef DEBUG_TRACES - std::cout << row_to_vertex_[it.index()] << ", " ; + std::cout << row_to_vertex_[rw_v] << ", " ; #endif // DEBUG_TRACES } } @@ -275,23 +272,24 @@ class Flag_complex_sparse_matrix { return non_zero_indices; } - doubleVector closed_common_neighbours_row_index(Edge e) // Returns the list of closed neighbours of the edge :{u,v}. + // Returns the list of closed neighbours of the edge :{u,v}. + Row_indices_vector closed_common_neighbours_row_index(const std::pair& rw_edge) { - doubleVector common; - doubleVector non_zero_indices_u; - doubleVector non_zero_indices_v; - double u = std::get<0>(e); - double v = std::get<1>(e); - - non_zero_indices_u = closed_neighbours_row_index(u); - non_zero_indices_v = closed_neighbours_row_index(v); + Row_indices_vector common; + Row_indices_vector non_zero_indices_u; + Row_indices_vector non_zero_indices_v; + Row_index rw_u = std::get<0>(rw_edge); + Row_index rw_v = std::get<1>(rw_edge); + + non_zero_indices_u = closed_neighbours_row_index(rw_u); + non_zero_indices_v = closed_neighbours_row_index(rw_v); std::set_intersection(non_zero_indices_u.begin(), non_zero_indices_u.end(), non_zero_indices_v.begin(), non_zero_indices_v.end(), std::inserter(common, common.begin())); return common; } - - void insert_vertex(const Vertex& vertex, double filt_val) { + + void insert_vertex(const Vertex_handle& vertex, Filtration_value filt_val) { auto rw = vertex_to_row_.find(vertex); if (rw == vertex_to_row_.end()) { // Initializing the diagonal element of the adjency matrix corresponding to rw_b. @@ -303,7 +301,7 @@ class Flag_complex_sparse_matrix { } } - void insert_new_edges(const Vertex& u, const Vertex& v, double filt_val) + void insert_new_edges(const Vertex_handle& u, const Vertex_handle& v, Filtration_value filt_val) { // The edge must not be added before, it should be a new edge. insert_vertex(u, filt_val); @@ -340,8 +338,8 @@ class Flag_complex_sparse_matrix { Flag_complex_sparse_matrix(const Filtered_sorted_edge_list& edge_t) : rows(0) { for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { - Vertex u = std::get<1>(edge_t[bgn_idx]); - Vertex v = std::get<2>(edge_t[bgn_idx]); + Vertex_handle u = std::get<1>(edge_t[bgn_idx]); + Vertex_handle v = std::get<2>(edge_t[bgn_idx]); f_edge_vector_.push_back({{u, v}, std::get<0>(edge_t[bgn_idx])}); vertices_.emplace(u); vertices_.emplace(v); @@ -352,15 +350,15 @@ class Flag_complex_sparse_matrix { Flag_complex_sparse_matrix(const OneSkeletonGraph& one_skeleton_graph) : rows(0) { // Insert all vertices_ - for (auto v_it = boost::vertices_(one_skeleton_graph); v_it.first != v_it.second; ++v_it.first) { + for (auto v_it = boost::vertices(one_skeleton_graph); v_it.first != v_it.second; ++v_it.first) { vertices_.emplace(*(v_it.first)); } // Insert all edges for (auto edge_it = boost::edges(one_skeleton_graph); edge_it.first != edge_it.second; ++edge_it.first) { auto edge = *(edge_it.first); - Vertex u = source(edge, one_skeleton_graph); - Vertex v = target(edge, one_skeleton_graph); + 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)}); } // Sort edges @@ -379,7 +377,7 @@ class Flag_complex_sparse_matrix { // Performs edge collapse in a decreasing sequence of the filtration value. template void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { - std::size_t endIdx = 0; + Row_index endIdx = 0; u_set_removed_redges_.clear(); u_set_dominated_redges_.clear(); @@ -390,10 +388,10 @@ class Flag_complex_sparse_matrix { while (endIdx < f_edge_vector_.size()) { Filtered_edge fec = f_edge_vector_[endIdx]; - Edge e = std::get<0>(fec); - Vertex u = std::get<0>(e); - Vertex v = std::get<1>(e); - double filt = std::get<1>(fec); + 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) insert_new_edges(u, v, filt); @@ -402,7 +400,7 @@ class Flag_complex_sparse_matrix { critical_edge_indicator_.push_back(false); dominated_edge_indicator_.push_back(false); - if (not check_edge_domination(e)) { + if (not check_edge_domination(edge)) { critical_edge_indicator_[endIdx] = true; dominated_edge_indicator_[endIdx] = false; filtered_edge_insert({u, v}, filt); diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 8cfa7d5f..38adfa8a 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -19,10 +19,11 @@ #include "gudhi/Flag_complex_sparse_matrix.h" -using Filtration_value = double; -using Vertex_handle = size_t; +using Filtration_value = float; +using Vertex_handle = short; using Filtered_edge = std::tuple; -using Filtered_sorted_edge_list = std::vector>; +using Filtered_sorted_edge_list = std::vector; +using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; bool find_edge_in_list(const Filtered_edge& edge, const Filtered_sorted_edge_list& edge_list) { for (auto edge_from_list : edge_list) { @@ -40,10 +41,10 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt } std::cout << "COLLAPSE - keep edges: " << std::endl; - Gudhi::collapse::Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); + Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); Filtered_sorted_edge_list collapse_edges; flag_complex_sparse_matrix.filtered_edge_collapse( - [&collapse_edges](std::pair edge, double filtration) { + [&collapse_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; collapse_edges.push_back({filtration, std::get<0>(edge), std::get<1>(edge)}); }); 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 b937a8ff..56e9bab6 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -6,16 +6,14 @@ #include #include -#include - #include -// Types definition -using Point = CGAL::Epick_d::Point_d; -using Vector_of_points = std::vector; - using Simplex_tree = Gudhi::Simplex_tree; -using Filtration_value = double; +using Filtration_value = Simplex_tree::Filtration_value; +using Vertex_handle = Simplex_tree::Vertex_handle; + +using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; + using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -64,17 +62,12 @@ void program_options(int argc, char* argv[], std::string& csv_matrix_file, std:: Filtration_value& threshold, int& dim_max, int& p, Filtration_value& min_persistence); int main(int argc, char* argv[]) { - auto the_begin = std::chrono::high_resolution_clock::now(); - - typedef size_t Vertex_handle; - typedef std::vector> Filtered_sorted_edge_list; - std::string csv_matrix_file; std::string filediag; - double threshold; + Filtration_value threshold; int dim_max = 2; int p; - double min_persistence; + Filtration_value min_persistence; program_options(argc, argv, csv_matrix_file, filediag, threshold, dim_max, p, min_persistence); @@ -82,15 +75,12 @@ int main(int argc, char* argv[]) { Distance_matrix sparse_distances; distances = Gudhi::read_lower_triangular_matrix_from_csv_file(csv_matrix_file); - std::size_t number_of_points = distances.size(); - std::cout << "Read the distance matrix succesfully, of size: " << number_of_points << std::endl; + std::cout << "Read the distance matrix succesfully, of size: " << distances.size() << std::endl; - Filtered_sorted_edge_list edge_t; - std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; + Flag_complex_sparse_matrix::Filtered_sorted_edge_list edge_t; Rips_edge_list Rips_edge_list_from_file(distances, threshold); Rips_edge_list_from_file.create_edges(edge_t); - std::cout<< "Sorted edge list computed" << std::endl; if (edge_t.size() <= 0) { std::cerr << "Total number of egdes are zero." << std::endl; @@ -100,13 +90,11 @@ int main(int argc, char* argv[]) { std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl; // Now we will perform filtered edge collapse to sparsify the edge list edge_t. - std::cout << "Filtered edge collapse begins" << std::endl; - Gudhi::collapse::Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); - std::cout << "Matrix instansiated" << std::endl; + Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); Simplex_tree stree; mat_filt_edge_coll.filtered_edge_collapse( - [&stree](std::vector edge, double filtration) { + [&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.); @@ -134,12 +122,6 @@ int main(int argc, char* argv[]) { pcoh.output_diagram(out); out.close(); } - - auto the_end = std::chrono::high_resolution_clock::now(); - - std::cout << "Total computation time : " << std::chrono::duration(the_end - the_begin).count() - << " ms\n" - << std::endl; return 0; } 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 5fa24306..4b52e4c6 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -16,10 +16,11 @@ using Simplex_tree = Gudhi::Simplex_tree<>; using Filtration_value = Simplex_tree::Filtration_value; -using Vertex_handle = std::size_t; /*Simplex_tree::Vertex_handle;*/ +using Vertex_handle = Simplex_tree::Vertex_handle; using Point = std::vector; using Vector_of_points = std::vector; +using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -33,12 +34,6 @@ void program_options(int argc, char* argv[], std::string& off_file_points, std:: Filtration_value& threshold, int& dim_max, int& p, Filtration_value& min_persistence); int main(int argc, char* argv[]) { - typedef std::vector> Filtered_sorted_edge_list; - - auto the_begin = std::chrono::high_resolution_clock::now(); - std::size_t number_of_points; - - std::string off_file_points; std::string filediag; double threshold; @@ -68,12 +63,8 @@ int main(int argc, char* argv[]) { exit(-1); // ----- >> } - //int dimension = point_vector[0].dimension(); - number_of_points = point_vector.size(); - std::cout << "Successfully read " << number_of_points << " point_vector.\n"; - //std::cout << "Ambient dimension is " << dimension << ".\n"; - - std::cout << "Point Set Generated." << std::endl; + std::cout << "Successfully read " << point_vector.size() << " point_vector.\n"; + std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; Adjacency_list proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), threshold, @@ -84,16 +75,11 @@ int main(int argc, char* argv[]) { exit(-1); } - std::cout << "Filtered edge collapse begins" << std::endl; - Gudhi::collapse::Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); - - std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl; - - std::cout << "Matrix instansiated" << std::endl; + Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); Simplex_tree stree; mat_filt_edge_coll.filtered_edge_collapse( - [&stree](std::vector edge, double filtration) { + [&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.); @@ -122,11 +108,6 @@ int main(int argc, char* argv[]) { out.close(); } - auto the_end = std::chrono::high_resolution_clock::now(); - - std::cout << "Total computation time : " << std::chrono::duration(the_end - the_begin).count() - << " ms\n" - << std::endl; return 0; } -- cgit v1.2.3 From 1ce5d0d19e13a14e8a67442aec7bc40eae68dc8e Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Sun, 12 Apr 2020 10:33:38 +0200 Subject: Modify interface and utils --- .../include/gudhi/Flag_complex_sparse_matrix.h | 86 ++++++++------ src/Collapse/test/collapse_unit_test.cpp | 129 +++++++++++++-------- ...tance_matrix_edge_collapse_rips_persistence.cpp | 28 ++--- .../point_cloud_edge_collapse_rips_persistence.cpp | 15 +-- 4 files changed, 148 insertions(+), 110 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index d472bf15..e90d284d 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -16,6 +16,7 @@ #include #include +#include #include @@ -32,6 +33,7 @@ #include #include + namespace Gudhi { namespace collapse { @@ -47,26 +49,28 @@ namespace collapse { * Algorithm. * * \tparam Vertex_handle type must be a signed integer type. It admits a total order <. - * \tparam Filtration_value type for the value of the filtration function. Must be comparable with <. + * \tparam Filtration type for the value of the filtration function. Must be comparable with <. */ -template +template class Flag_complex_sparse_matrix { private: using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first // element being the smaller i.e {2,3} not {3,2}. However this is at the level // of row indices on actual vertex lables - using Filtered_edge = std::pair; + using Filtered_edge = std::pair; using Row_index = std::size_t; using Map_vertex_to_index = std::unordered_map; - using Sparse_row_matrix = Eigen::SparseMatrix; + using Sparse_row_matrix = Eigen::SparseMatrix; using Row_indices_vector = std::vector; public: - using Filtered_sorted_edge_list = std::vector>; + using Filtered_sorted_edge_list = std::vector>; + using Filtration_value = Filtration; + using Proximity_graph = Gudhi::Proximity_graph; private: std::unordered_map row_to_vertex_; @@ -88,9 +92,9 @@ class Flag_complex_sparse_matrix { // Boolean vector to indicate if the index is critical or not. std::vector dominated_edge_indicator_; // domination indicator - //! Stores the Map between vertices_row_to_vertex_ and row indices row_to_vertex_ -> row-index. + //! Stores the Map between verticesrow_to_vertex_ and row indices row_to_vertex_ -> row-index. /*! - So, if the original simplex tree had vertices_ 0,1,4,5
+ So, if the original simplex tree had vertices 0,1,4,5
row_to_vertex_ would store :
\verbatim Values = | 0 | 1 | 4 | 5 | @@ -106,10 +110,10 @@ class Flag_complex_sparse_matrix { */ std::unordered_map vertex_to_row_; - //! Stores the Sparse matrix of Filtration_value values representing the Original Simplicial Complex. + //! Stores the Sparse matrix of Filtration values representing the Original Simplicial Complex. /*! \code - Sparse_row_matrix = Eigen::SparseMatrix ; + Sparse_row_matrix = Eigen::SparseMatrix ; \endcode ; */ @@ -120,7 +124,7 @@ class Flag_complex_sparse_matrix { //! Stores true for dominated rows and false for undominated rows. /*! Initialised to a vector of length equal to the value of the variable rows with all false values. - Subsequent removal of dominated vertices_ is reflected by concerned entries changing to true in this vector. + Subsequent removal of dominated vertices is reflected by concerned entries changing to true in this vector. */ std::vector domination_indicator_; //(domination indicator) @@ -128,9 +132,9 @@ class Flag_complex_sparse_matrix { std::vector f_edge_vector_; - //! Stores the number of vertices_ in the original Simplicial Complex. + //! Stores the number of vertices in the original Simplicial Complex. /*! - This stores the count of vertices_ (which is also the number of rows in the Matrix). + This stores the count of vertices (which is also the number of rows in the Matrix). */ Row_index rows; @@ -202,7 +206,7 @@ class Flag_complex_sparse_matrix { } template - void set_edge_critical(Row_index indx, Filtration_value filt, FilteredEdgeInsertion filtered_edge_insert) { + void set_edge_critical(Row_index indx, Filtration filt, FilteredEdgeInsertion filtered_edge_insert) { #ifdef DEBUG_TRACES std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << std::endl; @@ -290,7 +294,7 @@ class Flag_complex_sparse_matrix { return common; } - void insert_vertex(Vertex_handle vertex, Filtration_value filt_val) { + void insert_vertex(Vertex_handle vertex, Filtration filt_val) { auto rw = vertex_to_row_.find(vertex); if (rw == vertex_to_row_.end()) { // Initializing the diagonal element of the adjency matrix corresponding to rw_b. @@ -302,7 +306,7 @@ class Flag_complex_sparse_matrix { } } - void insert_new_edges(Vertex_handle u, Vertex_handle v, Filtration_value filt_val) + void insert_new_edges(Vertex_handle u, Vertex_handle v, Filtration filt_val) { // The edge must not be added before, it should be a new edge. insert_vertex(u, filt_val); @@ -336,19 +340,27 @@ class Flag_complex_sparse_matrix { domination_indicator_ are initialised by init() function which is called at the begining of this.
*/ - Flag_complex_sparse_matrix(const Filtered_sorted_edge_list& edge_t) + template + Flag_complex_sparse_matrix(const DistanceMatrix& distance_matrix) : rows(0) { - for (size_t bgn_idx = 0; bgn_idx < edge_t.size(); bgn_idx++) { - Vertex_handle u = std::get<1>(edge_t[bgn_idx]); - Vertex_handle v = std::get<2>(edge_t[bgn_idx]); - f_edge_vector_.push_back({{u, v}, std::get<0>(edge_t[bgn_idx])}); - vertices_.emplace(u); - vertices_.emplace(v); + Vertex_handle num_vertices = std::distance(std::begin(distance_matrix), std::end(distance_matrix)); + + // This one is not part of the loop + vertices_.emplace(0); + // Only browse the lower part of the distance matrix + for (Vertex_handle line_index = 1; line_index < num_vertices; line_index++) { + for (Vertex_handle row_index = 0; row_index < line_index; row_index++) { +#ifdef DEBUG_TRACES + std::cout << "Insert edge: fn[" << row_index << ", " << line_index << "] = " + << distance_matrix[line_index][row_index] << std::endl; +#endif // DEBUG_TRACES + f_edge_vector_.push_back({{row_index, line_index}, distance_matrix[line_index][row_index]}); + } + vertices_.emplace(line_index); } } - template - Flag_complex_sparse_matrix(const OneSkeletonGraph& one_skeleton_graph) + Flag_complex_sparse_matrix(const Proximity_graph& one_skeleton_graph) : rows(0) { // Insert all vertices_ for (auto v_it = boost::vertices(one_skeleton_graph); v_it.first != v_it.second; ++v_it.first) { @@ -362,6 +374,18 @@ class Flag_complex_sparse_matrix { Vertex_handle v = target(edge, one_skeleton_graph); f_edge_vector_.push_back({{u, v}, boost::get(Gudhi::edge_filtration_t(), one_skeleton_graph, edge)}); } + } + + // Performs edge collapse in a decreasing sequence of the filtration value. + template + void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { + Row_index endIdx = 0; + + u_set_removed_redges_.clear(); + u_set_dominated_redges_.clear(); + critical_edge_indicator_.clear(); + + std::cout << "Sort it - " << f_edge_vector_.size() << std::endl; // Sort edges auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool { @@ -373,17 +397,9 @@ class Flag_complex_sparse_matrix { #else std::stable_sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); #endif - } - - // Performs edge collapse in a decreasing sequence of the filtration value. - template - void filtered_edge_collapse(FilteredEdgeInsertion filtered_edge_insert) { - Row_index endIdx = 0; - - u_set_removed_redges_.clear(); - u_set_dominated_redges_.clear(); - critical_edge_indicator_.clear(); + std::cout << "Sorted" << std::endl; + std::cout << vertices_.size() << std::endl; // Initializing sparse_row_adjacency_matrix_, This is a row-major sparse matrix. sparse_row_adjacency_matrix_ = Sparse_row_matrix(vertices_.size(), vertices_.size()); @@ -392,7 +408,7 @@ class Flag_complex_sparse_matrix { Edge edge = std::get<0>(fec); Vertex_handle u = std::get<0>(edge); Vertex_handle v = std::get<1>(edge); - Filtration_value filt = std::get<1>(fec); + Filtration filt = std::get<1>(fec); // Inserts the edge in the sparse matrix to update the graph (G_i) insert_new_edges(u, v, filt); diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 38adfa8a..3a07e088 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -11,6 +11,7 @@ #include #include #include +#include #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "collapse" @@ -32,7 +33,7 @@ bool find_edge_in_list(const Filtered_edge& edge, const Filtered_sorted_edge_lis } return false; } - +/* void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filtered_sorted_edge_list& removed_edges) { std::cout << "BEFORE COLLAPSE - Total number of edges: " << edges.size() << std::endl; BOOST_CHECK(edges.size() > 0); @@ -68,70 +69,104 @@ void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filt } BOOST_AUTO_TEST_CASE(collapse) { - /* - 1 2 - o---o - | | - | | - | | - o---o - 0 3 - */ + // 1 2 + // o---o + // | | + // | | + // | | + // o---o + // 0 3 Filtered_sorted_edge_list edges {{1., 0, 1}, {1., 1, 2}, {1., 2, 3}, {1., 3, 0}}; trace_and_check_collapse(edges, {}); - /* - 1 2 - o---o - |\ /| - | x | - |/ \| - o---o - 0 3 - */ + // 1 2 + // o---o + // |\ /| + // | x | + // |/ \| + // o---o + // 0 3 edges.push_back({2., 0, 2}); edges.push_back({2., 1, 3}); trace_and_check_collapse(edges, {{2., 1, 3}}); - /* - 1 2 4 - o---o---o - |\ /| | - | x | | - |/ \| | - o---o---o - 0 3 5 - */ + // 1 2 4 + // o---o---o + // |\ /| | + // | x | | + // |/ \| | + // o---o---o + // 0 3 5 edges.push_back({3., 2, 4}); edges.push_back({3., 4, 5}); edges.push_back({3., 5, 3}); trace_and_check_collapse(edges, {{2., 1, 3}}); - /* - 1 2 4 - o---o---o - |\ /|\ /| - | x | x | - |/ \|/ \| - o---o---o - 0 3 5 - */ + // 1 2 4 + // o---o---o + // |\ /|\ /| + // | x | x | + // |/ \|/ \| + // o---o---o + // 0 3 5 edges.push_back({4., 2, 5}); edges.push_back({4., 4, 3}); trace_and_check_collapse(edges, {{2., 1, 3}, {4., 4, 3}}); - /* - 1 2 4 - o---o---o - |\ /|\ /| - | x | x | + [0,4] and [1,5] - |/ \|/ \| - o---o---o - 0 3 5 - */ + // 1 2 4 + // o---o---o + // |\ /|\ /| + // | x | x | + [0,4] and [1,5] + // |/ \|/ \| + // o---o---o + // 0 3 5 edges.push_back({5., 1, 5}); edges.push_back({5., 0, 4}); trace_and_check_collapse(edges, {{2., 1, 3}, {4., 4, 3}, {5., 0, 4}}); -} +}*/ + + +BOOST_AUTO_TEST_CASE(collapse_from_distance_matrix) { + // 1 2 + // o---o + // |\ /| + // | x | + // |/ \| + // o---o + // 0 3 + // Lower diagonal distance matrix + std::array, 4> distance_matrix = {{{0., 0., 0., 0.}, + {1., 0., 0., 0.}, + {2., 1., 0., 0.}, + {1., 2., 1., 0.} }}; + + std::cout << "COLLAPSE - keep edges: " << std::endl; + Flag_complex_sparse_matrix flag_complex_sparse_matrix(distance_matrix); + Filtered_sorted_edge_list collapse_edges; + flag_complex_sparse_matrix.filtered_edge_collapse( + [&collapse_edges](std::pair edge, Filtration_value filtration) { + std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; + collapse_edges.push_back({filtration, std::get<0>(edge), std::get<1>(edge)}); + }); + std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; + BOOST_CHECK(collapse_edges.size() == 5); + Filtered_sorted_edge_list edges {{1., 0, 1}, {1., 1, 2}, {1., 2, 3}, {1., 0, 3}, {2., 0, 2}, {2., 1, 3}}; + + for (auto edge_from_collapse : collapse_edges) { + std::cout << "f[" << std::get<1>(edge_from_collapse) << ", " << std::get<2>(edge_from_collapse) << "] = " + << std::get<0>(edge_from_collapse) << std::endl; + // Check each edge from collapse is in the input + BOOST_CHECK(find_edge_in_list(edge_from_collapse, edges)); + } + Filtered_sorted_edge_list removed_edges {{2., 1, 3}}; + + std::cout << "CHECK COLLAPSE - Total number of removed edges: " << removed_edges.size() << std::endl; + for (auto removed_edge : removed_edges) { + std::cout << "f[" << std::get<1>(removed_edge) << ", " << std::get<2>(removed_edge) << "] = " + << std::get<0>(removed_edge) << std::endl; + // Check each removed edge from collapse is in the input + BOOST_CHECK(!find_edge_in_list(removed_edge, collapse_edges)); + } +} \ No newline at end of file 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 f6926224..f4a460ab 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -11,10 +11,8 @@ #include #include #include -#include -#include #include -#include +#include #include @@ -23,8 +21,8 @@ using Filtration_value = Simplex_tree::Filtration_value; using Vertex_handle = Simplex_tree::Vertex_handle; using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; +using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; -using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; using Distance_matrix = std::vector>; @@ -82,28 +80,22 @@ int main(int argc, char* argv[]) { program_options(argc, argv, csv_matrix_file, filediag, threshold, dim_max, p, min_persistence); Distance_matrix distances; - Distance_matrix sparse_distances; distances = Gudhi::read_lower_triangular_matrix_from_csv_file(csv_matrix_file); std::cout << "Read the distance matrix succesfully, of size: " << distances.size() << std::endl; - Flag_complex_sparse_matrix::Filtered_sorted_edge_list edge_t; - - Rips_edge_list Rips_edge_list_from_file(distances, threshold); - Rips_edge_list_from_file.create_edges(edge_t); - - if (edge_t.size() <= 0) { - std::cerr << "Total number of egdes are zero." << std::endl; - exit(-1); - } - - std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl; + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(boost::irange((size_t)0, + distances.size()), + threshold, + [&distances](size_t i, size_t j) { + return distances[j][i]; + }); // Now we will perform filtered edge collapse to sparsify the edge list edge_t. - Flag_complex_sparse_matrix mat_filt_edge_coll(edge_t); + Flag_complex_sparse_matrix flag_complex(proximity_graph); Simplex_tree stree; - mat_filt_edge_coll.filtered_edge_collapse( + flag_complex.filtered_edge_collapse( [&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.); 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 e322d3cd..b9130d4c 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -12,11 +12,9 @@ #include #include #include -#include #include #include -#include #include #include // for std::pair @@ -31,15 +29,12 @@ using Point = std::vector; using Vector_of_points = std::vector; using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; +using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; using Distance_matrix = std::vector>; -using Adjacency_list = boost::adjacency_list, - boost::property>; - void program_options(int argc, char* argv[], std::string& off_file_points, std::string& filediag, Filtration_value& threshold, int& dim_max, int& p, Filtration_value& min_persistence); @@ -76,9 +71,9 @@ int main(int argc, char* argv[]) { std::cout << "Successfully read " << point_vector.size() << " point_vector.\n"; std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; - Adjacency_list proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), - threshold, - Gudhi::Euclidean_distance()); + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), + threshold, + Gudhi::Euclidean_distance()); if (num_edges(proximity_graph) <= 0) { std::cerr << "Total number of egdes are zero." << std::endl; @@ -89,7 +84,7 @@ int main(int argc, char* argv[]) { Simplex_tree stree; mat_filt_edge_coll.filtered_edge_collapse( - [&stree](std::vector edge, Filtration_value filtration) { + [&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.); -- cgit v1.2.3 From 8c7eafebb4db99057820ddc226c5e9d55e95c31d Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Mon, 13 Apr 2020 11:44:29 +0200 Subject: Remove Rips_edge_list and review the interfaces --- .../include/gudhi/Flag_complex_sparse_matrix.h | 66 ++++---- src/Collapse/include/gudhi/Rips_edge_list.h | 184 --------------------- src/Collapse/test/collapse_unit_test.cpp | 159 ++++++++++-------- 3 files changed, 117 insertions(+), 292 deletions(-) delete mode 100644 src/Collapse/include/gudhi/Rips_edge_list.h (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index e90d284d..e225f7db 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -12,7 +12,6 @@ #ifndef FLAG_COMPLEX_SPARSE_MATRIX_H_ #define FLAG_COMPLEX_SPARSE_MATRIX_H_ -#include #include #include @@ -25,14 +24,14 @@ #endif #include -#include +#include // for std::pair #include -#include #include -#include -#include -#include - +#include +#include +#include // for std::tie +#include // for std::includes +#include // for std::inserter namespace Gudhi { @@ -48,28 +47,29 @@ namespace collapse { * A class to store the vertices v/s MaxSimplices Sparse Matrix and to perform collapse operations using the N^2() * Algorithm. * - * \tparam Vertex_handle type must be a signed integer type. It admits a total order <. + * \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 +template class Flag_complex_sparse_matrix { + public: + using Vertex_handle = Vertex; + using Filtration_value = Filtration; private: using Edge = std::pair; // This is an ordered pair, An edge is stored with convention of the first // element being the smaller i.e {2,3} not {3,2}. However this is at the level // of row indices on actual vertex lables - using Filtered_edge = std::pair; using Row_index = std::size_t; using Map_vertex_to_index = std::unordered_map; - using Sparse_row_matrix = Eigen::SparseMatrix; + using Sparse_row_matrix = Eigen::SparseMatrix; using Row_indices_vector = std::vector; public: - using Filtered_sorted_edge_list = std::vector>; - using Filtration_value = Filtration; + using Filtered_edge = std::pair; using Proximity_graph = Gudhi::Proximity_graph; private: @@ -113,7 +113,7 @@ class Flag_complex_sparse_matrix { //! Stores the Sparse matrix of Filtration values representing the Original Simplicial Complex. /*! \code - Sparse_row_matrix = Eigen::SparseMatrix ; + Sparse_row_matrix = Eigen::SparseMatrix ; \endcode ; */ @@ -206,7 +206,7 @@ class Flag_complex_sparse_matrix { } template - void set_edge_critical(Row_index indx, Filtration filt, FilteredEdgeInsertion filtered_edge_insert) { + void set_edge_critical(Row_index indx, Filtration_value filt, FilteredEdgeInsertion filtered_edge_insert) { #ifdef DEBUG_TRACES std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << std::endl; @@ -294,7 +294,7 @@ class Flag_complex_sparse_matrix { return common; } - void insert_vertex(Vertex_handle vertex, Filtration filt_val) { + void insert_vertex(Vertex_handle vertex, Filtration_value filt_val) { auto rw = vertex_to_row_.find(vertex); if (rw == vertex_to_row_.end()) { // Initializing the diagonal element of the adjency matrix corresponding to rw_b. @@ -306,7 +306,7 @@ class Flag_complex_sparse_matrix { } } - void insert_new_edges(Vertex_handle u, Vertex_handle v, Filtration filt_val) + void insert_new_edges(Vertex_handle u, Vertex_handle v, Filtration_value filt_val) { // The edge must not be added before, it should be a new edge. insert_vertex(u, filt_val); @@ -340,23 +340,16 @@ class Flag_complex_sparse_matrix { domination_indicator_ are initialised by init() function which is called at the begining of this.
*/ - template - Flag_complex_sparse_matrix(const DistanceMatrix& distance_matrix) - : rows(0) { - Vertex_handle num_vertices = std::distance(std::begin(distance_matrix), std::end(distance_matrix)); - - // This one is not part of the loop - vertices_.emplace(0); - // Only browse the lower part of the distance matrix - for (Vertex_handle line_index = 1; line_index < num_vertices; line_index++) { - for (Vertex_handle row_index = 0; row_index < line_index; row_index++) { -#ifdef DEBUG_TRACES - std::cout << "Insert edge: fn[" << row_index << ", " << line_index << "] = " - << distance_matrix[line_index][row_index] << std::endl; -#endif // DEBUG_TRACES - f_edge_vector_.push_back({{row_index, line_index}, distance_matrix[line_index][row_index]}); - } - vertices_.emplace(line_index); + template + Flag_complex_sparse_matrix(const Filtered_edge_range& filtered_edge_range) + : f_edge_vector_(filtered_edge_range.begin(), filtered_edge_range.end()), + rows(0) { + for (Filtered_edge filtered_edge : filtered_edge_range) { + Vertex_handle u; + Vertex_handle v; + std::tie(u,v) = std::get<0>(filtered_edge); + vertices_.emplace(u); + vertices_.emplace(v); } } @@ -385,7 +378,6 @@ class Flag_complex_sparse_matrix { u_set_dominated_redges_.clear(); critical_edge_indicator_.clear(); - std::cout << "Sort it - " << f_edge_vector_.size() << std::endl; // Sort edges auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool { @@ -397,9 +389,7 @@ class Flag_complex_sparse_matrix { #else std::stable_sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); #endif - std::cout << "Sorted" << std::endl; - std::cout << vertices_.size() << std::endl; // Initializing sparse_row_adjacency_matrix_, This is a row-major sparse matrix. sparse_row_adjacency_matrix_ = Sparse_row_matrix(vertices_.size(), vertices_.size()); @@ -408,7 +398,7 @@ class Flag_complex_sparse_matrix { Edge edge = std::get<0>(fec); Vertex_handle u = std::get<0>(edge); Vertex_handle v = std::get<1>(edge); - Filtration filt = std::get<1>(fec); + Filtration_value filt = std::get<1>(fec); // Inserts the edge in the sparse matrix to update the graph (G_i) insert_new_edges(u, v, filt); diff --git a/src/Collapse/include/gudhi/Rips_edge_list.h b/src/Collapse/include/gudhi/Rips_edge_list.h deleted file mode 100644 index b7c4dcff..00000000 --- a/src/Collapse/include/gudhi/Rips_edge_list.h +++ /dev/null @@ -1,184 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Clément Maria, Pawel Dlotko, Vincent Rouvreau Siddharth Pritam - * - * Copyright (C) 2016 INRIA - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef RIPS_edge_list_H_ -#define RIPS_edge_list_H_ - -#include -#include -#include - -#include -#include -#include -#include -#include // for numeric_limits -#include // for pair<> - - -namespace Gudhi { - -namespace rips_edge_list { - -/** - * \class Rips_complex - * \brief Rips complex data structure. - * - * \ingroup rips_complex - * - * \details - * The data structure is a one skeleton graph, or Rips graph, containing edges when the edge length is less or equal - * to a given threshold. Edge length is computed from a user given point cloud with a given distance function, or a - * distance matrix. - * - * \tparam Filtration_value is the type used to store the filtration values of the simplicial complex. - */ -template -class Rips_edge_list { - public: - /** - * \brief Type of the one skeleton graph stored inside the Rips complex structure. - */ - // typedef typename boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS - // , boost::property < vertex_filtration_t, Filtration_value > - // , boost::property < edge_filtration_t, Filtration_value >> OneSkeletonGraph; - - private: - typedef int Vertex_handle; - - public: - /** \brief Rips_complex constructor from a list of points. - * - * @param[in] points Range of points. - * @param[in] threshold Rips value. - * @param[in] distance distance function that returns a `Filtration_value` from 2 given points. - * - * \tparam ForwardPointRange must be a range for which `std::begin` and `std::end` return input iterators on a - * point. - * - * \tparam Distance furnishes `operator()(const Point& p1, const Point& p2)`, where - * `Point` is a point from the `ForwardPointRange`, and that returns a `Filtration_value`. - */ - template - Rips_edge_list(const ForwardPointRange& points, Filtration_value threshold, Distance distance) { - compute_proximity_graph(points, threshold, distance); - } - - /** \brief Rips_complex constructor from a distance matrix. - * - * @param[in] distance_matrix Range of distances. - * @param[in] threshold Rips value. - * - * \tparam DistanceMatrix must have a `size()` method and on which `distance_matrix[i][j]` returns - * the distance between points \f$i\f$ and \f$j\f$ as long as \f$ 0 \leqslant i < j \leqslant - * distance\_matrix.size().\f$ - */ - template - Rips_edge_list(const DistanceMatrix& distance_matrix, Filtration_value threshold) { - compute_proximity_graph(boost::irange((size_t)0, distance_matrix.size()), threshold, - [&](size_t i, size_t j){return distance_matrix[j][i];}); - } - - /** \brief Initializes the egde list (one skeleton) complex from the Rips graph - * - * \tparam EdgeListForRips must meet `EdgeListForRips` concept. - * - * @param[in] edges EdgeListForRips to be created. - * @param[in] dim_max graph expansion for Rips until this given maximal dimension. - * @exception std::invalid_argument In debug mode, if `edges.num_vertices()` does not return 0. - * - */ - template - void create_edges(EdgeListForRips& edge_list) { - GUDHI_CHECK(edges.num_vertices() == 0, - std::invalid_argument("Rips_complex::create_complex - edge list is not empty")); - - // sort the tuple (filteration_valuem, (v1,v2){edge}) - //By default the sort is done on the first element, so here it's filteration value. - std::sort(edges.begin(),edges.end()); - for(size_t i = 0; i < edges.size(); i++ ) - edge_list.emplace_back(edges.at(i)); - - } - - private: - /** \brief Computes the proximity graph of the points. - * - * If points contains n elements, the proximity graph is the graph with n vertices, and an edge [u,v] iff the - * distance function between points u and v is smaller than threshold. - * - * \tparam ForwardPointRange furnishes `.begin()` and `.end()` - * methods. - * - * \tparam Distance furnishes `operator()(const Point& p1, const Point& p2)`, where - * `Point` is a point from the `ForwardPointRange`, and that returns a `Filtration_value`. - */ - template< typename ForwardPointRange, typename Distance > - void compute_proximity_graph(const ForwardPointRange& points, Filtration_value threshold, - Distance distance) { - edges.clear(); - // Compute the proximity graph of the points. - // If points contains n elements, the proximity graph is the graph with n vertices, and an edge [u,v] iff the - // distance function between points u and v is smaller than threshold. - // -------------------------------------------------------------------------------------------- - // Creates the vector of edges and its filtration values (returned by distance function) - Vertex_handle idx_u = 0; - for (auto it_u = std::begin(points); it_u != std::end(points); ++it_u, ++idx_u) { - Vertex_handle idx_v = idx_u + 1; - for (auto it_v = it_u + 1; it_v != std::end(points); ++it_v, ++idx_v) { - Filtration_value fil = distance(*it_u, *it_v); - if (fil <= threshold) { - edges.emplace_back(fil, idx_u, idx_v); - } - } - } - - // -------------------------------------------------------------------------------------------- - // Creates the proximity graph from edges and sets the property with the filtration value. - // Number of points is labeled from 0 to idx_u-1 - // -------------------------------------------------------------------------------------------- - // Do not use : rips_skeleton_graph_ = OneSkeletonGraph(...) -> deep copy of the graph (boost graph is not - // move-enabled) - // rips_skeleton_graph_.~OneSkeletonGraph(); - // new(&rips_skeleton_graph_)OneSkeletonGraph(edges.begin(), edges.end(), edges_fil.begin(), idx_u); - - // auto vertex_prop = boost::get(vertex_filtration_t(), rips_skeleton_graph_); - - // using vertex_iterator = typename boost::graph_traits::vertex_iterator; - // vertex_iterator vi, vi_end; - // for (std::tie(vi, vi_end) = boost::vertices(rips_skeleton_graph_); - // vi != vi_end; ++vi) { - // boost::put(vertex_prop, *vi, 0.); - // } - } - - private: - // OneSkeletonGraph rips_skeleton_graph_; - std::vector< std::tuple < Filtration_value, Vertex_handle, Vertex_handle > > edges; - // std::vector< Filtration_value > edges_fil; -}; - -} // namespace rips_complex - -} // namespace Gudhi - -#endif // RIPS_COMPLEX_H_ diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 3a07e088..1bec3810 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -8,67 +8,77 @@ * - YYYY/MM Author: Description of the modification */ -#include -#include -#include -#include #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "collapse" #include #include -#include "gudhi/Flag_complex_sparse_matrix.h" +#include +#include +#include + +#include +#include +#include +#include +#include using Filtration_value = float; using Vertex_handle = short; -using Filtered_edge = std::tuple; -using Filtered_sorted_edge_list = std::vector; using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; +using Filtered_edge = Flag_complex_sparse_matrix::Filtered_edge; +using Filtered_edge_list = std::vector; -bool find_edge_in_list(const Filtered_edge& edge, const Filtered_sorted_edge_list& edge_list) { +template +bool find_edge_in_list(const Filtered_edge& edge, const Filtered_edge_range& edge_list) { for (auto edge_from_list : edge_list) { if (edge_from_list == edge) return true; } return false; } -/* -void trace_and_check_collapse(const Filtered_sorted_edge_list& edges, const Filtered_sorted_edge_list& removed_edges) { - std::cout << "BEFORE COLLAPSE - Total number of edges: " << edges.size() << std::endl; - BOOST_CHECK(edges.size() > 0); - for (auto edge : edges) { - std::cout << "f[" << std::get<1>(edge) << ", " << std::get<2>(edge) << "] = " << std::get<0>(edge) << std::endl; + +template +void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const Filtered_edge_list& removed_edges) { + 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 << "COLLAPSE - keep edges: " << std::endl; - Flag_complex_sparse_matrix flag_complex_sparse_matrix(edges); - Filtered_sorted_edge_list collapse_edges; + Flag_complex_sparse_matrix flag_complex_sparse_matrix(filtered_edges); + Filtered_edge_list collapse_edges; flag_complex_sparse_matrix.filtered_edge_collapse( [&collapse_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - collapse_edges.push_back({filtration, std::get<0>(edge), std::get<1>(edge)}); + collapse_edges.push_back({edge, filtration}); }); std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; - BOOST_CHECK(collapse_edges.size() <= edges.size()); - for (auto edge_from_collapse : collapse_edges) { - std::cout << "f[" << std::get<1>(edge_from_collapse) << ", " << std::get<2>(edge_from_collapse) << "] = " - << std::get<0>(edge_from_collapse) << std::endl; + BOOST_CHECK(collapse_edges.size() <= filtered_edges.size()); + for (auto filtered_edge_from_collapse : collapse_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; // Check each edge from collapse is in the input - BOOST_CHECK(find_edge_in_list(edge_from_collapse, edges)); + 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_edge : removed_edges) { - std::cout << "f[" << std::get<1>(removed_edge) << ", " << std::get<2>(removed_edge) << "] = " - << std::get<0>(removed_edge) << 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; // Check each removed edge from collapse is in the input - BOOST_CHECK(!find_edge_in_list(removed_edge, collapse_edges)); + BOOST_CHECK(!find_edge_in_list(removed_filtered_edge, collapse_edges)); } } BOOST_AUTO_TEST_CASE(collapse) { + std::cout << "***** COLLAPSE *****" << std::endl; // 1 2 // o---o // | | @@ -76,7 +86,7 @@ BOOST_AUTO_TEST_CASE(collapse) { // | | // o---o // 0 3 - Filtered_sorted_edge_list edges {{1., 0, 1}, {1., 1, 2}, {1., 2, 3}, {1., 3, 0}}; + Filtered_edge_list edges {{{0, 1}, 1.}, {{1, 2}, 1.}, {{2, 3}, 1.}, {{3, 0}, 1.}}; trace_and_check_collapse(edges, {}); // 1 2 @@ -86,9 +96,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| // o---o // 0 3 - edges.push_back({2., 0, 2}); - edges.push_back({2., 1, 3}); - trace_and_check_collapse(edges, {{2., 1, 3}}); + edges.push_back({{0, 2}, 2.}); + edges.push_back({{1, 3}, 2.}); + trace_and_check_collapse(edges, {{{1, 3}, 2.}}); // 1 2 4 // o---o---o @@ -97,10 +107,10 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \| | // o---o---o // 0 3 5 - edges.push_back({3., 2, 4}); - edges.push_back({3., 4, 5}); - edges.push_back({3., 5, 3}); - trace_and_check_collapse(edges, {{2., 1, 3}}); + edges.push_back({{2, 4}, 3.}); + edges.push_back({{4, 5}, 3.}); + edges.push_back({{5, 3}, 3.}); + trace_and_check_collapse(edges, {{{1, 3}, 2.}}); // 1 2 4 // o---o---o @@ -109,9 +119,9 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.push_back({4., 2, 5}); - edges.push_back({4., 4, 3}); - trace_and_check_collapse(edges, {{2., 1, 3}, {4., 4, 3}}); + edges.push_back({{2, 5}, 4.}); + edges.push_back({{4, 3}, 4.}); + trace_and_check_collapse(edges, {{{1, 3}, 2.}, {{4, 3}, 4.}}); // 1 2 4 // o---o---o @@ -120,13 +130,27 @@ BOOST_AUTO_TEST_CASE(collapse) { // |/ \|/ \| // o---o---o // 0 3 5 - edges.push_back({5., 1, 5}); - edges.push_back({5., 0, 4}); - trace_and_check_collapse(edges, {{2., 1, 3}, {4., 4, 3}, {5., 0, 4}}); -}*/ + edges.push_back({{1, 5}, 5.}); + edges.push_back({{0, 4}, 5.}); + trace_and_check_collapse(edges, {{{1, 3}, 2.}, {{4, 3}, 4.}, {{0, 4}, 5.}}); +} + +BOOST_AUTO_TEST_CASE(collapse_from_array) { + std::cout << "***** COLLAPSE FROM ARRAY *****" << std::endl; + // 1 2 + // o---o + // |\ /| + // | x | + // |/ \| + // 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.}}); +} -BOOST_AUTO_TEST_CASE(collapse_from_distance_matrix) { +BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { + std::cout << "***** COLLAPSE FROM PROXIMITY GRAPH *****" << std::endl; // 1 2 // o---o // |\ /| @@ -134,39 +158,34 @@ BOOST_AUTO_TEST_CASE(collapse_from_distance_matrix) { // |/ \| // o---o // 0 3 - // Lower diagonal distance matrix - std::array, 4> distance_matrix = {{{0., 0., 0., 0.}, - {1., 0., 0., 0.}, - {2., 1., 0., 0.}, - {1., 2., 1., 0.} }}; - - std::cout << "COLLAPSE - keep edges: " << std::endl; - Flag_complex_sparse_matrix flag_complex_sparse_matrix(distance_matrix); - Filtered_sorted_edge_list collapse_edges; + std::vector> point_cloud = {{0., 0.}, + {0., 1.}, + {1., 0.}, + {1., 1.} }; + + Filtration_value threshold = std::numeric_limits::infinity(); + using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, + threshold, + Gudhi::Euclidean_distance()); + Flag_complex_sparse_matrix flag_complex_sparse_matrix(proximity_graph); + Filtered_edge_list collapse_edges; flag_complex_sparse_matrix.filtered_edge_collapse( [&collapse_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - collapse_edges.push_back({filtration, std::get<0>(edge), std::get<1>(edge)}); + collapse_edges.push_back({edge, filtration}); }); - std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; BOOST_CHECK(collapse_edges.size() == 5); - Filtered_sorted_edge_list edges {{1., 0, 1}, {1., 1, 2}, {1., 2, 3}, {1., 0, 3}, {2., 0, 2}, {2., 1, 3}}; - - for (auto edge_from_collapse : collapse_edges) { - std::cout << "f[" << std::get<1>(edge_from_collapse) << ", " << std::get<2>(edge_from_collapse) << "] = " - << std::get<0>(edge_from_collapse) << std::endl; - // Check each edge from collapse is in the input - BOOST_CHECK(find_edge_in_list(edge_from_collapse, edges)); - } - - Filtered_sorted_edge_list removed_edges {{2., 1, 3}}; - - std::cout << "CHECK COLLAPSE - Total number of removed edges: " << removed_edges.size() << std::endl; - for (auto removed_edge : removed_edges) { - std::cout << "f[" << std::get<1>(removed_edge) << ", " << std::get<2>(removed_edge) << "] = " - << std::get<0>(removed_edge) << std::endl; - // Check each removed edge from collapse is in the input - BOOST_CHECK(!find_edge_in_list(removed_edge, collapse_edges)); + std::size_t filtration_is_edge_length_nb = 0; + std::size_t filtration_is_diagonal_length_nb = 0; + float epsilon = std::numeric_limits::epsilon(); + for (auto filtered_edge : collapse_edges) { + if (std::get<1>(filtered_edge) == 1.) + filtration_is_edge_length_nb++; + if (std::fabs(std::get<1>(filtered_edge) - std::sqrt(2.)) <= epsilon) + filtration_is_diagonal_length_nb++; } + 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 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 --- src/Collapse/doc/intro_edge_collapse.h | 6 +- .../example/edge_collapse_basic_example.cpp | 12 +- .../example/edge_collapse_conserve_persistence.cpp | 10 +- .../include/gudhi/Flag_complex_edge_collapser.h | 358 +++++++++++++++++++++ .../include/gudhi/Flag_complex_sparse_matrix.h | 358 --------------------- src/Collapse/test/collapse_unit_test.cpp | 18 +- ...tance_matrix_edge_collapse_rips_persistence.cpp | 10 +- .../point_cloud_edge_collapse_rips_persistence.cpp | 10 +- 8 files changed, 391 insertions(+), 391 deletions(-) create mode 100644 src/Collapse/include/gudhi/Flag_complex_edge_collapser.h delete mode 100644 src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h index 15f2208c..2b272a9e 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_sparse_matrix` from a proximity graph represented as a list of - * `Flag_complex_sparse_matrix::Filtered_edge`. - * Then it collapses edges and displays a new list of `Flag_complex_sparse_matrix::Filtered_edge` (with less edges) + * 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) * 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 a154c6bb..333bc231 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include @@ -7,10 +7,10 @@ int main() { // Type definitions using Filtration_value = float; using Vertex_handle = short; - using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; - using Filtered_edge = Flag_complex_sparse_matrix::Filtered_edge; + 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_sparse_matrix::Edge; + using Edge = Flag_complex_edge_collapser::Edge; // 1 2 // o---o @@ -26,11 +26,11 @@ int main() { {{0, 2}, 2.}, {{1, 3}, 2.}}; - Flag_complex_sparse_matrix flag_complex_sparse_matrix(graph); + Flag_complex_edge_collapser edge_collapser(graph); Filtered_edge_list collapse_edges; // Retrieve collapse edges from the output iterator - flag_complex_sparse_matrix.filtered_edge_collapse( + edge_collapser.process_edges( [&collapse_edges](std::pair edge, Filtration_value filtration) { collapse_edges.push_back({edge, filtration}); }); diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index 9c561efc..701ea1af 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -8,7 +8,7 @@ * - YYYY/MM Author: Description of the modification */ -#include +#include #include #include #include @@ -27,8 +27,8 @@ using Vertex_handle = Simplex_tree::Vertex_handle; using Point = std::vector; using Vector_of_points = std::vector; -using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; -using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; +using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; +using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -112,14 +112,14 @@ int main(int argc, char* argv[]) { int ambient_dim = point_vector[0].size(); // ***** Simplex tree from a flag complex built after collapse ***** - Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); + Flag_complex_edge_collapser edge_collapser(proximity_graph); Simplex_tree stree_from_collapse; for (Vertex_handle vertex = 0; static_cast(vertex) < point_vector.size(); vertex++) { // insert the vertex with a 0. filtration value just like a Rips stree_from_collapse.insert_simplex({vertex}, 0.); } - mat_filt_edge_coll.filtered_edge_collapse( + edge_collapser.process_edges( [&stree_from_collapse](const std::vector& edge, Filtration_value filtration) { // insert the edge stree_from_collapse.insert_simplex(edge, filtration); 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_ diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h deleted file mode 100644 index 4402523f..00000000 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ /dev/null @@ -1,358 +0,0 @@ -/* 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_SPARSE_MATRIX_H_ -#define FLAG_COMPLEX_SPARSE_MATRIX_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_sparse_matrix - * \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_sparse_matrix { - 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_sparse_matrix. */ - 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_sparse_matrix::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_sparse_matrix constructor from a range of filtered edges. - * - * @param[in] filtered_edge_range Range of filtered edges. Filtered edges must be in - * `Flag_complex_sparse_matrix::Filtered_edge`. - * - * There is no need the range to be sorted, as it will be performed in - * `Flag_complex_sparse_matrix::filtered_edge_collapse`. - */ - template - Flag_complex_sparse_matrix(const Filtered_edge_range& filtered_edge_range) - : f_edge_vector_(filtered_edge_range.begin(), filtered_edge_range.end()) { } - - /** \brief Flag_complex_sparse_matrix 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_sparse_matrix::Proximity_graph`. - * - * The constructor is computing and filling a vector of `Flag_complex_sparse_matrix::Filtered_edge` - */ - Flag_complex_sparse_matrix(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 filtered_edge_collapse(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_SPARSE_MATRIX_H_ diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 1bec3810..e45dc339 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -14,7 +14,7 @@ #include #include -#include +#include #include #include @@ -26,8 +26,8 @@ using Filtration_value = float; using Vertex_handle = short; -using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; -using Filtered_edge = Flag_complex_sparse_matrix::Filtered_edge; +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; template @@ -49,9 +49,9 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F } std::cout << "COLLAPSE - keep edges: " << std::endl; - Flag_complex_sparse_matrix flag_complex_sparse_matrix(filtered_edges); + Flag_complex_edge_collapser edge_collapser(filtered_edges); Filtered_edge_list collapse_edges; - flag_complex_sparse_matrix.filtered_edge_collapse( + edge_collapser.process_edges( [&collapse_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; collapse_edges.push_back({edge, filtration}); @@ -164,13 +164,13 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { {1., 1.} }; Filtration_value threshold = std::numeric_limits::infinity(); - using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; - Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, + using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, threshold, Gudhi::Euclidean_distance()); - Flag_complex_sparse_matrix flag_complex_sparse_matrix(proximity_graph); + Flag_complex_edge_collapser edge_collapser(proximity_graph); Filtered_edge_list collapse_edges; - flag_complex_sparse_matrix.filtered_edge_collapse( + edge_collapser.process_edges( [&collapse_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; collapse_edges.push_back({edge, 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 7201a6b4..ae9ff32b 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -8,7 +8,7 @@ * - YYYY/MM Author: Description of the modification */ -#include +#include #include #include #include @@ -20,8 +20,8 @@ using Simplex_tree = Gudhi::Simplex_tree; -using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; +using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; +using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -90,14 +90,14 @@ int main(int argc, char* argv[]) { }); // Now we will perform filtered edge collapse to sparsify the edge list edge_t. - Flag_complex_sparse_matrix flag_complex(proximity_graph); + Flag_complex_edge_collapser edge_collapser(proximity_graph); Simplex_tree stree; for (Vertex_handle vertex = 0; static_cast(vertex) < distances.size(); vertex++) { // insert the vertex with a 0. filtration value just like a Rips stree.insert_simplex({vertex}, 0.); } - flag_complex.filtered_edge_collapse( + 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.); 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 19f083c4..d2d31013 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -8,7 +8,7 @@ * - YYYY/MM Author: Description of the modification */ -#include +#include #include #include #include @@ -28,8 +28,8 @@ using Vertex_handle = Simplex_tree::Vertex_handle; using Point = std::vector; using Vector_of_points = std::vector; -using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; -using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; +using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; +using Proximity_graph = Flag_complex_edge_collapser::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -77,14 +77,14 @@ int main(int argc, char* argv[]) { exit(-1); } - Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); + Flag_complex_edge_collapser edge_collapser(proximity_graph); Simplex_tree stree; for (Vertex_handle vertex = 0; static_cast(vertex) < point_vector.size(); vertex++) { // insert the vertex with a 0. filtration value just like a Rips stree.insert_simplex({vertex}, 0.); } - mat_filt_edge_coll.filtered_edge_collapse( + 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.); -- 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/test/collapse_unit_test.cpp') 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 0a9cadf43cf61107b6064f368f61b58db153609a Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 18 Jun 2020 10:39:24 +0200 Subject: Code review: rename collapse_edges as remaining_edges --- .../example/edge_collapse_basic_example.cpp | 8 ++++---- src/Collapse/test/collapse_unit_test.cpp | 24 +++++++++++----------- 2 files changed, 16 insertions(+), 16 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp index 568115f5..17ed04a2 100644 --- a/src/Collapse/example/edge_collapse_basic_example.cpp +++ b/src/Collapse/example/edge_collapse_basic_example.cpp @@ -28,14 +28,14 @@ int main() { Flag_complex_edge_collapser edge_collapser(graph.begin(), graph.end()); - Filtered_edge_list collapse_edges; + Filtered_edge_list remaining_edges; // Retrieve collapse edges from the output iterator edge_collapser.process_edges( - [&collapse_edges](std::pair edge, Filtration_value filtration) { - collapse_edges.push_back({edge, filtration}); + [&remaining_edges](std::pair edge, Filtration_value filtration) { + remaining_edges.push_back({edge, filtration}); }); - for (Filtered_edge filtered_edge_from_collapse : collapse_edges) { + 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; diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index 3733ba13..6ca49299 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -50,15 +50,15 @@ 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()); - Filtered_edge_list collapse_edges; + Filtered_edge_list remaining_edges; edge_collapser.process_edges( - [&collapse_edges](std::pair edge, Filtration_value filtration) { + [&remaining_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - collapse_edges.push_back({edge, filtration}); + remaining_edges.push_back({edge, filtration}); }); - std::cout << "AFTER COLLAPSE - Total number of edges: " << collapse_edges.size() << std::endl; - BOOST_CHECK(collapse_edges.size() <= filtered_edges.size()); - for (auto filtered_edge_from_collapse : collapse_edges) { + 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; @@ -72,7 +72,7 @@ void trace_and_check_collapse(const Filtered_edge_range& filtered_edges, const F std::cout << "f[" << std::get<0>(removed_edge) << ", " << std::get<1>(removed_edge) << "] = " << std::get<1>(removed_filtered_edge) << std::endl; // Check each removed edge from collapse is in the input - BOOST_CHECK(!find_edge_in_list(removed_filtered_edge, collapse_edges)); + BOOST_CHECK(!find_edge_in_list(removed_filtered_edge, remaining_edges)); } } @@ -169,18 +169,18 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { threshold, Gudhi::Euclidean_distance()); Flag_complex_edge_collapser edge_collapser(proximity_graph); - Filtered_edge_list collapse_edges; + Filtered_edge_list remaining_edges; edge_collapser.process_edges( - [&collapse_edges](std::pair edge, Filtration_value filtration) { + [&remaining_edges](std::pair edge, Filtration_value filtration) { std::cout << "f[" << std::get<0>(edge) << ", " << std::get<1>(edge) << "] = " << filtration << std::endl; - collapse_edges.push_back({edge, filtration}); + remaining_edges.push_back({edge, filtration}); }); - BOOST_CHECK(collapse_edges.size() == 5); + BOOST_CHECK(remaining_edges.size() == 5); std::size_t filtration_is_edge_length_nb = 0; std::size_t filtration_is_diagonal_length_nb = 0; float epsilon = std::numeric_limits::epsilon(); - for (auto filtered_edge : collapse_edges) { + for (auto filtered_edge : remaining_edges) { if (std::get<1>(filtered_edge) == 1.) filtration_is_edge_length_nb++; if (std::fabs(std::get<1>(filtered_edge) - std::sqrt(2.)) <= epsilon) -- 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/test/collapse_unit_test.cpp') 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/test/collapse_unit_test.cpp') 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 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/test/collapse_unit_test.cpp') 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 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/test/collapse_unit_test.cpp') 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 8ccc304db8b118466dff3c3068f6884ba198dc97 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 26 Jun 2020 19:02:56 +0200 Subject: Use free functions for tests and examples --- .../example/edge_collapse_conserve_persistence.cpp | 18 +++---- src/Collapse/test/collapse_unit_test.cpp | 58 ++++++++++------------ 2 files changed, 33 insertions(+), 43 deletions(-) (limited to 'src/Collapse/test/collapse_unit_test.cpp') diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index e6672d25..b2c55e7a 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -29,8 +29,7 @@ using Vertex_handle = Simplex_tree::Vertex_handle; using Point = std::vector; using Vector_of_points = std::vector; -using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; -using Proximity_graph = Gudhi::Proximity_graph; +using Proximity_graph = Gudhi::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -111,10 +110,10 @@ 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( + auto remaining_edges = Gudhi::collapse::flag_complex_collapse_edges( boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ - return std::make_tuple(source(edge, proximity_graph), - target(edge, proximity_graph), + return std::make_tuple(static_cast(source(edge, proximity_graph)), + static_cast(target(edge, proximity_graph)), get(Gudhi::edge_filtration_t(), proximity_graph, edge)); }) ); @@ -124,11 +123,10 @@ int main(int argc, char* argv[]) { // insert the vertex with a 0. filtration value just like a Rips stree_from_collapse.insert_simplex({vertex}, 0.); } - edge_collapser.process_edges( - [&stree_from_collapse](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { - // insert the edge - stree_from_collapse.insert_simplex({u, v}, filtration); - }); + for (auto remaining_edge : remaining_edges) { + stree_from_collapse.insert_simplex({std::get<0>(remaining_edge), std::get<1>(remaining_edge)}, + std::get<2>(remaining_edge)); + } std::vector persistence_intervals_from_collapse = get_persistence_intervals(stree_from_collapse, ambient_dim); diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index b5ad09c5..b8876246 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -25,10 +25,14 @@ #include #include -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; +struct Simplicial_complex { + using Vertex_handle = short; + using Filtration_value = float; +}; + +using Vertex_handle = Simplicial_complex::Vertex_handle; +using Filtration_value = Simplicial_complex::Filtration_value; +using Filtered_edge = std::tuple; using Filtered_edge_list = std::vector; template @@ -50,13 +54,8 @@ 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); - Filtered_edge_list remaining_edges; - 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(u, v, filtration); - }); + auto remaining_edges = Gudhi::collapse::flag_complex_collapse_edges(filtered_edges); + 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) { @@ -155,7 +154,6 @@ BOOST_AUTO_TEST_CASE(collapse_from_array) { trace_and_check_collapse(f_edge_array, {{1, 3, 2.}}); } - BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { std::cout << "***** COLLAPSE FROM PROXIMITY GRAPH *****" << std::endl; // 1 2 @@ -166,30 +164,24 @@ BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { // o---o // 0 3 std::vector> point_cloud = {{0., 0.}, - {0., 1.}, - {1., 0.}, - {1., 1.} }; + {0., 1.}, + {1., 0.}, + {1., 1.} }; Filtration_value threshold = std::numeric_limits::infinity(); - using Proximity_graph = Gudhi::Proximity_graph; - Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, - threshold, - Gudhi::Euclidean_distance()); - - 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)); + using Proximity_graph = Gudhi::Proximity_graph; + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_cloud, + threshold, + Gudhi::Euclidean_distance()); + + auto remaining_edges = Gudhi::collapse::flag_complex_collapse_edges( + boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ + return std::make_tuple(static_cast(source(edge, proximity_graph)), + static_cast(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) { - std::cout << "f[" << u << ", " << v << "] = " << filtration << std::endl; - remaining_edges.emplace_back(u, v, filtration); - }); + ); + BOOST_CHECK(remaining_edges.size() == 5); std::size_t filtration_is_edge_length_nb = 0; -- cgit v1.2.3