From 9b05f9dadd25f2a5f1051044b2e00ebfc6e9b0a5 Mon Sep 17 00:00:00 2001
From: vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb>
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
---
 .../include/gudhi/graph_simplicial_complex.h       | 63 ++++++++++++++++++++++
 1 file changed, 63 insertions(+)

(limited to 'src/common/include/gudhi/graph_simplicial_complex.h')

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 <utility>  // for pair<>
 #include <vector>
 #include <map>
+#include <tuple>  // 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 <typename SimplicialComplexForProximityGraph>
+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<SimplicialComplexForProximityGraph> 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<std::pair< Vertex_handle, Vertex_handle >> 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<SimplicialComplexForProximityGraph> 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<Proximity_graph<SimplicialComplexForProximityGraph>>::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