| 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): Vincent Rouvreau |
| 4 |
* |
| 5 |
* Copyright (C) 2018 Inria |
| 6 |
* |
| 7 |
* Modification(s): |
| 8 |
* - YYYY/MM Author: Description of the modification |
| 9 |
*/ |
| 10 |
|
| 11 |
#include <gudhi/graph_simplicial_complex.h> |
| 12 |
#include <gudhi/distance_functions.h> |
| 13 |
#include <gudhi/Simplex_tree.h> |
| 14 |
#include <gudhi/Clock.h> |
| 15 |
#include <gudhi/Points_off_io.h> |
| 16 |
|
| 17 |
#include <boost/graph/adjacency_list.hpp> |
| 18 |
|
| 19 |
#include <iostream> |
| 20 |
#include <string> |
| 21 |
#include <vector> |
| 22 |
#include <limits> // for numeric limits |
| 23 |
#include <fstream> |
| 24 |
#include <cassert> |
| 25 |
|
| 26 |
|
| 27 |
std::ofstream results_csv("results.csv"); |
| 28 |
|
| 29 |
template< typename Adjacency_list, typename ForwardPointRange, typename Distance > |
| 30 |
Adjacency_list proximity_graph_computation(const ForwardPointRange& points, double threshold, Distance distance) { |
| 31 |
std::vector<std::pair< int, int >> edges; |
| 32 |
std::vector< double > edges_fil; |
| 33 |
std::map< int, double > vertices; |
| 34 |
|
| 35 |
int idx_u, idx_v; |
| 36 |
double fil; |
| 37 |
idx_u = 0; |
| 38 |
for (auto it_u = points.begin(); it_u != points.end(); ++it_u) { |
| 39 |
idx_v = idx_u + 1; |
| 40 |
for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) { |
| 41 |
fil = distance(*it_u, *it_v); |
| 42 |
if (fil <= threshold) { |
| 43 |
edges.emplace_back(idx_u, idx_v); |
| 44 |
edges_fil.push_back(fil); |
| 45 |
} |
| 46 |
} |
| 47 |
++idx_u; |
| 48 |
} |
| 49 |
|
| 50 |
// Points are labeled from 0 to idx_u-1 |
| 51 |
Adjacency_list skel_graph(edges.begin(), edges.end(), edges_fil.begin(), idx_u); |
| 52 |
|
| 53 |
auto vertex_prop = boost::get(Gudhi::vertex_filtration_t(), skel_graph); |
| 54 |
|
| 55 |
typename boost::graph_traits<Adjacency_list>::vertex_iterator vi, vi_end; |
| 56 |
for (std::tie(vi, vi_end) = boost::vertices(skel_graph); |
| 57 |
vi != vi_end; ++vi) { |
| 58 |
boost::put(vertex_prop, *vi, 0.); |
| 59 |
} |
| 60 |
|
| 61 |
return skel_graph; |
| 62 |
} |
| 63 |
|
| 64 |
template <typename Adjacency_list> |
| 65 |
void benchmark_proximity_graph(const std::string& msg, const std::string& off_file_name) { |
| 66 |
Gudhi::Points_off_reader<std::vector<double>> off_reader(off_file_name); |
| 67 |
assert(off_reader.is_valid()); |
| 68 |
|
| 69 |
std::clog << "+ " << msg << std::endl; |
| 70 |
|
| 71 |
results_csv << "\"nb_points\";" |
| 72 |
<< "\"nb_simplices\";" |
| 73 |
<< "\"compute proximity graph(sec.)\";" |
| 74 |
<< "\"complex_creation_time(sec.)\";" |
| 75 |
<< "\"" << msg << "\";" << std::endl; |
| 76 |
|
| 77 |
Gudhi::Clock pg_compute_proximity_graph(" benchmark_proximity_graph - compute proximity graph"); |
| 78 |
pg_compute_proximity_graph.begin(); |
| 79 |
// benchmark begin |
| 80 |
Adjacency_list proximity_graph = proximity_graph_computation<Adjacency_list>(off_reader.get_point_cloud(), |
| 81 |
std::numeric_limits<double>::infinity(), |
| 82 |
Gudhi::Euclidean_distance()); |
| 83 |
// benchmark end |
| 84 |
pg_compute_proximity_graph.end(); |
| 85 |
std::clog << pg_compute_proximity_graph; |
| 86 |
|
| 87 |
Gudhi::Simplex_tree<> complex; |
| 88 |
Gudhi::Clock st_create_clock(" benchmark_proximity_graph - complex creation"); |
| 89 |
st_create_clock.begin(); |
| 90 |
// benchmark begin |
| 91 |
complex.insert_graph(proximity_graph); |
| 92 |
// benchmark end |
| 93 |
st_create_clock.end(); |
| 94 |
std::clog << st_create_clock; |
| 95 |
|
| 96 |
results_csv << off_reader.get_point_cloud().size() << ";" << complex.num_simplices() << ";" |
| 97 |
<< pg_compute_proximity_graph.num_seconds() << ";" |
| 98 |
<< st_create_clock.num_seconds() << ";" << std::endl; |
| 99 |
|
| 100 |
std::clog << " benchmark_proximity_graph - nb simplices = " << complex.num_simplices() << std::endl; |
| 101 |
} |
| 102 |
|
| 103 |
int main(int argc, char * const argv[]) { |
| 104 |
std::string off_file_name(argv[1]); |
| 105 |
|
| 106 |
// The fastest, the less memory used |
| 107 |
using vecSdirectedS = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, |
| 108 |
boost::property<Gudhi::vertex_filtration_t, double>, |
| 109 |
boost::property<Gudhi::edge_filtration_t, double>>; |
| 110 |
benchmark_proximity_graph<vecSdirectedS>("vecSdirectedS", off_file_name); |
| 111 |
|
| 112 |
using vecSundirectedS = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, |
| 113 |
boost::property<Gudhi::vertex_filtration_t, double>, |
| 114 |
boost::property<Gudhi::edge_filtration_t, double>>; |
| 115 |
benchmark_proximity_graph<vecSundirectedS>("vecSundirectedS", off_file_name); |
| 116 |
|
| 117 |
using vecSbidirectionalS = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, |
| 118 |
boost::property<Gudhi::vertex_filtration_t, double>, |
| 119 |
boost::property<Gudhi::edge_filtration_t, double>>; |
| 120 |
benchmark_proximity_graph<vecSbidirectionalS>("vecSbidirectionalS", off_file_name); |
| 121 |
|
| 122 |
using setSdirectedS = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS, |
| 123 |
boost::property<Gudhi::vertex_filtration_t, double>, |
| 124 |
boost::property<Gudhi::edge_filtration_t, double>>; |
| 125 |
benchmark_proximity_graph<setSdirectedS>("setSdirectedS", off_file_name); |
| 126 |
|
| 127 |
using setSundirectedS = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, |
| 128 |
boost::property<Gudhi::vertex_filtration_t, double>, |
| 129 |
boost::property<Gudhi::edge_filtration_t, double>>; |
| 130 |
benchmark_proximity_graph<setSundirectedS>("setSundirectedS", off_file_name); |
| 131 |
|
| 132 |
using setSbidirectionalS = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, |
| 133 |
boost::property<Gudhi::vertex_filtration_t, double>, |
| 134 |
boost::property<Gudhi::edge_filtration_t, double>>; |
| 135 |
benchmark_proximity_graph<setSbidirectionalS>("setSbidirectionalS", off_file_name); |
| 136 |
|
| 137 |
return 0; |
| 138 |
} |