graph_simplicial_complex.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): ClĂ©ment Maria
4  *
5  * Copyright (C) 2014 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef GRAPH_SIMPLICIAL_COMPLEX_H_
12 #define GRAPH_SIMPLICIAL_COMPLEX_H_
13 
14 #include <boost/graph/adjacency_list.hpp>
15 
16 #include <utility> // for pair<>
17 #include <vector>
18 #include <map>
19 #include <tuple> // for std::tie
20 
21 namespace Gudhi {
22 
23 /* Edge tag for Boost PropertyGraph. */
24 struct edge_filtration_t {
25  typedef boost::edge_property_tag kind;
26 };
27 
28 /* Vertex tag for Boost PropertyGraph. */
29 struct vertex_filtration_t {
30  typedef boost::vertex_property_tag kind;
31 };
32 
39 template <typename SimplicialComplexForProximityGraph>
40 using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS
41 , boost::property < vertex_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >
42 , boost::property < edge_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >>;
43 
54 template< typename SimplicialComplexForProximityGraph
55  , typename ForwardPointRange
56  , typename Distance >
57 Proximity_graph<SimplicialComplexForProximityGraph> compute_proximity_graph(
58  const ForwardPointRange& points,
59  typename SimplicialComplexForProximityGraph::Filtration_value threshold,
60  Distance distance) {
61  using Vertex_handle = typename SimplicialComplexForProximityGraph::Vertex_handle;
62  using Filtration_value = typename SimplicialComplexForProximityGraph::Filtration_value;
63 
64  std::vector<std::pair< Vertex_handle, Vertex_handle >> edges;
65  std::vector< Filtration_value > edges_fil;
66  std::map< Vertex_handle, Filtration_value > vertices;
67 
68  Vertex_handle idx_u, idx_v;
69  Filtration_value fil;
70  idx_u = 0;
71  for (auto it_u = points.begin(); it_u != points.end(); ++it_u) {
72  idx_v = idx_u + 1;
73  for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) {
74  fil = distance(*it_u, *it_v);
75  if (fil <= threshold) {
76  edges.emplace_back(idx_u, idx_v);
77  edges_fil.push_back(fil);
78  }
79  }
80  ++idx_u;
81  }
82 
83  // Points are labeled from 0 to idx_u-1
84  Proximity_graph<SimplicialComplexForProximityGraph> skel_graph(edges.begin(), edges.end(), edges_fil.begin(), idx_u);
85 
86  auto vertex_prop = boost::get(vertex_filtration_t(), skel_graph);
87 
88  typename boost::graph_traits<Proximity_graph<SimplicialComplexForProximityGraph>>::vertex_iterator vi, vi_end;
89  for (std::tie(vi, vi_end) = boost::vertices(skel_graph);
90  vi != vi_end; ++vi) {
91  boost::put(vertex_prop, *vi, 0.);
92  }
93 
94  return skel_graph;
95 }
96 
97 } // namespace Gudhi
98 
99 #endif // GRAPH_SIMPLICIAL_COMPLEX_H_
FiltrationValue
Value type for a filtration function on a cell complex.
Definition: FiltrationValue.h:20
GUDHI  Version 3.1.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Wed Jan 22 2020 10:16:38 for GUDHI by Doxygen 1.8.16