From f538a1fac876b84edf87bb0d95d70413295e2330 Mon Sep 17 00:00:00 2001
From: glisse <glisse@636b058d-ea47-450e-bf9e-a15bfbe3eedb>
Date: Sun, 17 Dec 2017 18:14:39 +0000
Subject: Fix graph insertion.

It currently ignores edge (i, j) with j<i, but nothing in the concept forbids such an edge.


git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/misc-glisse@3080 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 305f58b4995878da23b0fa07dc783c0bdceab6db
---
 src/Simplex_tree/include/gudhi/Simplex_tree.h    | 31 ++++++++++++++---------
 src/Simplex_tree/test/simplex_tree_unit_test.cpp | 32 ++++++++++++++++++++++++
 2 files changed, 51 insertions(+), 12 deletions(-)

(limited to 'src/Simplex_tree')

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 1052e287..2dddc518 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -953,7 +953,10 @@ class Simplex_tree {
    * boost::graph_traits<OneSkeletonGraph>::vertex_descriptor
    *                                    must be Vertex_handle.
    * boost::graph_traits<OneSkeletonGraph>::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<class OneSkeletonGraph>
   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::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);
+
+  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