blob: 8876b56d69616c80acbe3a909406ad2dffba6285 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
#ifndef FAKE_SIMPLEX_TREE_H
#define FAKE_SIMPLEX_TREE_H
#include <cmath>
#include <gudhi/Simplex_tree.h>
#include <gudhi/Filtered_toplex_map.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bron_kerbosch_all_cliques.hpp>
namespace Gudhi {
struct Visitor {
Toplex_map* tm;
Visitor(Toplex_map* tm)
:tm(tm)
{}
template <typename Clique, typename Graph>
void clique(const Clique& c, const Graph& g)
{
tm->insert_simplex(c);
}
};
/** Fake_simplex_tree is a wrapper for Filtered_toplex_map which has the interface of the Simplex_tree.
* Mostly for retro-compatibility purpose. If you use a function that output non maximal simplices, it will be non efficient.
* \ingroup toplex_map */
class Fake_simplex_tree : public Filtered_toplex_map {
public:
/** Vertex is the type of vertices.
* \ingroup toplex_map */
typedef Toplex_map::Vertex Vertex;
/** Simplex is the type of simplices.
* \ingroup toplex_map */
typedef Toplex_map::Simplex Simplex;
/** The type of the pointers to maximal simplices.
* \ingroup toplex_map */
typedef Toplex_map::Simplex_ptr Simplex_ptr;
/** The type of the sets of Simplex_ptr.
* \ingroup toplex_map */
typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set;
/** Handle type to a vertex contained in the simplicial complex.
* \ingroup toplex_map */
typedef Vertex Vertex_handle;
/** Handle type to a simplex contained in the simplicial complex.
* \ingroup toplex_map */
typedef Simplex Simplex_handle;
typedef void Insertion_result_type;
/** Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph`
* in the simplicial complex.
* \ingroup toplex_map */
template<class OneSkeletonGraph>
void insert_graph(const OneSkeletonGraph& skel_graph);
/** Do actually nothing.
* \ingroup toplex_map */
void expansion(int max_dim);
/** Returns the number of vertices stored i.e. the number of max simplices
* \ingroup toplex_map */
std::size_t num_vertices() const;
/** Returns the dimension of the complex.
* \ingroup toplex_map */
std::size_t dimension() const;
/** Returns the dimension of a given simplex in the complex.
* \ingroup toplex_map */
std::size_t dimension(Simplex_ptr& sptr) const;
/** Returns the number of simplices stored i.e. the number of maximal simplices.
* \ingroup toplex_map */
std::size_t num_simplices() const;
/** Returns a range over the vertices of a simplex.
* \ingroup toplex_map */
Simplex simplex_vertex_range(const Simplex& s) const;
/** Returns a set of all maximal (critical if there is filtration values) simplices.
* \ingroup toplex_map */
std::vector<Simplex> max_simplices() const;
/** Returns all the simplices, of max dimension d if a parameter d is given.
* \ingroup toplex_map */
std::vector<Simplex> filtration_simplex_range(int d=std::numeric_limits<int>::max()) const;
/** Returns all the simplices of max dimension d
* \ingroup toplex_map */
std::vector<Simplex> skeleton_simplex_range(int d) const;
protected:
/** \internal Does all the facets of the given simplex belong to the complex ?
* \ingroup toplex_map */
template <typename Input_vertex_range>
bool all_facets_inside(const Input_vertex_range &vertex_range) const;
};
template<class OneSkeletonGraph>
void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){
toplex_maps.emplace(nan(""),Toplex_map());
using vertex_iterator = typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator;
vertex_iterator vi, vi_end;
for (std::tie(vi, vi_end) = boost::vertices(skel_graph); vi != vi_end; ++vi) {
Simplex s; s.insert(*vi);
insert_simplex_and_subfaces(s);
}
bron_kerbosch_all_cliques(skel_graph, Visitor(&(this->toplex_maps.at(nan("")))));
}
void Fake_simplex_tree::expansion(int max_dim){}
template <typename Input_vertex_range>
bool Fake_simplex_tree::all_facets_inside(const Input_vertex_range &vertex_range) const{
Simplex sigma(vertex_range);
for(const Simplex& s : facets(sigma))
if(!membership(s)) return false;
return true;
}
std::size_t Fake_simplex_tree::dimension() const {
std::size_t max = 0;
for(const Simplex& s : max_simplices())
max = std::max(max, s.size());
return max-1;
}
std::size_t Fake_simplex_tree::dimension(Simplex_ptr& sptr) const{
return sptr->size();
}
std::size_t Fake_simplex_tree::num_simplices() const {
//return filtration_simplex_range().size();
return max_simplices().size();
}
std::size_t Fake_simplex_tree::num_vertices() const {
std::unordered_set<Vertex> vertices;
for(const Simplex& s : max_simplices())
for (Vertex v : s)
vertices.emplace(v);
return vertices.size();
}
Simplex Fake_simplex_tree::simplex_vertex_range(const Simplex& s) const {
return s;
}
std::vector<Simplex> Fake_simplex_tree::max_simplices() const{
std::vector<Simplex> max_s;
for(auto kv : toplex_maps)
for(const Simplex_ptr& sptr : kv.second.maximal_cofaces(Simplex()))
max_s.emplace_back(*sptr);
return max_s;
}
std::vector<Simplex> Fake_simplex_tree::filtration_simplex_range(int d) const{
std::vector<Simplex> m = max_simplices();
std::vector<Simplex> range;
Simplex_ptr_set seen;
while(m.begin()!=m.end()){
Simplex s(m.back());
m.pop_back();
if(seen.find(get_key(s))==seen.end()){
if(s.size()-1<=d)
range.emplace_back(s);
seen.emplace(get_key(s));
if(s.size()>0)
for(Simplex& sigma : facets(s))
m.emplace_back(sigma);
}
}
return range;
}
std::vector<Simplex> Fake_simplex_tree::skeleton_simplex_range(int d) const{
return filtration_simplex_range(d);
}
} //namespace Gudhi
#endif /* FAKE_SIMPLEX_TREE_H */
|
