From 1fdaa406b6b0b85e409bd97090098ed5846c078c Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 22 Jun 2020 23:17:58 +0200 Subject: Don't explicitly copy the neighbors to a vector each time --- .../include/gudhi/Flag_complex_edge_collapser.h | 78 ++++++++++++++-------- 1 file changed, 49 insertions(+), 29 deletions(-) (limited to 'src/Collapse/include') diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 220330a7..09986d08 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -17,6 +17,7 @@ #include #include +#include #include @@ -70,6 +71,48 @@ class Flag_complex_edge_collapser { using Sparse_vector = Eigen::SparseVector; using Sparse_row_matrix = std::vector; + // Range of neighbors of a vertex + template + struct Neighbours { + class iterator : public boost::iterator_facade + { + public: + iterator():ptr(nullptr){} + iterator(Neighbours const*p):ptr(p){find_valid();} + private: + friend class boost::iterator_core_access; + Neighbours const*ptr; + void increment(){ + ++ptr->it; + find_valid(); + } + void find_valid(){ + auto& it = ptr->it; + do { + if(!it) { ptr=nullptr; break; } + if(IVertex(it.index()) == ptr->u) { + if(closed) break; + else continue; + } + Edge_index e = it.value(); + if(e <= ptr->ec->current_backward || ptr->ec->critical_edge_indicator_[e]) break; + } while(++it, true); + } + bool equal(iterator const& other) const { return ptr == other.ptr; } + IVertex dereference() const { return ptr->it.index(); } + }; + typedef iterator const_iterator; + mutable typename Sparse_vector::InnerIterator it; + Flag_complex_edge_collapser const*ec; + IVertex u; + iterator begin() const { return this; } + iterator end() const { return {}; } + explicit Neighbours(Flag_complex_edge_collapser const*p,IVertex u):it(p->sparse_row_adjacency_matrix_[u]),ec(p),u(u){} + }; + // A range of row indices using IVertex_vector = std::vector; @@ -121,7 +164,7 @@ class Flag_complex_edge_collapser { return true; else for (auto rw_c : common_neighbours) { - auto neighbours_c = neighbours_row_index(rw_c, true); + auto neighbours_c = neighbours_row_index(rw_c); // If neighbours_c contains the common neighbours. if (std::includes(neighbours_c.begin(), neighbours_c.end(), common_neighbours.begin(), common_neighbours.end())) @@ -193,41 +236,18 @@ class Flag_complex_edge_collapser { } // Returns list of neighbors of a particular vertex. - IVertex_vector neighbours_row_index(IVertex rw_u, bool closed) const + template + auto neighbours_row_index(IVertex rw_u) const { - IVertex_vector neighbors; - neighbors.reserve(sparse_row_adjacency_matrix_[rw_u].nonZeros()); // too much, but who cares -#ifdef DEBUG_TRACES - std::cout << "The neighbours of the vertex: " << row_to_vertex_[rw_u] << " are. " << std::endl; -#endif // DEBUG_TRACES - // Iterate over the neighbors - for (typename Sparse_vector::InnerIterator it(sparse_row_adjacency_matrix_[rw_u]); it; ++it) { - IVertex rw_v = it.index(); - if (!closed && rw_u == rw_v) continue; - Edge_index ei; - // If the vertex v is not dominated and the edge {u,v} is still in the matrix - if ((closed && rw_u == rw_v) || - (ei = it.value()) <= current_backward || - critical_edge_indicator_[ei]) { - neighbors.emplace_back(rw_v); -#ifdef DEBUG_TRACES - std::cout << row_to_vertex_[rw_v] << ", " ; -#endif // DEBUG_TRACES - } - } -#ifdef DEBUG_TRACES - std::cout << std::endl; -#endif // DEBUG_TRACES - return neighbors; + return Neighbours(this, rw_u); } // Returns the list of open neighbours of the edge :{u,v}. IVertex_vector open_common_neighbours_row_index(IVertex rw_u, IVertex rw_v) const { - IVertex_vector non_zero_indices_u = neighbours_row_index(rw_u, false); - IVertex_vector non_zero_indices_v = neighbours_row_index(rw_v, false); + auto non_zero_indices_u = neighbours_row_index(rw_u); + auto non_zero_indices_v = neighbours_row_index(rw_v); IVertex_vector common; - common.reserve(std::min(non_zero_indices_u.size(), non_zero_indices_v.size())); std::set_intersection(non_zero_indices_u.begin(), non_zero_indices_u.end(), non_zero_indices_v.begin(), non_zero_indices_v.end(), std::back_inserter(common)); -- cgit v1.2.3 From e4e55054945ec25bba613bf9051b9dde0b09357e Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Tue, 23 Jun 2020 00:00:58 +0200 Subject: Fix uses of emplace_back --- .../example/edge_collapse_basic_example.cpp | 2 +- .../example/edge_collapse_conserve_persistence.cpp | 6 +++--- .../include/gudhi/Flag_complex_edge_collapser.h | 6 +++--- src/Collapse/test/collapse_unit_test.cpp | 24 +++++++++++----------- 4 files changed, 19 insertions(+), 19 deletions(-) (limited to 'src/Collapse/include') 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