TTK
Loading...
Searching...
No Matches
ZeroSkeleton.cpp
Go to the documentation of this file.
1#include <ZeroSkeleton.h>
2
3using namespace ttk;
4
6 setDebugMsgPrefix("ZeroSkeleton");
7}
8
10 const SimplexId &vertexNumber,
11 const std::vector<std::array<SimplexId, 2>> &edgeList,
12 FlatJaggedArray &vertexEdges) const {
13
14 std::vector<SimplexId> offsets(vertexNumber + 1);
15 // number of edges processed per vertex
16 std::vector<SimplexId> edgesId(vertexNumber);
17
18 Timer t;
19
20 printMsg("Building vertex edges", 0, 0, 1, ttk::debug::LineMode::REPLACE);
21
22 // store number of edges per vertex
23 for(const auto &e : edgeList) {
24 offsets[e[0] + 1]++;
25 offsets[e[1] + 1]++;
26 }
27
28 // compute partial sum of number of neighbors per vertex
29 for(size_t i = 1; i < offsets.size(); ++i) {
30 offsets[i] += offsets[i - 1];
31 }
32
33 // allocate flat neighbors vector
34 std::vector<SimplexId> data(offsets.back());
35
36 // fill flat data vector using offsets and edges count vectors
37 for(size_t i = 0; i < edgeList.size(); ++i) {
38 const auto &e{edgeList[i]};
39 data[offsets[e[0]] + edgesId[e[0]]] = i;
40 edgesId[e[0]]++;
41 data[offsets[e[1]] + edgesId[e[1]]] = i;
42 edgesId[e[1]]++;
43 }
44
45 // fill FlatJaggedArray struct
46 vertexEdges.setData(std::move(data), std::move(offsets));
47
48 printMsg("Built " + std::to_string(vertexNumber) + " vertex edges", 1,
49 t.getElapsedTime(), 1);
50
51 // ethaneDiolMedium.vtu, 70Mtets, hal9000 (12coresHT)
52 // 1 thread: 11.85 s
53 // 24 threads: 20.93 s [not efficient]
54
55 return 0;
56}
57
58// 2D cells (triangles)
60 const FlatJaggedArray &vertexStars,
61 const std::vector<std::array<SimplexId, 3>> &cellEdges,
62 const std::vector<std::array<SimplexId, 2>> &edgeList,
63 FlatJaggedArray &vertexLinks) const {
64
65#ifndef TTK_ENABLE_KAMIKAZE
66 if(vertexStars.empty())
67 return -1;
68 if(cellEdges.empty())
69 return -2;
70 if(edgeList.empty())
71 return -3;
72#endif
73
74 Timer t;
75
76 const SimplexId vertexNumber = vertexStars.size();
77 std::vector<SimplexId> offsets(vertexNumber + 1);
78 // one edge per star
79 std::vector<SimplexId> links(vertexStars.dataSize());
80
81 printMsg("Building vertex links", 0, 0, threadNumber_,
83
84#ifdef TTK_ENABLE_OPENMP
85#pragma omp parallel for num_threads(threadNumber_)
86#endif // TTK_ENABLE_OPENMP
87 for(SimplexId i = 0; i < vertexNumber; i++) {
88
89 // copy the vertexStars offsets array
90 offsets[i] = vertexStars.offset(i);
91
92 for(SimplexId j = 0; j < vertexStars.size(i); j++) {
93 // for each cell/triangle in vertex i's star, get the opposite edge
94 for(size_t k = 0; k < cellEdges[vertexStars.get(i, j)].size(); k++) {
95 const auto e = cellEdges[vertexStars.get(i, j)][k];
96 if(i != edgeList[e][0] && i != edgeList[e][1]) {
97 links[offsets[i] + j] = e;
98 break;
99 }
100 }
101 }
102 }
103
104 // don't forget the last offset
105 offsets[vertexNumber] = vertexStars.offset(vertexNumber);
106
107 vertexLinks.setData(std::move(links), std::move(offsets));
108
109 printMsg("Built " + std::to_string(vertexNumber) + " vertex links", 1,
111
112 return 0;
113}
114
115// 3D cells (tetrahedron)
117 const FlatJaggedArray &vertexStars,
118 const std::vector<std::array<SimplexId, 4>> &cellTriangles,
119 const std::vector<std::array<SimplexId, 3>> &triangleList,
120 FlatJaggedArray &vertexLinks) const {
121
122#ifndef TTK_ENABLE_KAMIKAZE
123 if(vertexStars.empty())
124 return -1;
125 if(cellTriangles.empty())
126 return -2;
127 if(triangleList.empty())
128 return -3;
129#endif
130
131 Timer tm;
132
133 const SimplexId vertexNumber = vertexStars.size();
134 std::vector<SimplexId> offsets(vertexNumber + 1);
135 // one triangle per star
136 std::vector<SimplexId> links(vertexStars.dataSize());
137
138 printMsg("Building vertex links", 0, 0, threadNumber_,
140
141#ifdef TTK_ENABLE_OPENMP
142#pragma omp parallel for num_threads(threadNumber_)
143#endif // TTK_ENABLE_OPENMP
144 for(SimplexId i = 0; i < vertexNumber; i++) {
145
146 // copy the vertexStars offsets array
147 offsets[i] = vertexStars.offset(i);
148
149 for(SimplexId j = 0; j < vertexStars.size(i); j++) {
150 // for each cell/tetra in vertex i's star, get the opposite triangle
151 for(size_t k = 0; k < cellTriangles[vertexStars.get(i, j)].size(); k++) {
152 const auto t = cellTriangles[vertexStars.get(i, j)][k];
153 if(i != triangleList[t][0] && i != triangleList[t][1]
154 && i != triangleList[t][2]) {
155 links[offsets[i] + j] = t;
156 break;
157 }
158 }
159 }
160 }
161
162 // don't forget the last offset
163 offsets[vertexNumber] = vertexStars.offset(vertexNumber);
164
165 vertexLinks.setData(std::move(links), std::move(offsets));
166
167 printMsg("Built " + std::to_string(vertexNumber) + " vertex links", 1,
169
170 return 0;
171}
172
174 const SimplexId &vertexNumber,
175 FlatJaggedArray &vertexNeighbors,
176 const std::vector<std::array<SimplexId, 2>> &edgeList) const {
177
178 std::vector<SimplexId> offsets(vertexNumber + 1);
179 // number of neighbors processed per vertex
180 std::vector<SimplexId> neighborsId(vertexNumber);
181
182 Timer t;
183
184 printMsg("Building vertex neighbors", 0, 0, 1, ttk::debug::LineMode::REPLACE);
185
186 // store number of neighbors per vertex
187 for(const auto &e : edgeList) {
188 offsets[e[0] + 1]++;
189 offsets[e[1] + 1]++;
190 }
191
192 // compute partial sum of number of neighbors per vertex
193 for(size_t i = 1; i < offsets.size(); ++i) {
194 offsets[i] += offsets[i - 1];
195 }
196
197 // allocate flat neighbors vector
198 std::vector<SimplexId> neighbors(offsets.back());
199
200 // fill flat neighbors vector using offsets and neighbors count vectors
201 for(const auto &e : edgeList) {
202 neighbors[offsets[e[0]] + neighborsId[e[0]]] = e[1];
203 neighborsId[e[0]]++;
204 neighbors[offsets[e[1]] + neighborsId[e[1]]] = e[0];
205 neighborsId[e[1]]++;
206 }
207
208 // fill FlatJaggedArray struct
209 vertexNeighbors.setData(std::move(neighbors), std::move(offsets));
210
211 printMsg("Built " + std::to_string(vertexNumber) + " vertex neighbors", 1,
212 t.getElapsedTime(), 1);
213
214 // ethaneDiolMedium.vtu, 70Mtets, hal9000 (12coresHT)
215 // (only merging step, after edge list creation)
216 // 1 thread: 9.16 s
217 // 24 threads: 13.21 s [not efficient in parallel]
218
219 return 0;
220}
221
223 const CellArray &cellArray,
224 FlatJaggedArray &vertexStars) const {
225
226 Timer t;
227
228 printMsg("Building vertex stars", 0, 0, 1, ttk::debug::LineMode::REPLACE);
229
230 std::vector<SimplexId> offsets(vertexNumber + 1);
231 // number of cells processed per vertex
232 std::vector<SimplexId> cellIds(vertexNumber);
233
234 const auto cellNumber = cellArray.getNbCells();
235
236 // store number of stars per vertex
237 for(SimplexId i = 0; i < cellNumber; ++i) {
238 const auto nbVertCell = cellArray.getCellVertexNumber(i);
239 for(SimplexId j = 0; j < nbVertCell; ++j) {
240 offsets[cellArray.getCellVertex(i, j) + 1]++;
241 }
242 }
243
244 // compute partial sum of number of stars per vertex
245 for(size_t i = 1; i < offsets.size(); ++i) {
246 offsets[i] += offsets[i - 1];
247 }
248
249 // allocate flat data vector
250 std::vector<SimplexId> data(offsets.back());
251
252 // fill flat data vector using offsets and edges count vectors
253 for(SimplexId i = 0; i < cellNumber; ++i) {
254 const auto nbVertCell = cellArray.getCellVertexNumber(i);
255 for(SimplexId j = 0; j < nbVertCell; ++j) {
256 const auto v = cellArray.getCellVertex(i, j);
257 data[offsets[v] + cellIds[v]] = i;
258 cellIds[v]++;
259 }
260 }
261
262 // fill FlatJaggedArray struct
263 vertexStars.setData(std::move(data), std::move(offsets));
264
265 printMsg("Built " + std::to_string(vertexNumber) + " vertex stars", 1,
266 t.getElapsedTime(), 1);
267
268 // ethaneDiol.vtu, 8.7Mtets, hal9000 (12coresHT)
269 // 1 thread: 0.53 s
270 // 24 threads: 7.99 s
271
272 return 0;
273}
int threadNumber_
Definition: BaseClass.h:95
CellArray generic array of cells
LongSimplexId getCellVertex(const LongSimplexId cellId, const SimplexId localVertId) const
LongSimplexId getNbCells() const
Get the number of cells in the array.
SimplexId getCellVertexNumber(const LongSimplexId cellId) const
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
Replacement for std::vector<std::vector<SimplexId>>
size_t dataSize() const
Returns the size of the data_ member.
SimplexId get(SimplexId id, SimplexId local) const
Returns the data inside the sub-vectors.
void setData(std::vector< SimplexId > &&data, std::vector< SimplexId > &&offsets)
Set internal data from pre-existing vectors.
SimplexId size(SimplexId id) const
Get the size of a particular sub-vector.
SimplexId offset(SimplexId id) const
Get the offset of a particular sub-vector.
bool empty() const
If the underlying buffers are empty.
double getElapsedTime()
Definition: Timer.h:15
int buildVertexEdges(const SimplexId &vertexNumber, const std::vector< std::array< SimplexId, 2 > > &edgeList, FlatJaggedArray &vertexEdges) const
Definition: ZeroSkeleton.cpp:9
int buildVertexStars(const SimplexId &vertexNumber, const CellArray &cellArray, FlatJaggedArray &vertexStars) const
int buildVertexLinks(const FlatJaggedArray &vertexStars, const std::vector< std::array< SimplexId, 3 > > &cellEdges, const std::vector< std::array< SimplexId, 2 > > &edgeList, FlatJaggedArray &vertexLinks) const
int buildVertexNeighbors(const SimplexId &vertexNumber, FlatJaggedArray &vertexNeighbors, const std::vector< std::array< SimplexId, 2 > > &edgeList) const
The Topology ToolKit.
int SimplexId
Identifier type for simplices of any dimension.
Definition: DataTypes.h:22