TTK
Loading...
Searching...
No Matches
PlanarGraphLayout.h
Go to the documentation of this file.
1
33
34#pragma once
35
36#include <map>
37
38// base code includes
39#include <Debug.h>
40
41namespace ttk {
42
43 class PlanarGraphLayout : virtual public Debug {
44
45 public:
48
49 template <typename ST, typename IT, typename CT>
50 int computeLayout(
51 // Output
52 float *layout,
53
54 // Input
55 const CT *connectivityList,
56 const size_t &nPoints,
57 const size_t &nEdges,
58 const ST *pointSequences,
59 const float *sizes,
60 const IT *branches,
61 const IT *levels) const;
62
63 template <typename IT, typename CT>
64 int extractLevel(
65 // Output
66 std::vector<size_t> &nodeIndices,
67 std::vector<size_t> &edgeIndices,
68
69 // Input
70 const CT *connectivityList,
71 const size_t &nPoints,
72 const size_t &nEdges,
73 const IT &level,
74 const IT *levels) const;
75
76 template <typename ST, typename IT, typename CT>
78 // Output
79 std::string &dotString,
80
81 // Input
82 const CT *connectivityList,
83 const ST *pointSequences,
84 const float *sizes,
85 const IT *branches,
86 const std::vector<size_t> &nodeIndices,
87 const std::vector<size_t> &edgeIndices,
88 const std::map<ST, size_t> &sequenceValueToIndexMap) const;
89
90 template <typename IT, typename CT>
91 int computeSlots(
92 // Output
93 float *layout,
94
95 // Input
96 const CT *connectivityList,
97 const size_t &nPoints,
98 const size_t &nEdges,
99 const float *sizes,
100 const IT *levels,
101 const IT &nLevels) const;
102
103 // Compute Dot Layout
105 // Output
106 float *layout,
107
108 // Input
109 const std::vector<size_t> &nodeIndices,
110 const std::string &dotString) const;
111 };
112} // namespace ttk
113
114// =============================================================================
115// Extract Level
116// =============================================================================
117template <typename IT, typename CT>
119 // Output
120 std::vector<size_t> &nodeIndices,
121 std::vector<size_t> &edgeIndices,
122
123 // Input
124 const CT *connectivityList,
125 const size_t &nPoints,
126 const size_t &nEdges,
127 const IT &level,
128 const IT *levels) const {
129
130 // If levels==nullptr then return all points and edges
131 if(levels == nullptr) {
132 nodeIndices.resize(nPoints);
133 for(size_t i = 0; i < nPoints; i++)
134 nodeIndices[i] = i;
135
136 edgeIndices.resize(nEdges);
137 for(size_t i = 0; i < nEdges; i++)
138 edgeIndices[i] = i;
139
140 return 1;
141 }
142
143 // Get nodes at level
144 for(size_t i = 0; i < nPoints; i++)
145 if(levels[i] == level)
146 nodeIndices.push_back(i);
147
148 // Get edges at level
149 size_t nEdges2 = nEdges * 2;
150 for(size_t i = 0; i < nEdges2; i += 2) {
151 auto n0l = levels[connectivityList[i + 0]];
152 auto n1l = levels[connectivityList[i + 1]];
153 if(n0l == level && n0l == n1l)
154 edgeIndices.push_back(i / 2);
155 }
156
157 return 1;
158}
159
160// =============================================================================
161// Compute Dot String
162// =============================================================================
163template <typename ST, typename IT, typename CT>
165 // Output
166 std::string &dotString,
167
168 // Input
169 const CT *connectivityList,
170 const ST *pointSequences,
171 const float *sizes,
172 const IT *branches,
173 const std::vector<size_t> &nodeIndices,
174 const std::vector<size_t> &edgeIndices,
175 const std::map<ST, size_t> &sequenceValueToIndexMap) const {
176
177 Timer t;
178
179 this->printMsg("Generating DOT String", 0, debug::LineMode::REPLACE);
180
181 bool useSequences = pointSequences != nullptr;
182 bool useSizes = sizes != nullptr;
183 bool useBranches = branches != nullptr;
184
185 std::string headString = "digraph g {rankdir=LR;";
186 std::string nodeString = "";
187 std::string edgeString = "";
188 std::string rankString = "";
189
190 // lambda functions that generate string representations of nodes
191 auto sl = [](size_t s) { return "\"s" + std::to_string(s) + "\""; };
192 auto nl = [](size_t id) { return std::to_string(id); };
193
194 // ---------------------------------------------------------------------------
195 // Nodes
196 // ---------------------------------------------------------------------------
197 {
198 // Set default node style
199 nodeString += "node[label=\"\",shape=box,width=1,height=1];";
200
201 // If useSizes then map size to node height
202 if(useSizes)
203 for(auto &i : nodeIndices)
204 nodeString += nl(i) + "[height=" + std::to_string(sizes[i]) + "];";
205 }
206
207 // ---------------------------------------------------------------------------
208 // Ranks
209 // ---------------------------------------------------------------------------
210 if(useSequences) {
211 size_t nSequenceValues = sequenceValueToIndexMap.size();
212
213 // Sequence Chain
214 {
215 edgeString += sl(0);
216 for(size_t s = 1; s < nSequenceValues; s++)
217 edgeString += "->" + sl(s);
218 edgeString += "[weight=1];";
219 }
220
221 // Collect nodes with the same sequence index
222 std::vector<std::vector<size_t>> sequenceIndexToPointIndexMap(
223 nSequenceValues);
224 for(auto &i : nodeIndices)
225 sequenceIndexToPointIndexMap
226 [sequenceValueToIndexMap.find(pointSequences[i])->second]
227 .push_back(i);
228
229 // Compute individual ranks
230 for(size_t s = 0; s < nSequenceValues; s++) {
231 rankString += "{rank=same " + sl(s);
232
233 auto &nodes = sequenceIndexToPointIndexMap[s];
234 for(auto &i : nodes)
235 rankString += " " + nl(i);
236
237 rankString += "}";
238 }
239 }
240
241 // ---------------------------------------------------------------------------
242 // Edges
243 // ---------------------------------------------------------------------------
244 {
245 for(auto &edgeIndex : edgeIndices) {
246 size_t temp = edgeIndex * 2;
247 auto &i0 = connectivityList[temp + 0];
248 auto &i1 = connectivityList[temp + 1];
249 edgeString += nl(i0) + "->" + nl(i1);
250
251 if(useBranches) {
252 auto b0 = branches[i0];
253 auto b1 = branches[i1];
254 edgeString += b0 == b1 ? "[weight=1]" : "[weight=0]";
255 }
256
257 edgeString += ";";
258 }
259 }
260
261 // ---------------------------------------------------------------------------
262 // Finalize
263 // ---------------------------------------------------------------------------
264
265 // Build Dot String
266 { dotString = headString + nodeString + edgeString + rankString + "}"; }
267
268 // Print Status
269 this->printMsg("Generating DOT string", 1, t.getElapsedTime());
270 this->printMsg("\n" + dotString + "\n", debug::Priority::VERBOSE);
271
272 return 1;
273}
274
275// =============================================================================
276// Compute Slots
277// =============================================================================
278template <typename IT, typename CT>
280 // Output
281 float *layout,
282
283 // Input
284 const CT *connectivityList,
285 const size_t &nPoints,
286 const size_t &nEdges,
287 const float *sizes,
288 const IT *levels,
289 const IT &nLevels) const {
290
291 if(sizes == nullptr || levels == nullptr) {
292 return -1;
293 }
294
295 Timer t;
296 this->printMsg("Computing slots", 0, debug::LineMode::REPLACE);
297
298 // Comparator that sorts children based on layout.y
299 struct ChildrenComparator {
300 const float *layout_;
301
302 ChildrenComparator(const float *layout) : layout_(layout) {
303 }
304
305 inline bool operator()(const size_t &i, const size_t &j) {
306 return layout_[i * 2 + 1] < layout_[j * 2 + 1];
307 }
308 };
309
310 auto comparator = ChildrenComparator(layout);
311
312 // ---------------------------------------------------------------------------
313 // Compute Children
314 // ---------------------------------------------------------------------------
315 std::vector<std::vector<size_t>> nodeIndexChildrenIndexMap(nPoints);
316
317 size_t nEdges2 = nEdges * 2;
318 for(size_t i = 0; i < nEdges2; i += 2) {
319 auto n0 = connectivityList[i + 0];
320 auto n1 = connectivityList[i + 1];
321 if((levels[n0] + 1) == levels[n1])
322 nodeIndexChildrenIndexMap[n0].push_back(n1);
323 }
324
325 // ---------------------------------------------------------------------------
326 // Adjust positions from bottom to top (skip last level)
327 // ---------------------------------------------------------------------------
328 for(IT l = 0; l < nLevels - 1; l++) {
329 std::vector<size_t> nodeIndices;
330 std::vector<size_t> edgeIndices;
331
332 // get nodes at current level (parents)
333 this->extractLevel<IT, CT>(
334 // Output
335 nodeIndices, edgeIndices,
336
337 // Input
338 connectivityList, nPoints, nEdges, l, levels);
339
340 // for each parent adjust position of children
341 for(auto &parent : nodeIndices) {
342 auto &children = nodeIndexChildrenIndexMap[parent];
343 size_t nChildren = children.size();
344 if(nChildren < 1)
345 continue;
346
347 // sort children
348 sort(children.begin(), children.end(), comparator);
349
350 // size of parent
351 float sizeParent = sizes[parent];
352
353 // size of child
354 float sizeChildren = 0;
355 for(auto &child : children)
356 sizeChildren += sizes[child];
357
358 // gap space
359 float gap = sizeParent - sizeChildren;
360 float gapDelta = (gap / (nChildren + 1)) / 2;
361
362 float y = layout[parent * 2 + 1] + sizeParent * 0.5 - gapDelta;
363 for(auto &child : children) {
364 float temp = gapDelta + sizes[child] / 2;
365 layout[child * 2 + 1] = y - temp;
366 y -= 2 * temp;
367 }
368 }
369 }
370
371 this->printMsg("Computing slots", 1, t.getElapsedTime());
372
373 return 1;
374}
375
376// =============================================================================
377// Execute
378// =============================================================================
379template <typename ST, typename IT, typename CT>
381 // Output
382 float *layout,
383
384 // Input
385 const CT *connectivityList,
386 const size_t &nPoints,
387 const size_t &nEdges,
388 const ST *pointSequences,
389 const float *sizes,
390 const IT *branches,
391 const IT *levels) const {
392
393 Timer t;
394
395 // Init Input
396 bool useSequences = pointSequences != nullptr;
397 bool useSizes = sizes != nullptr;
398 bool useBranches = branches != nullptr;
399 bool useLevels = levels != nullptr;
400
401 // Print Input
402 {
403 std::string modeS = "";
404 if(useSequences)
405 modeS += "Sequence + ";
406 if(useSizes)
407 modeS += "Size + ";
408 if(useBranches)
409 modeS += "Branches + ";
410 if(useLevels)
411 modeS += "Levels + ";
412
414 this->printMsg({{"#Nodes", std::to_string(nPoints)},
415 {"#Edges", std::to_string(nEdges)},
416 {"Mode", modeS.substr(0, modeS.length() - 3)}});
418 }
419
420 if(useLevels && !useSizes) {
421 this->printErr("'UseLevels' requires 'UseSizes'.");
422 return 0;
423 }
424
425 // Global SequenceValue to SequenceIndex map
426 std::map<ST, size_t> sequenceValueToIndexMap;
427 if(useSequences) {
428 for(size_t i = 0; i < nPoints; i++)
429 sequenceValueToIndexMap[pointSequences[i]] = 0;
430 size_t i = 0;
431 for(auto &el : sequenceValueToIndexMap)
432 el.second = i++;
433 }
434
435 // Get number of levels
436 IT nLevels = 1;
437 if(useLevels) {
438 for(size_t i = 0; i < nPoints; i++)
439 if(nLevels < levels[i])
440 nLevels = levels[i];
441 nLevels += 1;
442 }
443
444 // ---------------------------------------------------------------------------
445 // Compute initial layout for each level
446 // ---------------------------------------------------------------------------
447 for(IT l = 0; l < nLevels; l++) {
448 std::vector<size_t> nodeIndices;
449 std::vector<size_t> edgeIndices;
450
451 // Extract nodes and edges at certain level
452 {
453 int status = this->extractLevel<IT, CT>(
454 // Output
455 nodeIndices, edgeIndices,
456
457 // Input
458 connectivityList, nPoints, nEdges, l, levels);
459 if(status != 1)
460 return 0;
461 }
462
463 // Compute Dot String
464 std::string dotString;
465 {
466 int status = this->computeDotString<ST, IT, CT>(
467 // Output
468 dotString,
469
470 // Input
471 connectivityList, pointSequences, sizes, branches, nodeIndices,
472 edgeIndices, sequenceValueToIndexMap);
473 if(status != 1)
474 return 0;
475 }
476
477 // Compute Dot Layout
478 {
479 int status = this->computeDotLayout(layout, nodeIndices, dotString);
480 if(status != 1)
481 return 0;
482 }
483 }
484
485 // ---------------------------------------------------------------------------
486 // If nLevels>1 then compute slots
487 // ---------------------------------------------------------------------------
488 if(nLevels > 1) {
489 this->computeSlots<IT, CT>(
490 // Output
491 layout,
492
493 // Input
494 connectivityList, nPoints, nEdges, sizes, levels, nLevels);
495 }
496
497 // ---------------------------------------------------------------------------
498 // Print performance
499 // ---------------------------------------------------------------------------
501 this->printMsg("Complete", 1, t.getElapsedTime());
503
504 return 1;
505}
Minimalist debugging class.
Definition: Debug.h:88
TTK planarGraphLayout processing package.
int computeLayout(float *layout, const CT *connectivityList, const size_t &nPoints, const size_t &nEdges, const ST *pointSequences, const float *sizes, const IT *branches, const IT *levels) const
~PlanarGraphLayout() override
int computeDotString(std::string &dotString, const CT *connectivityList, const ST *pointSequences, const float *sizes, const IT *branches, const std::vector< size_t > &nodeIndices, const std::vector< size_t > &edgeIndices, const std::map< ST, size_t > &sequenceValueToIndexMap) const
int computeSlots(float *layout, const CT *connectivityList, const size_t &nPoints, const size_t &nEdges, const float *sizes, const IT *levels, const IT &nLevels) const
int computeDotLayout(float *layout, const std::vector< size_t > &nodeIndices, const std::string &dotString) const
int extractLevel(std::vector< size_t > &nodeIndices, std::vector< size_t > &edgeIndices, const CT *connectivityList, const size_t &nPoints, const size_t &nEdges, const IT &level, const IT *levels) const
double getElapsedTime()
Definition: Timer.h:15
The Topology ToolKit.
printMsg(debug::output::GREEN+"                           "+debug::output::ENDCOLOR+debug::output::GREEN+"▒"+debug::output::ENDCOLOR+debug::output::GREEN+"▒▒▒▒▒▒▒▒▒▒▒▒▒░"+debug::output::ENDCOLOR, debug::Priority::PERFORMANCE, debug::LineMode::NEW, stream)