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') 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') 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') 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') 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') 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') 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