diff options
Diffstat (limited to 'src/common/include/gudhi/graph_simplicial_complex.h')
-rw-r--r-- | src/common/include/gudhi/graph_simplicial_complex.h | 99 |
1 files changed, 99 insertions, 0 deletions
diff --git a/src/common/include/gudhi/graph_simplicial_complex.h b/src/common/include/gudhi/graph_simplicial_complex.h new file mode 100644 index 00000000..b8508697 --- /dev/null +++ b/src/common/include/gudhi/graph_simplicial_complex.h @@ -0,0 +1,99 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Clément Maria + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef GRAPH_SIMPLICIAL_COMPLEX_H_ +#define GRAPH_SIMPLICIAL_COMPLEX_H_ + +#include <boost/graph/adjacency_list.hpp> + +#include <utility> // for pair<> +#include <vector> +#include <map> +#include <tuple> // for std::tie + +namespace Gudhi { + +/* Edge tag for Boost PropertyGraph. */ +struct edge_filtration_t { + typedef boost::edge_property_tag kind; +}; + +/* Vertex tag for Boost PropertyGraph. */ +struct vertex_filtration_t { + typedef boost::vertex_property_tag kind; +}; + +/** \brief Proximity_graph contains the vertices and edges with their filtration values in order to store the result + * of `Gudhi::compute_proximity_graph` function. + * + * \tparam SimplicialComplexForProximityGraph furnishes `Filtration_value` type definition. + * + */ +template <typename SimplicialComplexForProximityGraph> +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 >>; + +/** \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_ |