diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2019-01-17 15:26:17 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2019-01-17 15:26:17 +0000 |
commit | 13b6be9e73f4ac5105f8344dcf37a7007e9ef904 (patch) | |
tree | 37adb80b55c51c4fea763676973e78ab3d6b104e /src | |
parent | a9664a6796501af974eb18d924f28dd9ed6ddeb4 (diff) |
adjacency lists can be directed, undirected or bidirectional for Simplex tree insert_graph method
Use of directed adjacency lists to fasten computation and use less memory
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/adjacency_list_direction_improvement@4061 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 839fabc15398ce590d09806bd783cd656029f3c1
Diffstat (limited to 'src')
6 files changed, 47 insertions, 27 deletions
diff --git a/src/Rips_complex/include/gudhi/Rips_complex.h b/src/Rips_complex/include/gudhi/Rips_complex.h index f0fe57f4..e902e52c 100644 --- a/src/Rips_complex/include/gudhi/Rips_complex.h +++ b/src/Rips_complex/include/gudhi/Rips_complex.h @@ -59,7 +59,7 @@ class Rips_complex { /** * \brief Type of the one skeleton graph stored inside the Rips complex structure. */ - typedef typename boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS + typedef typename boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS , boost::property < vertex_filtration_t, Filtration_value > , boost::property < edge_filtration_t, Filtration_value >> OneSkeletonGraph; diff --git a/src/Rips_complex/include/gudhi/Sparse_rips_complex.h b/src/Rips_complex/include/gudhi/Sparse_rips_complex.h index 4dcc08ed..00da148f 100644 --- a/src/Rips_complex/include/gudhi/Sparse_rips_complex.h +++ b/src/Rips_complex/include/gudhi/Sparse_rips_complex.h @@ -55,7 +55,7 @@ template <typename Filtration_value> class Sparse_rips_complex { private: // TODO(MG): use a different graph where we know we can safely insert in parallel. - typedef typename boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, + typedef typename boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<vertex_filtration_t, Filtration_value>, boost::property<edge_filtration_t, Filtration_value>> Graph; 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 index 34092ef6..6bab8adb 100644 --- a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp +++ b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp @@ -50,7 +50,7 @@ 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, +using Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 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>; diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 78697ea2..4b18651c 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1049,7 +1049,8 @@ class Simplex_tree { * boost::graph_traits<OneSkeletonGraph>::vertex_descriptor * must be Vertex_handle. * boost::graph_traits<OneSkeletonGraph>::directed_category - * must be undirected_tag. + * can be directed_tag (the fastest, the least RAM use), undirected_tag or even + * bidirected_tag. * * If an edge appears with multiplicity, the function will arbitrarily pick * one representative to read the filtration value. */ @@ -1077,12 +1078,14 @@ class Simplex_tree { root_.members_.end(), *v_it, Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it))); } - typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it, - e_it_end; - for (std::tie(e_it, e_it_end) = boost::edges(skel_graph); e_it != e_it_end; - ++e_it) { - auto u = source(*e_it, skel_graph); - auto v = target(*e_it, skel_graph); + std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator, + typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = boost::edges(skel_graph); + // boost_edges.first is the equivalent to boost_edges.begin() + // boost_edges.second is the equivalent to boost_edges.end() + for (; boost_edges.first != boost_edges.second; boost_edges.first++) { + auto edge = *(boost_edges.first); + auto u = source(edge, skel_graph); + auto v = target(edge, skel_graph); 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 @@ -1098,7 +1101,7 @@ class Simplex_tree { } sh->second.children()->members().emplace(v, - Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, *e_it))); + Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, edge))); } } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index f63ea080..0ae073ca 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -864,34 +864,51 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { } -BOOST_AUTO_TEST_CASE(insert_graph) { + +typedef boost::mpl::list<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, + boost::property<vertex_filtration_t, double>, + boost::property<edge_filtration_t, double>>, + boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, + boost::property<vertex_filtration_t, double>, + boost::property<edge_filtration_t, double>>, + boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, + boost::property<vertex_filtration_t, double>, + boost::property<edge_filtration_t, double>>> list_of_graph_variants; + +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insert_graph, Graph, list_of_graph_variants) { std::cout << "********************************************************************" << std::endl; std::cout << "INSERT GRAPH" << std::endl; - typedef typename boost::adjacency_list<boost::vecS, boost::vecS, - boost::undirectedS, - boost::property<vertex_filtration_t, double>, - boost::property<edge_filtration_t, double>> 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); + add_edge(0, 1, 1.1, g); + add_edge(2, 0, 2.2, g); + add_edge(2, 1, 3.3, g); - typedef Simplex_tree<> typeST; - typeST st1; + Simplex_tree<> 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; + add_edge(1, 0, 1.1, g); + add_edge(1, 2, 3.3, g); + add_edge(0, 2, 2.2, g); + add_edge(0, 1, 1.1, g); + add_edge(2, 1, 3.3, g); + add_edge(2, 0, 2.2, g); + Simplex_tree<> st2; st2.insert_graph(g); BOOST_CHECK(st2.num_simplices() == 6); + + std::cout << "st1 is" << std::endl; + std::cout << st1 << std::endl; + + std::cout << "st2 is" << std::endl; + std::cout << st2 << std::endl; + + BOOST_CHECK(st1 == st2); } diff --git a/src/common/include/gudhi/graph_simplicial_complex.h b/src/common/include/gudhi/graph_simplicial_complex.h index 49fe56cc..0d81ca71 100644 --- a/src/common/include/gudhi/graph_simplicial_complex.h +++ b/src/common/include/gudhi/graph_simplicial_complex.h @@ -49,7 +49,7 @@ struct vertex_filtration_t { * */ template <typename SimplicialComplexForProximityGraph> -using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS +using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS , boost::property < vertex_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value > , boost::property < edge_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >>; |