VTK-m  2.0
ActiveGraph.h
Go to the documentation of this file.
1 //============================================================================
2 // Copyright (c) Kitware, Inc.
3 // All rights reserved.
4 // See LICENSE.txt for details.
5 //
6 // This software is distributed WITHOUT ANY WARRANTY; without even
7 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 // PURPOSE. See the above copyright notice for more information.
9 //============================================================================
10 // Copyright (c) 2018, The Regents of the University of California, through
11 // Lawrence Berkeley National Laboratory (subject to receipt of any required approvals
12 // from the U.S. Dept. of Energy). All rights reserved.
13 //
14 // Redistribution and use in source and binary forms, with or without modification,
15 // are permitted provided that the following conditions are met:
16 //
17 // (1) Redistributions of source code must retain the above copyright notice, this
18 // list of conditions and the following disclaimer.
19 //
20 // (2) Redistributions in binary form must reproduce the above copyright notice,
21 // this list of conditions and the following disclaimer in the documentation
22 // and/or other materials provided with the distribution.
23 //
24 // (3) Neither the name of the University of California, Lawrence Berkeley National
25 // Laboratory, U.S. Dept. of Energy nor the names of its contributors may be
26 // used to endorse or promote products derived from this software without
27 // specific prior written permission.
28 //
29 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
30 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
31 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
32 // IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
33 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
34 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
36 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
37 // OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
38 // OF THE POSSIBILITY OF SUCH DAMAGE.
39 //
40 //=============================================================================
41 //
42 // This code is an extension of the algorithm presented in the paper:
43 // Parallel Peak Pruning for Scalable SMP Contour Tree Computation.
44 // Hamish Carr, Gunther Weber, Christopher Sewell, and James Ahrens.
45 // Proceedings of the IEEE Symposium on Large Data Analysis and Visualization
46 // (LDAV), October 2016, Baltimore, Maryland.
47 //
48 // The PPP2 algorithm and software were jointly developed by
49 // Hamish Carr (University of Leeds), Gunther H. Weber (LBNL), and
50 // Oliver Ruebel (LBNL)
51 //==============================================================================
52 
53 #ifndef vtk_m_worklet_contourtree_augmented_activegraph_h
54 #define vtk_m_worklet_contourtree_augmented_activegraph_h
55 
56 #include <iomanip>
57 #include <numeric>
58 
59 // local includes
89 
90 
91 //VTKM includes
92 #include <vtkm/Types.h>
93 #include <vtkm/cont/Algorithm.h>
95 #include <vtkm/cont/ArrayHandle.h>
101 #include <vtkm/cont/Error.h>
102 #include <vtkm/cont/Invoker.h>
103 
104 
106 
107 
108 namespace vtkm
109 {
110 namespace worklet
111 {
112 namespace contourtree_augmented
113 {
114 
115 
117 { // class ActiveGraph
118 
119  template <typename T, typename S>
121  {
122  return vtkm::cont::ArrayGetValue(ah.GetNumberOfValues() - 1, ah);
123  }
124 
125 public:
127 
128  // we also need the orientation of the edges (i.e. is it join or split)
130 
131  // we will store the number of iterations the computation took here
133 
134  // ARRAYS FOR NODES IN THE TOPOLOGY GRAPH
135 
136  // for each vertex, we need to know where it is in global sort order / mesh
138 
139  // the hyperarcs - i.e. the pseudoextremum defining the hyperarc the vertex is on
141 
142  // the first edge for each vertex
144 
145  // the outdegree for each vertex
147 
148  // ARRAYS FOR EDGES IN THE TOPOLOGY GRAPH
149 
150  // we will also need to keep track of both near and far ends of each edge
153 
154  // these now track the active nodes, edges, &c.:
157 
158  // and an array for sorting edges
160 
161  // temporary arrays for super/hyper ID numbers
164 
165  // variables tracking size of super/hyper tree
168 
169  // BASIC ROUTINES: CONSTRUCTOR, PRINT, &c.
170 
171  // constructor takes necessary references
172  ActiveGraph(bool IsJoinGraph);
173 
174  // initialises the active graph
175  template <class Mesh>
176  void Initialise(Mesh& mesh, const MeshExtrema& meshExtrema);
177 
178  // routine that computes the merge tree from the active graph
179  // was previously Compute()
180  void MakeMergeTree(MergeTree& tree, MeshExtrema& meshExtrema);
181 
182  // sorts saddle starts to find governing saddles
183  void FindGoverningSaddles();
184 
185  // marks now regular points for removal
186  void TransferRegularPoints();
187 
188  // compacts the active vertex list
189  void CompactActiveVertices();
190 
191  // compacts the active edge list
192  void CompactActiveEdges();
193 
194  // builds the chains for the new active vertices
195  void BuildChains();
196 
197  // suppresses non-saddles for the governing saddles pass
198  void TransferSaddleStarts();
199 
200  // sets all remaining active vertices
201  void BuildTrunk();
202 
203  // finds all super and hyper nodes, numbers them & sets up arrays for lookup
204  void FindSuperAndHyperNodes(MergeTree& tree);
205 
206  // uses active graph to set superarcs & hyperparents in merge tree
207  void SetSuperArcs(MergeTree& tree);
208 
209  // uses active graph to set hypernodes in merge tree
210  void SetHyperArcs(MergeTree& tree);
211 
212  // uses active graph to set arcs in merge tree
213  void SetArcs(MergeTree& tree, MeshExtrema& meshExtrema);
214 
215  // Allocate the vertex array
216  void AllocateVertexArrays(vtkm::Id nElems);
217 
218  // Allocate the edge array
219  void AllocateEdgeArrays(vtkm::Id nElems);
220 
221  // releases temporary arrays
222  void ReleaseTemporaryArrays();
223 
224  // prints the contents of the active graph in a standard format
225  void DebugPrint(const char* message, const char* fileName, long lineNum);
226 
227 }; // class ActiveGraph
228 
229 
230 // constructor takes necessary references
231 inline ActiveGraph::ActiveGraph(bool isJoinGraph)
232  : Invoke()
233  , IsJoinGraph(isJoinGraph)
234 { // constructor
235  this->NumIterations = 0;
236  this->NumSupernodes = 0;
237  this->NumHypernodes = 0;
238 } // constructor
239 
240 
241 
242 // initialises the active graph
243 template <class Mesh>
244 inline void ActiveGraph::Initialise(Mesh& mesh, const MeshExtrema& meshExtrema)
245 { // InitialiseActiveGraph()
246  // reference to the correct array in the extrema
247  const IdArrayType& extrema = this->IsJoinGraph ? meshExtrema.Peaks : meshExtrema.Pits;
248 
249  // For every vertex, work out whether it is critical
250  // We do so by computing outdegree in the mesh & suppressing the vertex if outdegree is 1
251  // All vertices of outdegree 0 must be extrema
252  // Saddle points must be at least outdegree 2, so this is a correct test
253  // BUT it is possible to overestimate the degree of a non-extremum,
254  // The test is therefore necessary but not sufficient, and extra vertices are put in the active graph
255 
256  // Neighbourhood mask (one bit set per connected component in neighbourhood
257  IdArrayType neighbourhoodMasks;
258  neighbourhoodMasks.Allocate(mesh.NumVertices);
259  IdArrayType outDegrees; // TODO Should we change this to an unsigned type
260  outDegrees.Allocate(mesh.NumVertices);
261 
262  // Initialize the nerighborhoodMasks and outDegrees arrays
263  mesh.SetPrepareForExecutionBehavior(this->IsJoinGraph);
264  vtkm::cont::ArrayHandleIndex sortIndexArray(mesh.NumVertices);
266  this->IsJoinGraph);
267 
268  this->Invoke(initNeighMasksAndOutDegWorklet,
269  sortIndexArray,
270  mesh,
271  neighbourhoodMasks, // output
272  outDegrees); // output
273 
274  // next, we compute where each vertex lands in the new array
275  // it needs to be one place offset, hence the +/- 1
276  // this should automatically parallelise
277  // The following commented code block is variant ported directly from PPP2 using std::partial_sum. This has been replaced here with vtkm's ScanExclusive.
278  /*auto oneIfCritical = [](unsigned x) { return x!= 1 ? 1 : 0; };
279 
280  // we need a temporary inverse index to change vertex IDs
281  IdArrayType inverseIndex;
282  inverseIndex.Allocate(mesh.NumVertices);
283  inverseIndex.WritePortal().Set(0,0);
284 
285  std::partial_sum(
286  boost::make_transform_iterator(vtkm::cont::ArrayPortalToIteratorBegin(outDegrees.WritePortal()), oneIfCritical),
287  boost::make_transform_iterator(vtkm::cont::ArrayPortalToIteratorEnd(outDegrees.WritePortal())-1, oneIfCritical),
288  vtkm::cont::ArrayPortalToIteratorBegin(inverseIndex.WritePortal()) + 1);
289  */
290  IdArrayType inverseIndex;
291  OneIfCritical oneIfCriticalFunctor;
292  auto oneIfCriticalArrayHandle =
293  vtkm::cont::ArrayHandleTransform<IdArrayType, OneIfCritical>(outDegrees, oneIfCriticalFunctor);
294  vtkm::cont::Algorithm::ScanExclusive(oneIfCriticalArrayHandle, inverseIndex);
295 
296  // now we can compute how many critical points we carry forward
297  vtkm::Id nCriticalPoints =
298  this->GetLastValue(inverseIndex) + oneIfCriticalFunctor(this->GetLastValue(outDegrees));
299 
300  // we need to keep track of what the index of each vertex is in the active graph
301  // for most vertices, this should have the NO_SUCH_VERTEX flag set
303  nCriticalPoints); // allocates outdegree, GlobalIndex, Hyperarcs, ActiveVertices
304 
305  // our processing now depends on the degree of the vertex
306  // but basically, we want to set up the arrays for this vertex:
307  // activeIndex gets the next available ID in the active graph (was called nearIndex before)
308  // GlobalIndex stores the index in the join tree for later access
309  IdArrayType activeIndices;
310  activeIndices.Allocate(mesh.NumVertices);
312  static_cast<vtkm::Id>(NO_SUCH_ELEMENT), mesh.NumVertices);
313  vtkm::cont::Algorithm::Copy(noSuchElementArray, activeIndices);
314 
315  active_graph_inc_ns::InitializeActiveGraphVertices initActiveGraphVerticesWorklet;
316  this->Invoke(initActiveGraphVerticesWorklet,
317  sortIndexArray,
318  outDegrees,
319  inverseIndex,
320  extrema,
321  activeIndices,
322  this->GlobalIndex,
323  this->Outdegree,
324  this->Hyperarcs,
325  this->ActiveVertices);
326 
327  // now we need to compute the FirstEdge array from the outDegrees
328  this->FirstEdge.Allocate(nCriticalPoints);
329  // STD Version of the prefix sum
330  //this->FirstEdge.WritePortal().Set(0, 0);
331  //std::partial_sum(vtkm::cont::ArrayPortalToIteratorBegin(this->Outdegree.GetPortalControl()),
332  // vtkm::cont::ArrayPortalToIteratorEnd(this->Outdegree.GetPortalControl()) - 1,
333  // vtkm::cont::ArrayPortalToIteratorBegin(this->firstEdge.GetPortalControl()) + 1);
334  // VTKM Version of the prefix sum
336  // Compute the number of critical edges
337 
338  vtkm::Id nCriticalEdges =
339  this->GetLastValue(this->FirstEdge) + this->GetLastValue(this->Outdegree);
340 
341  AllocateEdgeArrays(nCriticalEdges);
342 
344  this->Invoke(initActiveEdgesWorklet,
345  this->Outdegree,
346  mesh,
347  this->FirstEdge,
348  this->GlobalIndex,
349  extrema,
350  neighbourhoodMasks,
351  this->EdgeNear,
352  this->EdgeFar,
353  this->ActiveEdges);
354 
355  // now we have to go through and set the far ends of the new edges using the
356  // inverse index array
358  this->Invoke(initEdgeFarWorklet, this->EdgeFar, extrema, activeIndices);
359 
360  DebugPrint("Active Graph Started", __FILE__, __LINE__);
361 
362  // then we loop through the active vertices to convert their indices to active graph indices
364  this->Invoke(initHyperarcsWorklet, this->Hyperarcs, activeIndices);
365 
366  // finally, allocate and initialise the edgeSorter array
369 
370  //DebugPrint("Active Graph Initialised", __FILE__, __LINE__);
371 } // InitialiseActiveGraph()
372 
373 
374 // routine that computes the merge tree from the active graph
375 // was previously Compute()
376 inline void ActiveGraph::MakeMergeTree(MergeTree& tree, MeshExtrema& meshExtrema)
377 { // MakeMergeTree()
378  DebugPrint("Active Graph Computation Starting", __FILE__, __LINE__);
379 
380  // loop until we run out of active edges
381  vtkm::Id maxNumIterations = this->EdgeSorter.GetNumberOfValues();
382  this->NumIterations = 0;
383  while (true)
384  { // main loop
385  // choose the subset of edges for the governing saddles
387 
388  // test whether there are any left (if not, we're on the trunk)
389  if (this->EdgeSorter.GetNumberOfValues() <= 0)
390  {
391  break;
392  }
393  // test whether we are in a bad infinite loop due to bad input data. Usually
394  // this is not an issue for the merge tree (only for the contour tree), but
395  // we check just to make absolutely sure we won't get stuck in an infinite loop
396  if (this->NumIterations >= maxNumIterations)
397  {
398  throw new vtkm::cont::ErrorInternal("Bad iteration. Merge tree unable to process all edges.");
399  }
400 
401  // find & label the extrema with their governing saddles
403 
404  // label the regular points
406 
407  // compact the active set of vertices & edges
410 
411  // rebuild the chains
412  BuildChains();
413 
414  // increment the iteration count
415  this->NumIterations++;
416  } // main loop
417 
418  // final pass to label the trunk vertices
419  BuildTrunk();
420 
421  // transfer results to merge tree
423  SetSuperArcs(tree);
424  SetHyperArcs(tree);
425  SetArcs(tree, meshExtrema);
426 
427  // we can now release many of the arrays to free up space
429 
430  DebugPrint("Merge Tree Computed", __FILE__, __LINE__);
431 } // MakeMergeTree()
432 
433 
434 // suppresses non-saddles for the governing saddles pass
436 { // TransferSaddleStarts()
437  // update all of the edges so that the far end resets to the result of the ascent in the previous step
438 
440  this->Invoke(transferSaddleResetWorklet, this->ActiveEdges, this->Hyperarcs, this->EdgeFar);
441 
442  // in parallel, we need to create a vector to count the first edge for each vertex
443  IdArrayType newOutdegree;
444  newOutdegree.Allocate(this->ActiveVertices.GetNumberOfValues());
445 
446  // this will be a stream compaction later, but for now we'll do it the serial way
448  this->Invoke(transferOutDegree,
449  this->ActiveVertices,
450  this->FirstEdge,
451  this->Outdegree,
452  this->ActiveEdges,
453  this->Hyperarcs,
454  this->EdgeFar,
455  newOutdegree);
456 
457  // now do a parallel prefix sum using the offset partial sum trick.
458  IdArrayType newFirstEdge;
459  newFirstEdge.Allocate(this->ActiveVertices.GetNumberOfValues());
460  // STD version of the prefix sum
461  // newFirstEdge.WritePortal().Set(0, 0);
462  // std::partial_sum(vtkm::cont::ArrayPortalToIteratorBegin(newOutdegree.WritePortal()),
463  // vtkm::cont::ArrayPortalToIteratorEnd(newOutdegree.WritePortal()) - 1,
464  // vtkm::cont::ArrayPortalToIteratorBegin(newFirstEdge.WritePortal()) + 1);
465  // VTK:M version of the prefix sum
466  vtkm::cont::Algorithm::ScanExclusive(newOutdegree, newFirstEdge);
467 
468  vtkm::Id nEdgesToSort = this->GetLastValue(newFirstEdge) + this->GetLastValue(newOutdegree);
469 
470  // now we write only the active saddle edges to the sorting array
471  this->EdgeSorter
472  .ReleaseResources(); // TODO is there a single way to resize an array handle without calling ReleaseResources followed by Allocate
473  this->EdgeSorter.Allocate(nEdgesToSort);
474 
475  // this will be a stream compaction later, but for now we'll do it the serial way
477  this->Invoke(updateEdgeSorterWorklet,
478  this->ActiveVertices,
479  this->ActiveEdges,
480  this->FirstEdge,
481  newFirstEdge,
482  newOutdegree,
483  this->EdgeSorter);
484 
485  DebugPrint("Saddle Starts Transferred", __FILE__, __LINE__);
486 } // TransferSaddleStarts()
487 
488 
489 // sorts saddle starts to find governing saddles
491 { // FindGoverningSaddles()
492  // sort with the comparator
494  this->EdgeSorter,
496 
497  // DebugPrint("After Sorting", __FILE__, __LINE__);
498 
499  // now loop through the edges to find the governing saddles
502 
503  this->Invoke(findGovSaddlesWorklet,
504  edgeIndexArray,
505  this->EdgeSorter,
506  this->EdgeFar,
507  this->EdgeNear,
508  this->Hyperarcs,
509  this->Outdegree);
510 
511  DebugPrint("Governing Saddles Set", __FILE__, __LINE__);
512 } // FindGoverningSaddles()
513 
514 
515 // marks now regular points for removal
517 { // TransferRegularPointsWorklet
518  // we need to label the regular points that have been identified
520  this->Invoke(transRegPtWorklet, this->ActiveVertices, this->Hyperarcs, this->Outdegree);
521 
522  DebugPrint("Regular Points Should Now Be Labelled", __FILE__, __LINE__);
523 } // TransferRegularPointsWorklet()
524 
525 
526 // compacts the active vertex list
528 { // CompactActiveVertices()
530 
531  // create a temporary array the same size
532  vtkm::cont::ArrayHandle<vtkm::Id> newActiveVertices;
533 
534  // Use only the current this->ActiveVertices this->Outdegree to match size on CopyIf
535  vtkm::cont::ArrayHandle<vtkm::Id> outdegreeLookup;
536  vtkm::cont::Algorithm::Copy(PermuteIndexType(this->ActiveVertices, this->Outdegree),
537  outdegreeLookup);
538 
539  // compact the this->ActiveVertices array to keep only the ones of interest
540  vtkm::cont::Algorithm::CopyIf(this->ActiveVertices, outdegreeLookup, newActiveVertices);
541 
543  vtkm::cont::Algorithm::Copy(newActiveVertices, this->ActiveVertices);
544 
545  DebugPrint("Active Vertex List Compacted", __FILE__, __LINE__);
546 } // CompactActiveVertices()
547 
548 
549 // compacts the active edge list
551 { // CompactActiveEdges()
552  // grab the size of the array for easier reference
553  vtkm::Id nActiveVertices = this->ActiveVertices.GetNumberOfValues();
554 
555  // first, we have to work out the first edge for each active vertex
556  // we start with a temporary new outdegree
557  IdArrayType newOutdegree;
558  newOutdegree.Allocate(nActiveVertices);
559 
560  // Run workflet to compute newOutdegree for each vertex
562  this->Invoke(computeNewOutdegreeWorklet,
563  this->ActiveVertices, // (input)
564  this->ActiveEdges, // (input)
565  this->EdgeFar, // (input)
566  this->FirstEdge, // (input)
567  this->Outdegree, // (input)
568  this->Hyperarcs, // (input/output)
569  newOutdegree // (output)
570  );
571 
572  // now we do a reduction to compute the offsets of each vertex
574  // newPosition.Allocate(nActiveVertices); // Not necessary. ScanExclusive takes care of this.
575  vtkm::cont::Algorithm::ScanExclusive(newOutdegree, newPosition);
576 
577  vtkm::Id nNewEdges = vtkm::cont::ArrayGetValue(nActiveVertices - 1, newPosition) +
578  vtkm::cont::ArrayGetValue(nActiveVertices - 1, newOutdegree);
579 
580  // create a temporary vector for copying
581  IdArrayType newActiveEdges;
582  newActiveEdges.Allocate(nNewEdges);
583  // overwriting Hyperarcs in parallel is safe, as the worst than can happen is
584  // that another valid ascent is found; for comparison and validation purposes
585  // however it makes sense to have a `canoical' computation. To achieve this
586  // canonical computation, we need to write into a new array during computation
587  // ensuring that we always use the same information. The following is left in
588  // commented out for future debugging and validation
589 
590  //DebugPrint("Active Edges Counted", __FILE__, __LINE__);
591 
592  // now copy the relevant edges into the active edge array
594  this->Invoke(transferActiveEdgesWorklet,
595  this->ActiveVertices,
596  newPosition, // (input)
597  newOutdegree, // (input)
598  this->ActiveEdges, // (input)
599  newActiveEdges, // (output)
600  this->EdgeFar, // (input/output)
601  this->FirstEdge, // (input/output)
602  this->Outdegree, // (input/output)
603  this->Hyperarcs // (input/output)
604  );
605 
606  // resize the original array and recopy
607  //vtkm::cont::Algorithm::::Copy(newActiveEdges, this-ActiveEdges);
609  // vtkm ArrayHandles are smart, so we can just swap it in without having to copy
610  this->ActiveEdges = newActiveEdges;
611 
612  // for canonical computation: swap in newly computed hyperarc array
613  // this->Hyperarcs.swap(newHyperarcs);
614 
615  DebugPrint("Active Edges Now Compacted", __FILE__, __LINE__);
616 } // CompactActiveEdges()
617 
618 
619 
620 // builds the chains for the new active vertices
622 { // BuildChains()
623  // 1. compute the number of log steps required in this pass
624  vtkm::Id numLogSteps = 1;
625  for (vtkm::Id shifter = this->ActiveVertices.GetNumberOfValues(); shifter != 0; shifter >>= 1)
626  numLogSteps++;
627 
628  // 2. Use path compression / step doubling to collect vertices along chains
629  // until every vertex has been assigned to *an* extremum
630  for (vtkm::Id logStep = 0; logStep < numLogSteps; logStep++)
631  { // per log step
632  active_graph_inc_ns::BuildChainsWorklet buildChainsWorklet;
633  this->Invoke(buildChainsWorklet, this->ActiveVertices, this->Hyperarcs);
634  } // per log step
635  DebugPrint("Chains Built", __FILE__, __LINE__);
636 } // BuildChains()
637 
638 
639 // sets all remaining active vertices
641 { //BuildTrunk
642  // all remaining vertices belong to the trunk
643  active_graph_inc_ns::BuildTrunkWorklet buildTrunkWorklet;
644  this->Invoke(buildTrunkWorklet, this->ActiveVertices, this->Hyperarcs);
645 
646  DebugPrint("Trunk Built", __FILE__, __LINE__);
647 } //BuildTrunk
648 
649 
650 // finds all super and hyper nodes, numbers them & sets up arrays for lookup
652 { // FindSuperAndHyperNodes()
653  // allocate memory for nodes
654  this->HyperID.ReleaseResources();
656 
657  // compute new node positions
658  // The following commented code block is variant ported directly from PPP2 using std::partial_sum. This has been replaced here with vtkm's ScanExclusive.
659  /*auto oneIfSupernode = [](vtkm::Id v) { return IsSupernode(v) ? 1 : 0; };
660  IdArrayType newSupernodePosition;
661  newSupernodePosition.Allocate(this->Hyperarcs.GetNumberOfValues());
662  newSupernodePosition.WritePortal().Set(0, 0);
663 
664  std::partial_sum(
665  boost::make_transform_iterator(vtkm::cont::ArrayPortalToIteratorBegin(this->Hyperarcs.WritePortal()), oneIfSupernode),
666  boost::make_transform_iterator(vtkm::cont::ArrayPortalToIteratorEnd(this->Hyperarcs.WritePortal()) - 1, oneIfSupernode),
667  vtkm::cont::ArrayPortalToIteratorBegin(newSupernodePosition.GetPortalControl()) + 1);*/
668 
669  IdArrayType newSupernodePosition;
670  OneIfSupernode oneIfSupernodeFunctor;
671  auto oneIfSupernodeArrayHandle = vtkm::cont::ArrayHandleTransform<IdArrayType, OneIfSupernode>(
672  this->Hyperarcs, oneIfSupernodeFunctor);
673  vtkm::cont::Algorithm::ScanExclusive(oneIfSupernodeArrayHandle, newSupernodePosition);
674 
675  this->NumSupernodes = this->GetLastValue(newSupernodePosition) +
676  oneIfSupernodeFunctor(this->GetLastValue(this->Hyperarcs));
677 
679  tree.Supernodes.Allocate(this->NumSupernodes);
680 
681  // The following commented code block is variant ported directly from PPP2 using std::partial_sum. This has been replaced here with vtkm's ScanExclusive.
682  /*
683  auto oneIfHypernode = [](vtkm::Id v) { return IsHypernode(v) ? 1 : 0; };
684  IdArrayType newHypernodePosition;
685  newHypernodePosition.Allocate(this->Hyperarcs.GetNumberOfValues());
686  newHypernodePosition.WritePortal().Set(0, 0);
687  std::partial_sum(
688  boost::make_transform_iterator(vtkm::cont::ArrayPortalToIteratorBegin(this->Hyperarcs.WritePortal()), oneIfHypernode),
689  boost::make_transform_iterator(vtkm::cont::ArrayPortalToIteratorEnd(this->Hyperarcs.WritePortal()) - 1, oneIfHypernode),
690  vtkm::cont::ArrayPortalToIteratorBegin(newHypernodePosition.GetPortalControl()) + 1);
691  */
692  IdArrayType newHypernodePosition;
693  OneIfHypernode oneIfHypernodeFunctor;
694  auto oneIfHypernodeArrayHandle = vtkm::cont::ArrayHandleTransform<IdArrayType, OneIfHypernode>(
695  this->Hyperarcs, oneIfHypernodeFunctor);
696  vtkm::cont::Algorithm::ScanExclusive(oneIfHypernodeArrayHandle, newHypernodePosition);
697 
698  this->NumHypernodes = this->GetLastValue(newHypernodePosition) +
699  oneIfHypernodeFunctor(this->GetLastValue(this->Hyperarcs));
700 
703 
704  // perform stream compression
705  active_graph_inc_ns::FindSuperAndHyperNodesWorklet findSuperAndHyperNodesWorklet;
707  this->Invoke(findSuperAndHyperNodesWorklet,
708  graphVertexIndex,
709  this->Hyperarcs,
710  newHypernodePosition,
711  newSupernodePosition,
712  this->HyperID,
713  tree.Hypernodes,
714  tree.Supernodes);
715 
716  DebugPrint("Super/Hypernodes Found", __FILE__, __LINE__);
717  tree.DebugPrint("Super/Hypernodes Found", __FILE__, __LINE__);
718 } // FindSuperAndHyperNodes()
719 
720 
721 // uses active graph to set superarcs & hyperparents in merge tree
723 { // SetSuperArcs()
725 
726  // 1. set the hyperparents
727  // allocate space for the hyperparents
729  tree.Hyperparents.Allocate(this->NumSupernodes);
730 
731  // execute the worklet to set the hyperparents
732  active_graph_inc_ns::SetSuperArcsSetTreeHyperparents setTreeHyperparentsWorklet;
733  this->Invoke(setTreeHyperparentsWorklet, tree.Supernodes, this->Hyperarcs, tree.Hyperparents);
734 
735  tree.DebugPrint("Hyperparents Set", __FILE__, __LINE__);
736  // a. And the super ID array needs setting up
737  this->SuperID.ReleaseResources();
740  this->SuperID);
741  vtkm::cont::ArrayHandleIndex supernodeIndex(this->NumSupernodes);
742  PermutedIdArrayType permutedSuperID(tree.Supernodes, this->SuperID);
743  vtkm::cont::Algorithm::Copy(supernodeIndex, permutedSuperID);
744 
745  // 2. Sort the supernodes into segments according to hyperparent
746  // See comparator for details
749  tree.Hyperparents, this->SuperID, tree.IsJoinTree));
750 
751  // 3. Now update the other arrays to match
752  IdArrayType hyperParentsTemp;
753  hyperParentsTemp.Allocate(this->NumSupernodes);
754  auto permutedTreeHyperparents = vtkm::cont::make_ArrayHandlePermutation(
756 
757  vtkm::cont::Algorithm::Copy(permutedTreeHyperparents, hyperParentsTemp);
758  vtkm::cont::Algorithm::Copy(hyperParentsTemp, tree.Hyperparents);
759  hyperParentsTemp.ReleaseResources();
760  // a. And the super ID array needs setting up // TODO Check if we really need this?
761  vtkm::cont::Algorithm::Copy(supernodeIndex, permutedSuperID);
762 
763  DebugPrint("Supernodes Sorted", __FILE__, __LINE__);
764  tree.DebugPrint("Supernodes Sorted", __FILE__, __LINE__);
765 
766  // 4. Allocate memory for superarcs
768  tree.Superarcs.Allocate(this->NumSupernodes);
771 
772  // 5. Each supernode points to its neighbour in the list, except at the end of segments
773  // execute the worklet to set the tree.Hyperparents and tree.FirstSuperchild
775  this->Invoke(setTreeSuperarcsWorklet,
776  tree.Supernodes, // (input)
777  this->Hyperarcs, // (input)
778  tree.Hyperparents, // (input)
779  this->SuperID, // (input)
780  this->HyperID, // (input)
781  tree.Superarcs, // (output)
782  tree.FirstSuperchild // (output)
783  );
784 
785  // 6. Now we can reset the supernodes to mesh IDs
786  PermutedIdArrayType permuteGlobalIndex(tree.Supernodes, this->GlobalIndex);
787  vtkm::cont::Algorithm::Copy(permuteGlobalIndex, tree.Supernodes);
788 
789  // 7. and the hyperparent to point to a hyperarc rather than a graph index
790  PermutedIdArrayType permuteHyperID(tree.Hyperparents, this->HyperID);
791  vtkm::cont::Algorithm::Copy(permuteHyperID, tree.Hyperparents);
792 
793  tree.DebugPrint("Superarcs Set", __FILE__, __LINE__);
794 } // SetSuperArcs()
795 
796 
797 // uses active graph to set hypernodes in merge tree
799 { // SetHyperArcs()
800  // 1. Allocate memory for hypertree
801  tree.Hypernodes.Allocate(
802  this->NumHypernodes, // Has been allocated previously.
803  vtkm::CopyFlag::On); // The values are needed but the size may be too large.
805  tree.Hyperarcs.Allocate(this->NumHypernodes); // Has not been allocated yet
806 
807  // 2. Use the superIDs already set to fill in the Hyperarcs array
808  active_graph_inc_ns::SetHyperArcsWorklet setHyperArcsWorklet;
809  this->Invoke(
810  setHyperArcsWorklet, tree.Hypernodes, tree.Hyperarcs, this->Hyperarcs, this->SuperID);
811 
812  // Debug output
813  DebugPrint("Hyperarcs Set", __FILE__, __LINE__);
814  tree.DebugPrint("Hyperarcs Set", __FILE__, __LINE__);
815 } // SetHyperArcs()
816 
817 
818 // uses active graph to set arcs in merge tree
819 inline void ActiveGraph::SetArcs(MergeTree& tree, MeshExtrema& meshExtrema)
820 { // SetArcs()
822 
823  // reference to the correct array in the extrema
824  const IdArrayType& extrema = this->IsJoinGraph ? meshExtrema.Peaks : meshExtrema.Pits;
825 
826  // 1. Set the arcs for the super/hypernodes based on where they prune to
827  active_graph_inc_ns::SetArcsSetSuperAndHypernodeArcs setSuperAndHypernodeArcsWorklet;
828  this->Invoke(setSuperAndHypernodeArcsWorklet,
829  this->GlobalIndex,
830  this->Hyperarcs,
831  this->HyperID,
832  tree.Arcs,
833  tree.Superparents);
834 
835  DebugPrint("Sliding Arcs Set", __FILE__, __LINE__);
836  tree.DebugPrint("Sliding Arcs Set", __FILE__, __LINE__);
837 
838  // 2. Loop through all vertices to slide down Hyperarcs
839  active_graph_inc_ns::SetArcsSlideVertices slideVerticesWorklet(
840  this->IsJoinGraph, this->NumSupernodes, this->NumHypernodes);
841  this->Invoke(slideVerticesWorklet,
842  tree.Arcs, // (input)
843  extrema, // (input) i.e,. meshExtrema.Peaks or meshExtrema.Pits
844  tree.FirstSuperchild, // (input)
845  tree.Supernodes, // (input)
846  tree.Superparents); // (input/output)
847 
848  tree.DebugPrint("Sliding Finished", __FILE__, __LINE__);
849 
850  // 3. Now set the superparents correctly for the supernodes
851  PermuteIndexType permuteTreeSuperparents(tree.Supernodes, tree.Superparents);
852  vtkm::cont::ArrayHandleIndex supernodesIndex(this->NumSupernodes);
853  vtkm::cont::Algorithm::Copy(supernodesIndex, permuteTreeSuperparents);
854 
855  tree.DebugPrint("Superparents Set", __FILE__, __LINE__);
856 
857  // 4. Finally, sort all of the vertices onto their superarcs
858  IdArrayType nodes;
860  vtkm::cont::Algorithm::Copy(nodesIndex, nodes);
861 
862  // 5. Sort the nodes into segments according to superparent
863  // See comparator for details
866 
867  // 6. Connect the nodes to each other
868  active_graph_inc_ns::SetArcsConnectNodes connectNodesWorklet;
869  this->Invoke(connectNodesWorklet,
870  tree.Arcs, // (input/output)
871  nodes, // (input)
872  tree.Superparents, // (input)
873  tree.Superarcs, // (input)
874  tree.Supernodes); // (input)
875 
876  tree.DebugPrint("Arcs Set", __FILE__, __LINE__);
877 } // SetArcs()
878 
879 
880 // Allocate the vertex array
882 {
883  this->GlobalIndex.Allocate(nElems);
884  this->Outdegree.Allocate(nElems);
885  this->Hyperarcs.Allocate(nElems);
886  this->ActiveVertices.Allocate(nElems);
887 }
888 
889 
890 // Allocate the edge array
892 {
893  this->ActiveEdges.Allocate(nElems);
894  this->EdgeNear.Allocate(nElems);
895  this->EdgeFar.Allocate(nElems);
896 }
897 
898 
899 // releases temporary arrays
901 {
903  this->FirstEdge.ReleaseResources();
904  this->Outdegree.ReleaseResources();
905  this->EdgeNear.ReleaseResources();
906  this->EdgeFar.ReleaseResources();
910  this->Hyperarcs.ReleaseResources();
911  this->HyperID.ReleaseResources();
912  this->SuperID.ReleaseResources();
913 }
914 
915 
916 // prints the contents of the active graph in a standard format
917 inline void ActiveGraph::DebugPrint(const char* message, const char* fileName, long lineNum)
918 { // DebugPrint()
919 #ifdef DEBUG_PRINT
920  std::cout << "------------------------------------------------------" << std::endl;
921  std::cout << std::setw(30) << std::left << fileName << ":" << std::right << std::setw(4)
922  << lineNum << std::endl;
923  std::cout << std::left << std::string(message) << std::endl;
924  std::cout << "Active Graph Contains: " << std::endl;
925  std::cout << "------------------------------------------------------" << std::endl;
926 
927  std::cout << "Is Join Graph? " << (this->IsJoinGraph ? "T" : "F") << std::endl;
928  std::cout << "NumIterations " << this->NumIterations << std::endl;
929  std::cout << "nSupernodes " << this->NumSupernodes << std::endl;
930  std::cout << "nHypernodes " << this->NumHypernodes << std::endl;
931 
932  // Full Vertex Arrays
933  std::cout << "Full Vertex Arrays - Size: " << this->GlobalIndex.GetNumberOfValues() << std::endl;
935  PrintIndices("Global Index", this->GlobalIndex);
936  PrintIndices("First Edge", this->FirstEdge);
937  PrintIndices("Outdegree", this->Outdegree);
938  PrintIndices("Hyperarc ID", this->Hyperarcs);
939  PrintIndices("Hypernode ID", this->HyperID);
940  PrintIndices("Supernode ID", this->SuperID);
941  std::cout << std::endl;
942 
943  // Active Vertex Arrays
944  IdArrayType activeIndices;
945  PermuteArray<vtkm::Id>(this->GlobalIndex, this->ActiveVertices, activeIndices);
946  IdArrayType activeFirst;
947  PermuteArray<vtkm::Id>(this->FirstEdge, this->ActiveVertices, activeFirst);
948  IdArrayType activeOutdegree;
949  PermuteArray<vtkm::Id>(this->Outdegree, this->ActiveVertices, activeOutdegree);
950  IdArrayType activeHyperarcs;
951  PermuteArray<vtkm::Id>(this->Hyperarcs, this->ActiveVertices, activeHyperarcs);
952  std::cout << "Active Vertex Arrays - Size: " << this->ActiveVertices.GetNumberOfValues()
953  << std::endl;
955  PrintIndices("Active Vertices", this->ActiveVertices);
956  PrintIndices("Active Indices", activeIndices);
957  PrintIndices("Active First Edge", activeFirst);
958  PrintIndices("Active Outdegree", activeOutdegree);
959  PrintIndices("Active Hyperarc ID", activeHyperarcs);
960  std::cout << std::endl;
961 
962  // Full Edge Arrays
963  IdArrayType farIndices;
964  PermuteArray<vtkm::Id>(this->GlobalIndex, this->EdgeFar, farIndices);
965  IdArrayType nearIndices;
966  PermuteArray<vtkm::Id>(this->GlobalIndex, this->EdgeNear, nearIndices);
967  std::cout << "Full Edge Arrays - Size: " << this->EdgeNear.GetNumberOfValues() << std::endl;
969  PrintIndices("Near", this->EdgeNear);
970  PrintIndices("Far", this->EdgeFar);
971  PrintIndices("Near Index", nearIndices);
972  PrintIndices("Far Index", farIndices);
973  std::cout << std::endl;
974 
975  // Active Edge Arrays
976  IdArrayType activeFarIndices;
977  PermuteArray<vtkm::Id>(this->EdgeFar, this->ActiveEdges, activeFarIndices);
978  IdArrayType activeNearIndices;
979  PermuteArray<vtkm::Id>(this->EdgeNear, this->ActiveEdges, activeNearIndices);
980  std::cout << "Active Edge Arrays - Size: " << this->ActiveEdges.GetNumberOfValues()
981  << std::endl;
983  PrintIndices("Active Edges", this->ActiveEdges);
984  PrintIndices("Edge Near Index", activeNearIndices);
985  PrintIndices("Edge Far Index", activeFarIndices);
986  std::cout << std::endl;
987 
988  // Edge Sorter Array
989  IdArrayType sortedFarIndices;
990  PermuteArray<vtkm::Id>(this->EdgeFar, this->EdgeSorter, sortedFarIndices);
991  IdArrayType sortedNearIndices;
992  PermuteArray<vtkm::Id>(this->EdgeNear, this->EdgeSorter, sortedNearIndices);
993  std::cout << "Edge Sorter - Size: " << this->EdgeSorter.GetNumberOfValues() << std::endl;
995  PrintIndices("Edge Sorter", this->EdgeSorter);
996  PrintIndices("Sorted Near Index", sortedNearIndices);
997  PrintIndices("Sorted Far Index", sortedFarIndices);
998  std::cout << std::endl;
999 
1000  std::cout << "---------------------------" << std::endl;
1001  std::cout << std::endl;
1002 #else
1003  // Prevent unused parameter warning
1004  (void)message;
1005  (void)fileName;
1006  (void)lineNum;
1007 #endif
1008 } // DebugPrint()
1009 
1010 
1011 
1012 } // namespace contourtree_augmented
1013 } // worklet
1014 } // vtkm
1015 
1016 #endif
vtkm::worklet::contourtree_augmented::ActiveGraph::FindGoverningSaddles
void FindGoverningSaddles()
Definition: ActiveGraph.h:490
vtkm::worklet::contourtree_augmented::ActiveGraph::IsJoinGraph
bool IsJoinGraph
Definition: ActiveGraph.h:129
vtkm::worklet::contourtree_augmented::OneIfHypernode
Definition: ArrayTransforms.h:144
InitializeNeighbourhoodMasksAndOutDegrees.h
InitializeEdgeFarFromActiveIndices.h
vtkm::worklet::contourtree_augmented::ActiveGraph::AllocateEdgeArrays
void AllocateEdgeArrays(vtkm::Id nElems)
Definition: ActiveGraph.h:891
vtkm::cont::ArrayHandle::GetNumberOfValues
VTKM_CONT vtkm::Id GetNumberOfValues() const
Returns the number of entries in the array.
Definition: ArrayHandle.h:448
vtkm::worklet::contourtree_augmented::ActiveGraph::EdgeSorter
IdArrayType EdgeSorter
Definition: ActiveGraph.h:159
vtkm::cont::ArrayHandle< T, S >
ArrayHandle.h
SetArcsConnectNodes.h
vtkm::worklet::contourtree_augmented::ActiveGraph::ReleaseTemporaryArrays
void ReleaseTemporaryArrays()
Definition: ActiveGraph.h:900
vtkm
Groups connected points that have the same field value.
Definition: Atomic.h:19
vtkm::worklet::contourtree_augmented::ActiveGraph::SuperID
IdArrayType SuperID
Definition: ActiveGraph.h:162
FindSuperAndHyperNodesWorklet.h
vtkm::worklet::contourtree_augmented::MergeTree::Arcs
IdArrayType Arcs
Definition: augmented/MergeTree.h:88
vtkm::worklet::contourtree_augmented::ActiveGraph::ActiveVertices
IdArrayType ActiveVertices
Definition: ActiveGraph.h:155
vtkm::worklet::contourtree_augmented::active_graph_inc::FindGoverningSaddlesWorklet
Definition: FindGoverningSaddlesWorklet.h:72
Types.h
vtkm::worklet::contourtree_augmented::ActiveGraph::Outdegree
IdArrayType Outdegree
Definition: ActiveGraph.h:146
EdgePeakComparator.h
vtkm::cont::ArrayHandle::Allocate
VTKM_CONT void Allocate(vtkm::Id numberOfValues, vtkm::CopyFlag preserve, vtkm::cont::Token &token) const
Allocates an array large enough to hold the given number of values.
Definition: ArrayHandle.h:465
vtkm::worklet::contourtree_augmented::ActiveGraph::CompactActiveVertices
void CompactActiveVertices()
Definition: ActiveGraph.h:527
InitializeActiveEdges.h
vtkm::worklet::contourtree_augmented::ActiveGraph::Hyperarcs
IdArrayType Hyperarcs
Definition: ActiveGraph.h:140
vtkm::worklet::contourtree_augmented::active_graph_inc::FindSuperAndHyperNodesWorklet
Definition: FindSuperAndHyperNodesWorklet.h:69
ArrayPortalToIterators.h
vtkm::worklet::contourtree_augmented::ActiveGraph::AllocateVertexArrays
void AllocateVertexArrays(vtkm::Id nElems)
Definition: ActiveGraph.h:881
ArrayHandleTransform.h
vtkm::worklet::contourtree_augmented::MeshExtrema::Pits
IdArrayType Pits
Definition: MeshExtrema.h:85
MergeTree.h
InitializeActiveGraphVertices.h
vtkm::cont::Algorithm::Sort
static VTKM_CONT void Sort(vtkm::cont::DeviceAdapterId devId, vtkm::cont::ArrayHandle< T, Storage > &values)
Definition: Algorithm.h:965
vtkm::worklet::contourtree_augmented::active_graph_inc::SetHyperArcsWorklet
Definition: SetHyperArcsWorklet.h:69
vtkm::cont::make_ArrayHandleConstant
vtkm::cont::ArrayHandleConstant< T > make_ArrayHandleConstant(T value, vtkm::Id numberOfValues)
make_ArrayHandleConstant is convenience function to generate an ArrayHandleImplicit.
Definition: ArrayHandleConstant.h:89
vtkm::worklet::contourtree_augmented::MeshExtrema
Definition: MeshExtrema.h:79
ArrayHandleConstant.h
vtkm::worklet::contourtree_augmented::ActiveGraph::SetSuperArcs
void SetSuperArcs(MergeTree &tree)
Definition: ActiveGraph.h:722
vtkm::worklet::contourtree_augmented::active_graph_inc::SetArcsConnectNodes
Definition: SetArcsConnectNodes.h:69
vtkm::cont::ArrayGetValue
VTKM_CONT T ArrayGetValue(vtkm::Id id, const vtkm::cont::ArrayHandle< T, S > &data)
Obtain a small set of values from an ArrayHandle with minimal device transfers.
Definition: ArrayGetValues.h:264
vtkm::worklet::contourtree_augmented::ActiveGraph::BuildTrunk
void BuildTrunk()
Definition: ActiveGraph.h:640
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveGraphVertices
Definition: InitializeActiveGraphVertices.h:70
vtkm::cont::Algorithm::Copy
static VTKM_CONT bool Copy(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, vtkm::cont::ArrayHandle< U, COut > &output)
Definition: Algorithm.h:410
PrintVectors.h
Invoker.h
SetArcsSetSuperAndHypernodeArcs.h
ArrayTransforms.h
vtkm::worklet::contourtree_augmented::ActiveGraph::HyperID
IdArrayType HyperID
Definition: ActiveGraph.h:163
vtkm::worklet::contourtree_augmented::MergeTree::Supernodes
IdArrayType Supernodes
Definition: augmented/MergeTree.h:98
vtkm::worklet::contourtree_augmented::ActiveGraph::GetLastValue
static T GetLastValue(const vtkm::cont::ArrayHandle< T, S > &ah)
Definition: ActiveGraph.h:120
vtkm::worklet::contourtree_augmented::ActiveGraph::DebugPrint
void DebugPrint(const char *message, const char *fileName, long lineNum)
Definition: ActiveGraph.h:917
SetHyperArcsWorklet.h
vtkm::worklet::contourtree_augmented::ActiveGraph::TransferRegularPoints
void TransferRegularPoints()
Definition: ActiveGraph.h:516
vtkm::Id
vtkm::Int32 Id
Represents an ID (index into arrays).
Definition: Types.h:191
vtkm::worklet::contourtree_augmented::active_graph_inc::SetSuperArcsSetTreeSuperarcs
Definition: SetSuperArcsSetTreeSuperarcs.h:69
vtkm::worklet::contourtree_augmented::active_graph_inc
Definition: BuildChainsWorklet.h:65
vtkm::worklet::contourtree_augmented::ActiveGraph::EdgeNear
IdArrayType EdgeNear
Definition: ActiveGraph.h:152
vtkm::worklet::contourtree_augmented::ActiveGraph::GlobalIndex
IdArrayType GlobalIndex
Definition: ActiveGraph.h:137
vtkm::worklet::contourtree_augmented::ActiveGraph::FindSuperAndHyperNodes
void FindSuperAndHyperNodes(MergeTree &tree)
Definition: ActiveGraph.h:651
vtkm::worklet::contourtree_augmented::MergeTree::IsJoinTree
bool IsJoinTree
Definition: augmented/MergeTree.h:81
TransferSaddleStartsResetEdgeFar.h
SuperArcNodeComparator.h
vtkm::cont::ErrorInternal
This class is thrown when VTKm detects an internal state that should never be reached.
Definition: ErrorInternal.h:26
vtkm::worklet::contourtree_augmented::active_graph_inc::TransferSaddleStartsSetNewOutdegreeForSaddles
Definition: TransferSaddleStartsSetNewOutdegreeForSaddles.h:72
vtkm::worklet::contourtree_augmented::ActiveGraph::ActiveGraph
ActiveGraph(bool IsJoinGraph)
Definition: ActiveGraph.h:231
vtkm::worklet::contourtree_augmented::active_graph_inc::SetSuperArcsSetTreeHyperparents
Definition: SetSuperArcsSetTreeHyperparents.h:69
vtkm::worklet::contourtree_augmented::active_graph_inc::TransferSaddleStartsResetEdgeFar
Definition: TransferSaddleStartsResetEdgeFar.h:71
vtkm::worklet::contourtree_augmented::MergeTree::Hyperarcs
IdArrayType Hyperarcs
Definition: augmented/MergeTree.h:115
vtkm::worklet::contourtree_augmented::active_graph_inc::SuperArcNodeComparator
Definition: SuperArcNodeComparator.h:119
ArrayHandlePermutation.h
Algorithm.h
ArrayHandleIndex.h
vtkm::worklet::contourtree_augmented::ActiveGraph::ActiveEdges
IdArrayType ActiveEdges
Definition: ActiveGraph.h:156
vtkm::worklet::contourtree_augmented::MergeTree::DebugPrint
void DebugPrint(const char *message, const char *fileName, long lineNum)
Definition: augmented/MergeTree.h:168
TransferSaddleStartsUpdateEdgeSorter.h
vtkm::worklet::contourtree_augmented::MergeTree::Hypernodes
IdArrayType Hypernodes
Definition: augmented/MergeTree.h:110
vtkm::cont::Algorithm::ScanExclusive
static VTKM_CONT T ScanExclusive(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, vtkm::cont::ArrayHandle< T, COut > &output)
Definition: Algorithm.h:816
vtkm::cont::ArrayHandlePermutation
Implicitly permutes the values in an array.
Definition: ArrayHandlePermutation.h:227
Error.h
vtkm::cont::Invoker
Allows launching any worklet without a dispatcher.
Definition: Invoker.h:41
InitializeHyperarcsFromActiveIndices.h
vtkm::cont::Algorithm::CopyIf
static VTKM_CONT void CopyIf(vtkm::cont::DeviceAdapterId devId, const vtkm::cont::ArrayHandle< T, CIn > &input, const vtkm::cont::ArrayHandle< U, CStencil > &stencil, vtkm::cont::ArrayHandle< T, COut > &output)
Definition: Algorithm.h:435
vtkm::worklet::contourtree_augmented::ActiveGraph::SetArcs
void SetArcs(MergeTree &tree, MeshExtrema &meshExtrema)
Definition: ActiveGraph.h:819
Types.h
vtkm::worklet::contourtree_augmented::active_graph_inc::HyperArcSuperNodeComparator
Definition: HyperArcSuperNodeComparator.h:119
FindGoverningSaddlesWorklet.h
vtkm::cont::ArrayHandleTransform
Implicitly transform values of one array to another with a functor.
Definition: ArrayHandleTransform.h:437
vtkm::worklet::contourtree_augmented::ActiveGraph::FirstEdge
IdArrayType FirstEdge
Definition: ActiveGraph.h:143
SetArcsSlideVertices.h
vtkm::worklet::contourtree_augmented::active_graph_inc::CompactActiveEdgesTransferActiveEdges
Definition: CompactActiveEdgesTransferActiveEdges.h:70
CompactActiveEdgesComputeNewVertexOutdegree.h
vtkm::cont::ArrayHandleConstant
An array handle with a constant value.
Definition: ArrayHandleConstant.h:63
vtkm::worklet::contourtree_augmented::ActiveGraph::SetHyperArcs
void SetHyperArcs(MergeTree &tree)
Definition: ActiveGraph.h:798
vtkm::CopyFlag::On
@ On
TransferRegularPointsWorklet.h
MeshExtrema.h
ArrayGetValues.h
vtkm::worklet::contourtree_augmented::MergeTree::Superarcs
IdArrayType Superarcs
Definition: augmented/MergeTree.h:102
vtkm::worklet::contourtree_augmented::OneIfSupernode
Definition: ArrayTransforms.h:134
vtkm::worklet::contourtree_augmented::active_graph_inc::TransferRegularPointsWorklet
Definition: TransferRegularPointsWorklet.h:72
vtkm::worklet::contourtree_augmented::ActiveGraph::CompactActiveEdges
void CompactActiveEdges()
Definition: ActiveGraph.h:550
vtkm::worklet::contourtree_augmented::active_graph_inc::TransferSaddleStartsUpdateEdgeSorter
Definition: TransferSaddleStartsUpdateEdgeSorter.h:71
BuildTrunkWorklet.h
vtkm::worklet::contourtree_augmented::MergeTree::Superparents
IdArrayType Superparents
Definition: augmented/MergeTree.h:91
vtkm::cont::make_ArrayHandlePermutation
VTKM_CONT vtkm::cont::ArrayHandlePermutation< IndexArrayHandleType, ValueArrayHandleType > make_ArrayHandlePermutation(IndexArrayHandleType indexArray, ValueArrayHandleType valueArray)
make_ArrayHandleTransform is convenience function to generate an ArrayHandleTransform.
Definition: ArrayHandlePermutation.h:279
vtkm::worklet::contourtree_augmented::MergeTree
Definition: augmented/MergeTree.h:77
HyperArcSuperNodeComparator.h
vtkm::worklet::contourtree_augmented::ActiveGraph::Invoke
vtkm::cont::Invoker Invoke
Definition: ActiveGraph.h:126
vtkm::worklet::contourtree_augmented::active_graph_inc::CompactActiveEdgesComputeNewVertexOutdegree
Definition: CompactActiveEdgesComputeNewVertexOutdegree.h:71
vtkm::worklet::contourtree_augmented::ActiveGraph::TransferSaddleStarts
void TransferSaddleStarts()
Definition: ActiveGraph.h:435
vtkm::worklet::contourtree_augmented::active_graph_inc::BuildChainsWorklet
Definition: BuildChainsWorklet.h:69
BuildChainsWorklet.h
vtkm::worklet::contourtree_augmented::ActiveGraph::EdgeFar
IdArrayType EdgeFar
Definition: ActiveGraph.h:151
vtkm::worklet::contourtree_augmented::PrintIndices
void PrintIndices(std::string label, const vtkm::cont::ArrayHandle< T > &iVec, vtkm::Id nIndices=-1, std::ostream &outStream=std::cout)
Definition: augmented/PrintVectors.h:253
vtkm::worklet::contourtree_augmented::PrintHeader
void PrintHeader(vtkm::Id howMany, std::ostream &outStream=std::cout)
Definition: augmented/PrintVectors.h:151
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeActiveEdges
Definition: InitializeActiveEdges.h:72
SetSuperArcsSetTreeHyperparents.h
vtkm::worklet::contourtree_augmented::ActiveGraph::Initialise
void Initialise(Mesh &mesh, const MeshExtrema &meshExtrema)
Definition: ActiveGraph.h:244
vtkm::worklet::contourtree_augmented::ActiveGraph::NumSupernodes
vtkm::Id NumSupernodes
Definition: ActiveGraph.h:166
vtkm::worklet::contourtree_augmented::ActiveGraph::NumIterations
vtkm::Id NumIterations
Definition: ActiveGraph.h:132
vtkm::worklet::contourtree_augmented::ActiveGraph::NumHypernodes
vtkm::Id NumHypernodes
Definition: ActiveGraph.h:167
vtkm::worklet::contourtree_augmented::ActiveGraph
Definition: ActiveGraph.h:116
vtkm::worklet::contourtree_augmented::ActiveGraph::MakeMergeTree
void MakeMergeTree(MergeTree &tree, MeshExtrema &meshExtrema)
Definition: ActiveGraph.h:376
vtkm::worklet::contourtree_augmented::active_graph_inc::BuildTrunkWorklet
Definition: BuildTrunkWorklet.h:70
vtkm::worklet::contourtree_augmented::MergeTree::Hyperparents
IdArrayType Hyperparents
Definition: augmented/MergeTree.h:105
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeNeighbourhoodMasksAndOutDegrees
Definition: InitializeNeighbourhoodMasksAndOutDegrees.h:69
vtkm::worklet::contourtree_augmented::ActiveGraph::BuildChains
void BuildChains()
Definition: ActiveGraph.h:621
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeEdgeFarFromActiveIndices
Definition: InitializeEdgeFarFromActiveIndices.h:72
vtkm::worklet::contourtree_augmented::MergeTree::FirstSuperchild
IdArrayType FirstSuperchild
Definition: augmented/MergeTree.h:118
vtkm::worklet::contourtree_augmented::OneIfCritical
Definition: ArrayTransforms.h:124
SetSuperArcsSetTreeSuperarcs.h
vtkm::cont::ArrayHandle::ReleaseResources
VTKM_CONT void ReleaseResources() const
Releases all resources in both the control and execution environments.
Definition: ArrayHandle.h:559
vtkm::worklet::contourtree_augmented::NO_SUCH_ELEMENT
constexpr vtkm::Id NO_SUCH_ELEMENT
Definition: filter/scalar_topology/worklet/contourtree_augmented/Types.h:73
vtkm::worklet::contourtree_augmented::MeshExtrema::Peaks
IdArrayType Peaks
Definition: MeshExtrema.h:84
TransferSaddleStartsSetNewOutdegreeForSaddles.h
CompactActiveEdgesTransferActiveEdges.h
vtkm::worklet::contourtree_augmented::active_graph_inc::EdgePeakComparator
Definition: augmented/activegraph/EdgePeakComparator.h:141
vtkm::worklet::contourtree_augmented::active_graph_inc::SetArcsSlideVertices
Definition: SetArcsSlideVertices.h:69
vtkm::worklet::contourtree_augmented::active_graph_inc::SetArcsSetSuperAndHypernodeArcs
Definition: SetArcsSetSuperAndHypernodeArcs.h:69
vtkm::worklet::contourtree_augmented::active_graph_inc::InitializeHyperarcsFromActiveIndices
Definition: InitializeHyperarcsFromActiveIndices.h:71
vtkm::cont::ArrayHandleIndex
An implicit array handle containing the its own indices.
Definition: ArrayHandleIndex.h:54