Debian Codegraph @

src/common/benchmark/Graph_simplicial_complex_benchmark.cpp

raw
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 }