From e0c930251736ab31732787c4d94761e33f31ff4d Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 20 Nov 2017 16:03:08 +0000 Subject: Add upper_bound_dimension and associated documentation for automatic dimension set. prune_above_filtration cythonization git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/set_dimension_mechanism_precision@2917 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 12af3c5c2d6012c43d80cc95e1ecc8a2c0df340e --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 7da767cb..eef710e1 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -761,8 +761,12 @@ class Simplex_tree { return &root_; } - /** Set a dimension for the simplicial complex. */ + /** \brief Set a dimension for the simplicial complex. + * \details This function must be used with caution because it disables dimension recomputation when required + * (this recomputation can be triggered by `remove_maximal_simplex()` or `prune_above_filtration()`). + */ void set_dimension(int dimension) { + dimension_to_be_lowered_ = false; dimension_ = dimension; } -- cgit v1.2.3 From fbcb92c5b210d62d0a71e4001e51bc4ea3e81662 Mon Sep 17 00:00:00 2001 From: glisse Date: Mon, 20 Nov 2017 21:40:54 +0000 Subject: Copy the doc from FilteredComplex::simplex to the Simplex_tree. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-doc-simplex@2920 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0323c23e4cd46f79439f477475df4273847aafc2 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 7da767cb..836e0612 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -391,13 +391,13 @@ class Simplex_tree { return sh->second.key(); } - /** \brief Returns the simplex associated to a key. + /** \brief Returns the simplex that has index idx in the filtration. * * The filtration must be initialized. * \pre SimplexTreeOptions::store_key */ - Simplex_handle simplex(Simplex_key key) const { - return filtration_vect_[key]; + Simplex_handle simplex(Simplex_key idx) const { + return filtration_vect_[idx]; } /** \brief Returns the filtration value of a simplex. -- cgit v1.2.3 From 9b05f9dadd25f2a5f1051044b2e00ebfc6e9b0a5 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Wed, 22 Nov 2017 09:57:46 +0000 Subject: Merge graph_expansion_blocker fix from cech_complex branch git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@2932 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c6397609dbf92cad0fdd6c0fc5365b96657edec9 --- .../example/rips_persistence_step_by_step.cpp | 59 +----- src/Simplex_tree/example/CMakeLists.txt | 10 + .../example/cech_complex_cgal_mini_sphere_3d.cpp | 234 +++++++++++++++++++++ src/Simplex_tree/include/gudhi/Simplex_tree.h | 26 ++- .../include/gudhi/graph_simplicial_complex.h | 63 ++++++ 5 files changed, 323 insertions(+), 69 deletions(-) create mode 100644 src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp b/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp index 554eeba6..c1de0ef8 100644 --- a/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp +++ b/src/Persistent_cohomology/example/rips_persistence_step_by_step.cpp @@ -45,14 +45,7 @@ using Simplex_tree = Gudhi::Simplex_tree; using Vertex_handle = Simplex_tree::Vertex_handle; using Filtration_value = Simplex_tree::Filtration_value; -using Graph_t = boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS -, boost::property < vertex_filtration_t, Filtration_value > -, boost::property < edge_filtration_t, Filtration_value > ->; -using Edge_t = std::pair< Vertex_handle, Vertex_handle >; - -template< typename InputPointRange, typename Distance > -Graph_t compute_proximity_graph(InputPointRange &points, Filtration_value threshold, Distance distance); +using Proximity_graph = Gudhi::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; @@ -81,8 +74,9 @@ int main(int argc, char * argv[]) { Points_off_reader off_reader(off_file_points); // Compute the proximity graph of the points - Graph_t prox_graph = compute_proximity_graph(off_reader.get_point_cloud(), threshold - , Gudhi::Euclidean_distance()); + Proximity_graph prox_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), + threshold, + Gudhi::Euclidean_distance()); // Construct the Rips complex in a Simplex Tree Simplex_tree st; @@ -170,48 +164,3 @@ void program_options(int argc, char * argv[] std::abort(); } } - -/** Output 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. - * - * The type PointCloud furnishes .begin() and .end() methods, that return - * iterators with value_type Point. - */ -template< typename InputPointRange, typename Distance > -Graph_t compute_proximity_graph(InputPointRange &points, Filtration_value threshold, Distance distance) { - std::vector< Edge_t > edges; - std::vector< Filtration_value > edges_fil; - - Vertex_handle idx_u, idx_v; - Filtration_value fil; - idx_u = 0; - for (auto it_u = points.begin(); it_u != points.end(); ++it_u) { - idx_v = idx_u + 1; - for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) { - fil = distance(*it_u, *it_v); - if (fil <= threshold) { - edges.emplace_back(idx_u, idx_v); - edges_fil.push_back(fil); - } - } - ++idx_u; - } - - Graph_t skel_graph(edges.begin() - , edges.end() - , edges_fil.begin() - , idx_u); // number of points labeled from 0 to idx_u-1 - - auto vertex_prop = boost::get(vertex_filtration_t(), skel_graph); - - boost::graph_traits::vertex_iterator vi, vi_end; - for (std::tie(vi, vi_end) = boost::vertices(skel_graph); - vi != vi_end; ++vi) { - boost::put(vertex_prop, *vi, 0.); - } - - return skel_graph; -} diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt index 8bc4ad53..b33b2d05 100644 --- a/src/Simplex_tree/example/CMakeLists.txt +++ b/src/Simplex_tree/example/CMakeLists.txt @@ -34,6 +34,16 @@ if(GMP_FOUND AND CGAL_FOUND) "${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off") install(TARGETS Simplex_tree_example_alpha_shapes_3_from_off DESTINATION bin) + + add_executable ( Simplex_tree_example_cech_complex_cgal_mini_sphere_3d cech_complex_cgal_mini_sphere_3d.cpp ) + target_link_libraries(Simplex_tree_example_cech_complex_cgal_mini_sphere_3d ${Boost_PROGRAM_OPTIONS_LIBRARY} ${CGAL_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(Simplex_tree_example_cech_complex_cgal_mini_sphere_3d ${TBB_LIBRARIES}) + endif() + add_test(NAME Simplex_tree_example_cech_complex_cgal_mini_sphere_3d COMMAND $ + "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" -r 0.3 -d 3) + + install(TARGETS Simplex_tree_example_alpha_shapes_3_from_off DESTINATION bin) endif() add_executable ( Simplex_tree_example_graph_expansion_with_blocker graph_expansion_with_blocker.cpp ) diff --git a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp new file mode 100644 index 00000000..217e251f --- /dev/null +++ b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp @@ -0,0 +1,234 @@ +/* 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 + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (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 . + */ + +#include +#include +#include +#include + +#include +#include +#include + +#include + +#include +#include +#include // infinity +#include // for pair +#include + +// ------------------------------------------------------------------------------- +// cech_complex_cgal_mini_sphere_3d is an example of each step that is required to +// build a Cech over a Simplex_tree. Please refer to cech_persistence to see +// how to do the same thing with the Cech_complex wrapper for less detailed +// steps. +// ------------------------------------------------------------------------------- + +// Types definition +using Simplex_tree = Gudhi::Simplex_tree<>; +using Vertex_handle = Simplex_tree::Vertex_handle; +using Simplex_handle = Simplex_tree::Simplex_handle; +using Filtration_value = Simplex_tree::Filtration_value; +using Siblings = Simplex_tree::Siblings; +using Graph_t = boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS +, boost::property < Gudhi::vertex_filtration_t, Filtration_value > +, boost::property < Gudhi::edge_filtration_t, Filtration_value > +>; +using Edge_t = std::pair< Vertex_handle, Vertex_handle >; + +using Kernel = CGAL::Epick_d< CGAL::Dimension_tag<3> >; +using Point = Kernel::Point_d; +using Traits = CGAL::Min_sphere_of_points_d_traits_d; +using Min_sphere = CGAL::Min_sphere_of_spheres_d; + +using Points_off_reader = Gudhi::Points_off_reader; + +class Cech_blocker { + public: + bool operator()(Simplex_handle sh) { + std::vector points; +#if DEBUG_TRACES + std::cout << "Cech_blocker on ["; +#endif // DEBUG_TRACES + for (auto vertex : simplex_tree_.simplex_vertex_range(sh)) { + points.push_back(point_cloud_[vertex]); +#if DEBUG_TRACES + std::cout << vertex << ", "; +#endif // DEBUG_TRACES + } + Min_sphere ms(points.begin(),points.end()); + Filtration_value radius = ms.radius(); +#if DEBUG_TRACES + std::cout << "] - radius = " << radius << " - returns " << (radius > threshold_) << std::endl; +#endif // DEBUG_TRACES + simplex_tree_.assign_filtration(sh, radius); + return (radius > threshold_); + } + Cech_blocker(Simplex_tree& simplex_tree, Filtration_value threshold, const std::vector& point_cloud) + : simplex_tree_(simplex_tree), + threshold_(threshold), + point_cloud_(point_cloud) { } + private: + Simplex_tree simplex_tree_; + Filtration_value threshold_; + std::vector point_cloud_; +}; + +template< typename InputPointRange> +Graph_t compute_proximity_graph(InputPointRange &points, Filtration_value threshold); + +void program_options(int argc, char * argv[] + , std::string & off_file_points + , Filtration_value & threshold + , int & dim_max); + +int main(int argc, char * argv[]) { + std::string off_file_points; + Filtration_value threshold; + int dim_max; + + program_options(argc, argv, off_file_points, threshold, dim_max); + + // Extract the points from the file filepoints + Points_off_reader off_reader(off_file_points); + + // Compute the proximity graph of the points + Graph_t prox_graph = compute_proximity_graph(off_reader.get_point_cloud(), threshold); + + //Min_sphere sph1(off_reader.get_point_cloud()[0], off_reader.get_point_cloud()[1], off_reader.get_point_cloud()[2]); + // Construct the Rips complex in a Simplex Tree + Simplex_tree st; + // insert the proximity graph in the simplex tree + st.insert_graph(prox_graph); + // expand the graph until dimension dim_max + st.expansion_with_blockers(dim_max, Cech_blocker(st, threshold, off_reader.get_point_cloud())); + + std::cout << "The complex contains " << st.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << st.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + +#if DEBUG_TRACES + std::cout << "********************************************************************\n"; + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "* The complex contains " << st.num_simplices() << " simplices - dimension=" << st.dimension() << "\n"; + std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << static_cast(vertex) << " "; + } + std::cout << std::endl; + } +#endif // DEBUG_TRACES + return 0; +} + +void program_options(int argc, char * argv[] + , std::string & off_file_points + , Filtration_value & threshold + , int & dim_max) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value(&off_file_points), + "Name of an OFF file containing a 3d point set.\n"); + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("max-edge-length,r", + po::value(&threshold)->default_value(std::numeric_limits::infinity()), + "Maximal length of an edge for the Cech complex construction.") + ("cpx-dimension,d", po::value(&dim_max)->default_value(1), + "Maximal dimension of the Cech complex we want to compute."); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Construct a Cech complex defined on a set of input points.\n \n"; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} + +/** Output 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. + * + * The type PointCloud furnishes .begin() and .end() methods, that return + * iterators with value_type Point. + */ +template< typename InputPointRange> +Graph_t compute_proximity_graph(InputPointRange &points, Filtration_value threshold) { + std::vector< Edge_t > edges; + std::vector< Filtration_value > edges_fil; + + Kernel k; + Vertex_handle idx_u, idx_v; + Filtration_value fil; + idx_u = 0; + for (auto it_u = points.begin(); it_u != points.end(); ++it_u) { + idx_v = idx_u + 1; + for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) { + fil = k.squared_distance_d_object()(*it_u, *it_v); + // For Cech Complex, threshold is a radius (distance /2) + fil = std::sqrt(fil) / 2.; + if (fil <= threshold) { + edges.emplace_back(idx_u, idx_v); + edges_fil.push_back(fil); + } + } + ++idx_u; + } + + Graph_t skel_graph(edges.begin() + , edges.end() + , edges_fil.begin() + , idx_u); // number of points labeled from 0 to idx_u-1 + + auto vertex_prop = boost::get(Gudhi::vertex_filtration_t(), skel_graph); + + boost::graph_traits::vertex_iterator vi, vi_end; + for (std::tie(vi, vi_end) = boost::vertices(skel_graph); + vi != vi_end; ++vi) { + boost::put(vertex_prop, *vi, 0.); + } + + return skel_graph; +} diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 7da767cb..5d8a90ee 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1145,7 +1145,7 @@ class Simplex_tree { Siblings * new_sib = new Siblings(siblings, // oncles simplex->first, // parent boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t - std::vector blocked_new_sib_list; + std::vector blocked_new_sib_vertex_list; // As all intersections are inserted, we can call the blocker function on all new_sib members for (auto new_sib_member = new_sib->members().begin(); new_sib_member != new_sib->members().end(); @@ -1153,17 +1153,19 @@ class Simplex_tree { bool blocker_result = block_simplex(new_sib_member); // new_sib member has been blocked by the blocker function // add it to the list to be removed - do not perform it while looping on it - if (blocker_result) - blocked_new_sib_list.push_back(new_sib_member); + if (blocker_result) { + blocked_new_sib_vertex_list.push_back(new_sib_member->first); + } } - bool removed = false; - for (auto& blocked_new_sib_member : blocked_new_sib_list){ - removed = removed || remove_maximal_simplex(blocked_new_sib_member); - } - if (removed) { + if (blocked_new_sib_vertex_list.size() == new_sib->members().size()) { + // Specific case where all have to be deleted + delete new_sib; // ensure the children property simplex->second.assign_children(siblings); } else { + for (auto& blocked_new_sib_member : blocked_new_sib_vertex_list) { + new_sib->members().erase(blocked_new_sib_member); + } // ensure recursive call simplex->second.assign_children(new_sib); siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex); @@ -1338,16 +1340,14 @@ class Simplex_tree { public: /** \brief Remove a maximal simplex. * @param[in] sh Simplex handle on the maximal simplex to remove. - * @return a boolean value that is an implementation detail, and that the user is supposed to ignore * \pre Please check the simplex has no coface before removing it. * \exception std::invalid_argument In debug mode, if sh has children. - * \post Be aware that removing is shifting data in a flat_map (`initialize_filtration()` to be done). + * \post Be aware that removing is shifting data in a flat_map (initialize_filtration to be done). * \post Note that the dimension of the simplicial complex may be lower after calling `remove_maximal_simplex()` * than it was before. However, `upper_bound_dimension()` will return the old value, which remains a valid upper * bound. If you care, you can call `dimension()` to recompute the exact dimension. - * \internal @return true if the leaf's branch has no other leaves (branch's children has been re-assigned), false otherwise. */ - bool remove_maximal_simplex(Simplex_handle sh) { + void remove_maximal_simplex(Simplex_handle sh) { // Guarantee the simplex has no children GUDHI_CHECK(!has_children(sh), std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children")); @@ -1365,9 +1365,7 @@ class Simplex_tree { delete child; // dimension may need to be lowered dimension_to_be_lowered_ = true; - return true; } - return false; } private: diff --git a/src/common/include/gudhi/graph_simplicial_complex.h b/src/common/include/gudhi/graph_simplicial_complex.h index 5fe7c826..d84421b2 100644 --- a/src/common/include/gudhi/graph_simplicial_complex.h +++ b/src/common/include/gudhi/graph_simplicial_complex.h @@ -28,6 +28,9 @@ #include // for pair<> #include #include +#include // for std::tie + +namespace Gudhi { /* Edge tag for Boost PropertyGraph. */ struct edge_filtration_t { @@ -39,4 +42,64 @@ struct vertex_filtration_t { typedef boost::vertex_property_tag kind; }; +template +using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS +, boost::property < vertex_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value > +, boost::property < edge_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >>; + +/** \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 SimplicialComplexForProximityGraph + , typename ForwardPointRange + , typename Distance > +Proximity_graph compute_proximity_graph( + const ForwardPointRange& points, + typename SimplicialComplexForProximityGraph::Filtration_value threshold, + Distance distance) { + using Vertex_handle = typename SimplicialComplexForProximityGraph::Vertex_handle; + using Filtration_value = typename SimplicialComplexForProximityGraph::Filtration_value; + + std::vector> edges; + std::vector< Filtration_value > edges_fil; + std::map< Vertex_handle, Filtration_value > vertices; + + Vertex_handle idx_u, idx_v; + Filtration_value fil; + idx_u = 0; + for (auto it_u = points.begin(); it_u != points.end(); ++it_u) { + idx_v = idx_u + 1; + for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) { + fil = distance(*it_u, *it_v); + if (fil <= threshold) { + edges.emplace_back(idx_u, idx_v); + edges_fil.push_back(fil); + } + } + ++idx_u; + } + + // Points are labeled from 0 to idx_u-1 + Proximity_graph skel_graph(edges.begin(), edges.end(), edges_fil.begin(), idx_u); + + auto vertex_prop = boost::get(vertex_filtration_t(), skel_graph); + + typename boost::graph_traits>::vertex_iterator vi, vi_end; + for (std::tie(vi, vi_end) = boost::vertices(skel_graph); + vi != vi_end; ++vi) { + boost::put(vertex_prop, *vi, 0.); + } + + return skel_graph; +} + +} // namespace Gudhi + #endif // GRAPH_SIMPLICIAL_COMPLEX_H_ -- cgit v1.2.3 From 4cf2e2232a2046590909d78c887a2b96a2af8177 Mon Sep 17 00:00:00 2001 From: glisse Date: Sat, 2 Dec 2017 13:34:29 +0000 Subject: Cleanup checks in Simplex_tree Rewrite GUDHi_CHECK so we don't get nasty surprises with: if(cond) GUDHI_CHECK(...) else ... where the else would have been matched with the if in GUDHI_CHECK. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-glisse@3010 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: a1385540710d0079567b7e4566766bd0da53c584 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 7 ++++--- src/common/include/gudhi/Debug_utils.h | 2 +- 2 files changed, 5 insertions(+), 4 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index cb6ab309..81dff00d 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -106,8 +106,9 @@ class Simplex_tree { }; struct Key_simplex_base_dummy { Key_simplex_base_dummy() {} - void assign_key(Simplex_key) { } - Simplex_key key() const { assert(false); return -1; } + // Undefined so it will not link + void assign_key(Simplex_key); + Simplex_key key() const; }; typedef typename std::conditional::type Key_simplex_base; @@ -121,7 +122,7 @@ class Simplex_tree { }; struct Filtration_simplex_base_dummy { Filtration_simplex_base_dummy() {} - void assign_filtration(Filtration_value f) { assert(f == 0); } + void assign_filtration(Filtration_value GUDHI_CHECK_code(f)) { GUDHI_CHECK(f == 0, "filtration value specified for a complex that does not store them"); } Filtration_value filtration() const { return 0; } }; typedef typename std::conditional Date: Sat, 2 Dec 2017 15:51:56 +0000 Subject: Copy insert_simplex_and_subfaces from the gforge TODO, updated to set the dimension. Passes the testsuite. Not benchmarked yet. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-insert@3017 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0a1abbf9d60d14129431f9152a43d2d6d69a647d --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 96 ++++++++++++--------------- 1 file changed, 44 insertions(+), 52 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index cb6ab309..24980314 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -664,71 +664,63 @@ class Simplex_tree { */ template> std::pair insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, - Filtration_value filtration = 0) { + Filtration_value filtration = 0) { auto first = std::begin(Nsimplex); auto last = std::end(Nsimplex); if (first == last) - return std::pair(null_simplex(), true); // ----->> + return { null_simplex(), true }; // ----->> // Copy before sorting - std::vector copy(first, last); + thread_local std::vector copy; + copy.clear(); + copy.insert(copy.end(), first, last); std::sort(std::begin(copy), std::end(copy)); - std::vector> to_be_inserted; - std::vector> to_be_propagated; - return rec_insert_simplex_and_subfaces(copy, to_be_inserted, to_be_propagated, filtration); + return insert_simplex_and_subfaces_sorted(copy, filtration); } private: - std::pair rec_insert_simplex_and_subfaces(std::vector& the_simplex, - std::vector>& to_be_inserted, - std::vector>& to_be_propagated, - Filtration_value filtration = 0.0) { - std::pair insert_result; - if (the_simplex.size() > 1) { - // Get and remove last vertex - Vertex_handle last_vertex = the_simplex.back(); - the_simplex.pop_back(); - // Recursive call after last vertex removal - insert_result = rec_insert_simplex_and_subfaces(the_simplex, to_be_inserted, to_be_propagated, filtration); - - // Concatenation of to_be_inserted and to_be_propagated - to_be_inserted.insert(to_be_inserted.begin(), to_be_propagated.begin(), to_be_propagated.end()); - to_be_propagated = to_be_inserted; - - // to_be_inserted treatment - for (auto& simplex_tbi : to_be_inserted) { - simplex_tbi.push_back(last_vertex); - } - std::vector last_simplex(1, last_vertex); - to_be_inserted.insert(to_be_inserted.begin(), last_simplex); - // i.e. (0,1,2) => - // [to_be_inserted | to_be_propagated] = [(1) (0,1) | (0)] - // [to_be_inserted | to_be_propagated] = [(2) (0,2) (1,2) (0,1,2) | (0) (1) (0,1)] - // N.B. : it is important the last inserted to be the highest in dimension - // in order to return the "last" insert_simplex result - - // insert all to_be_inserted - for (auto& simplex_tbi : to_be_inserted) { - insert_result = insert_vertex_vector(simplex_tbi, filtration); - } - } else if (the_simplex.size() == 1) { - // When reaching the end of recursivity, vector of simplices shall be empty and filled on back recursive - if ((to_be_inserted.size() != 0) || (to_be_propagated.size() != 0)) { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty\n"; - exit(-1); + /// Same as insert_simplex_and_subfaces but assumes that the range of vertices is sorted + template> + std::pair insert_simplex_and_subfaces_sorted(const ForwardVertexRange& Nsimplex, Filtration_value filt = 0) { + auto first = std::begin(Nsimplex); + auto last = std::end(Nsimplex); + if (first == last) + return { null_simplex(), true }; // FIXME: false would make more sense to me. + GUDHI_CHECK(std::is_sorted(first, last), "simplex vertices listed in unsorted order"); + // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain. + dimension_ = std::max(dimension_, static_cast(std::distance(first, last)) - 1); + return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt); + } + // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1. + template + std::pair rec_insert_simplex_and_subfaces_sorted(Siblings* sib, ForwardVertexIterator first, ForwardVertexIterator last, Filtration_value filt) { + // An alternative strategy would be: + // - try to find the complete simplex, if found (and low filtration) exit + // - insert all the vertices at once in sib + // - loop over those (new or not) simplices, with a recursive call(++first, last) + Vertex_handle vertex_one = *first; + auto&& dict = sib->members(); + auto insertion_result = dict.emplace(vertex_one, Node(sib, filt)); + Simplex_handle simplex_one = insertion_result.first; + bool one_is_new = insertion_result.second; + if (!one_is_new) { + if (filtration(simplex_one) > filt) { + assign_filtration(simplex_one, filt); + } else { + // FIXME: this interface makes no sense, and it doesn't seem to be tested. + insertion_result.first = null_simplex(); } - std::vector first_simplex(1, the_simplex.back()); - // i.e. (0,1,2) => [to_be_inserted | to_be_propagated] = [(0) | ] - to_be_inserted.push_back(first_simplex); - - insert_result = insert_vertex_vector(first_simplex, filtration); - } else { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error\n"; - exit(-1); } - return insert_result; + if (++first == last) return insertion_result; + if (!has_children(simplex_one)) + // TODO: have special code here, we know we are building the whole subtree from scratch. + simplex_one->second.assign_children(new Siblings(sib, vertex_one)); + auto res = rec_insert_simplex_and_subfaces_sorted(simplex_one->second.children(), first, last, filt); + // No need to continue if the full simplex was already there with a low enough filtration value. + if (res.first != null_simplex()) rec_insert_simplex_and_subfaces_sorted(sib, first, last, filt); + return res; } public: -- cgit v1.2.3 From 32e5567c9fe1ccd11aa6da12d1dfb472d1ac8def Mon Sep 17 00:00:00 2001 From: glisse Date: Sun, 17 Dec 2017 14:58:15 +0000 Subject: Remove unused AdjacencyGraph requirement. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3078 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e7b92734bc7fbcaf070bd2439cb8aa6af3c2c8e1 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index cb6ab309..f09c8d20 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -941,7 +941,7 @@ class Simplex_tree { * called. * * Inserts all vertices and edges given by a OneSkeletonGraph. - * OneSkeletonGraph must be a model of boost::AdjacencyGraph, + * OneSkeletonGraph must be a model of * boost::EdgeListGraph and boost::PropertyGraph. * * The vertex filtration value is accessible through the property tag -- cgit v1.2.3 From a910ec9af137d8cd2d0d41ca17bbbc5d5ee8e77b Mon Sep 17 00:00:00 2001 From: glisse Date: Sun, 17 Dec 2017 15:24:38 +0000 Subject: Hyperlink to boost concepts. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3079 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 9ded02fd1e50098d8295c4f6e2b7a9a3adc4018f --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index f09c8d20..1052e287 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -942,7 +942,8 @@ class Simplex_tree { * * Inserts all vertices and edges given by a OneSkeletonGraph. * OneSkeletonGraph must be a model of - * boost::EdgeListGraph and boost::PropertyGraph. + * boost::EdgeListGraph + * and boost::PropertyGraph. * * The vertex filtration value is accessible through the property tag * vertex_filtration_t. -- cgit v1.2.3 From f538a1fac876b84edf87bb0d95d70413295e2330 Mon Sep 17 00:00:00 2001 From: glisse Date: Sun, 17 Dec 2017 18:14:39 +0000 Subject: Fix graph insertion. It currently ignores edge (i, j) with j::vertex_descriptor * must be Vertex_handle. * boost::graph_traits::directed_category - * must be undirected_tag. */ + * must be undirected_tag. + * + * If an edge appears with multiplicity, the function will arbitrarily pick + * one representative to read the filtration value. */ template void insert_graph(const OneSkeletonGraph& skel_graph) { // the simplex tree must be empty @@ -984,18 +987,22 @@ class Simplex_tree { ++e_it) { auto u = source(*e_it, skel_graph); auto v = target(*e_it, skel_graph); - if (u < v) { - // count edges only once { std::swap(u,v); } // u < v - auto sh = find_vertex(u); - if (!has_children(sh)) { - sh->second.assign_children(new Siblings(&root_, sh->first)); - } - - sh->second.children()->members().emplace( - v, - Node(sh->second.children(), - boost::get(edge_filtration_t(), skel_graph, *e_it))); + if (u == v) throw "Self-loops are not simplicial"; + // We cannot skip edges with the wrong orientation and expect them to + // come a second time with the right orientation, that does not always + // happen in practice. emplace() should be a NOP when an element with the + // same key is already there, so seeing the same edge multiple times is + // ok. + // Should we actually forbid multiple edges? That would be consistent + // with rejecting self-loops. + if (v < u) std::swap(u, v); + auto sh = find_vertex(u); + if (!has_children(sh)) { + sh->second.assign_children(new Siblings(&root_, sh->first)); } + + sh->second.children()->members().emplace(v, + Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, *e_it))); } } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 580d610a..f63ea080 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -863,3 +863,35 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { BOOST_CHECK(st == st_other_copy); } + +BOOST_AUTO_TEST_CASE(insert_graph) { + std::cout << "********************************************************************" << std::endl; + std::cout << "INSERT GRAPH" << std::endl; + typedef typename boost::adjacency_list, + boost::property> Graph; + Graph g(3); + // filtration value 0 everywhere + put(Gudhi::vertex_filtration_t(), g, 0, 0); + put(Gudhi::vertex_filtration_t(), g, 1, 0); + put(Gudhi::vertex_filtration_t(), g, 2, 0); + // vertices don't always occur in sorted order + add_edge(0, 1, 0, g); + add_edge(2, 1, 0, g); + add_edge(2, 0, 0, g); + + typedef Simplex_tree<> typeST; + typeST st1; + st1.insert_graph(g); + BOOST_CHECK(st1.num_simplices() == 6); + + // edges can have multiplicity in the graph unless we replace the first vecS with (hash_)setS + add_edge(1, 0, 0, g); + add_edge(1, 2, 0, g); + add_edge(0, 2, 0, g); + add_edge(0, 2, 0, g); + typeST st2; + st2.insert_graph(g); + BOOST_CHECK(st2.num_simplices() == 6); +} -- cgit v1.2.3 From 546245f15c9a8a6ab36a509a8bb836d7e54e5b08 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 22 Dec 2017 13:32:57 +0000 Subject: Check that user does not try to insert null_vertex in the complex. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3100 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b44cf48f810de029f3bd8c3a18cc8a9959c34bff --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 2dddc518..327e1a62 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -584,12 +584,14 @@ class Simplex_tree { std::pair res_insert; auto vi = simplex.begin(); for (; vi != simplex.end() - 1; ++vi) { + GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"); res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!(has_children(res_insert.first))) { res_insert.first->second.assign_children(new Siblings(curr_sib, *vi)); } curr_sib = res_insert.first->second.children(); } + GUDHI_CHECK(*vi != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"); res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!res_insert.second) { // if already in the complex @@ -674,6 +676,10 @@ class Simplex_tree { // Copy before sorting std::vector copy(first, last); std::sort(std::begin(copy), std::end(copy)); + GUDHI_CHECK_code( + for (Vertex_handle v : copy) + GUDHI_CHECK(v != null_vertex(), "cannot use the dummy null_vertex() as a real vertex"); + ) std::vector> to_be_inserted; std::vector> to_be_propagated; -- cgit v1.2.3 From 31693eda10d0de838b480b9fdbd0a30769208291 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 22 Dec 2017 14:14:02 +0000 Subject: Comment pointing out where we use null_vertex. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3101 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b6fa96bd51ef95767c10310262951339f7971442 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 1 + 1 file changed, 1 insertion(+) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 327e1a62..0b8ad6b8 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -500,6 +500,7 @@ class Simplex_tree { * sh has children.*/ template bool has_children(SimplexHandle sh) const { + // Here we rely on the root using null_vertex(), which cannot match any real vertex. return (sh->second.children()->parent() == sh->first); } -- cgit v1.2.3 From 0e574fc38658b23b25655991e9822fd42fff0890 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 22 Dec 2017 17:03:33 +0000 Subject: Use contiguous_vertices in find_simplex(). git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3104 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b8d7996b0c3a020d1b67003e4250e557c3cebee9 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 0b8ad6b8..1a6a72a3 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -531,7 +531,20 @@ class Simplex_tree { Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; Vertex_handle last = simplex.back(); - for (auto v : simplex) { + auto vi = simplex.begin(); + if (Options::contiguous_vertices) { + GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices"); + Vertex_handle v = *vi++; + if(v < 0 || v >= static_cast(root_.members_.size())) + return null_simplex(); + tmp_dit = root_.members_.begin() + v; + if (!has_children(tmp_dit) && v != last) { + return null_simplex(); + } + tmp_sib = tmp_dit->second.children(); + } + for (; vi != simplex.end(); ++vi) { + Vertex_handle v = *vi; tmp_dit = tmp_sib->members_.find(v); if (tmp_dit == tmp_sib->members_.end()) { return null_simplex(); -- cgit v1.2.3 From 13e9c4ecc222efe0ffc3588eb8f559f7cd1d761d Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 22 Dec 2017 17:41:54 +0000 Subject: Prettify find_simplex(). git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3105 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 34ce3d49fb8f9e64df8b492b2e9091e5e0ca6be4 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 21 ++++++++++----------- 1 file changed, 10 insertions(+), 11 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 1a6a72a3..92add101 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -530,31 +530,30 @@ class Simplex_tree { Simplex_handle find_simplex(const std::vector & simplex) { Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; - Vertex_handle last = simplex.back(); auto vi = simplex.begin(); if (Options::contiguous_vertices) { + // Equivalent to the first iteration of the normal loop GUDHI_CHECK(contiguous_vertices(), "non-contiguous vertices"); Vertex_handle v = *vi++; if(v < 0 || v >= static_cast(root_.members_.size())) return null_simplex(); tmp_dit = root_.members_.begin() + v; - if (!has_children(tmp_dit) && v != last) { + if (vi == simplex.end()) + return tmp_dit; + if (!has_children(tmp_dit)) return null_simplex(); - } tmp_sib = tmp_dit->second.children(); } - for (; vi != simplex.end(); ++vi) { - Vertex_handle v = *vi; - tmp_dit = tmp_sib->members_.find(v); - if (tmp_dit == tmp_sib->members_.end()) { + for (;;) { + tmp_dit = tmp_sib->members_.find(*vi++); + if (tmp_dit == tmp_sib->members_.end()) return null_simplex(); - } - if (!has_children(tmp_dit) && v != last) { + if (vi == simplex.end()) + return tmp_dit; + if (!has_children(tmp_dit)) return null_simplex(); - } tmp_sib = tmp_dit->second.children(); } - return tmp_dit; } /** \brief Returns the Simplex_handle corresponding to the 0-simplex -- cgit v1.2.3 From 937374846f26a8cc18786780c48112ca2387a4e0 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 8 Jan 2018 14:31:36 +0000 Subject: Add include for std::distance git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@3119 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 92438c70043c4ee0d200b8906400b059d176196f --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 1 + 1 file changed, 1 insertion(+) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 4094af25..527267a5 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -49,6 +49,7 @@ #include #include // for std::max #include // for std::uint32_t +#include // for std::distance namespace Gudhi { -- cgit v1.2.3 From b590611a71bd4be2fd7a92bc65666e9ba6355a2a Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 8 Jan 2018 15:38:46 +0000 Subject: Fix std::max Windows issue git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@3120 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 9aad5e17fb5b93b9b9054ce093dd54a56ca4b08a --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 527267a5..580f85ed 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -692,7 +692,7 @@ class Simplex_tree { return { null_simplex(), true }; // FIXME: false would make more sense to me. GUDHI_CHECK(std::is_sorted(first, last), "simplex vertices listed in unsorted order"); // Update dimension if needed. We could wait to see if the insertion succeeds, but I doubt there is much to gain. - dimension_ = std::max(dimension_, static_cast(std::distance(first, last)) - 1); + dimension_ = (std::max)(dimension_, static_cast(std::distance(first, last)) - 1); return rec_insert_simplex_and_subfaces_sorted(root(), first, last, filt); } // To insert {1,2,3,4}, we insert {2,3,4} twice, once at the root, and once below 1. @@ -1132,7 +1132,7 @@ class Simplex_tree { to_be_inserted=false; break; } - filt = std::max(filt, filtration(border_child)); + filt = (std::max)(filt, filtration(border_child)); } if (to_be_inserted) { intersection.emplace_back(next->first, Node(nullptr, filt)); @@ -1328,7 +1328,7 @@ class Simplex_tree { if (sh_dimension >= dimension_) // Stop browsing as soon as the dimension is reached, no need to go furter return false; - new_dimension = std::max(new_dimension, sh_dimension); + new_dimension = (std::max)(new_dimension, sh_dimension); } dimension_ = new_dimension; return true; -- cgit v1.2.3