Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::energybased::dtree::DTree< IntType, Dim > Class Template Reference

Implentation of the reduced quadtree for Dim dimensions. More...

#include <ogdf/energybased/dtree/DTree.h>

Classes

struct  MortonEntry
 The entry in the sorted order for a point. More...
 
struct  Node
 The node class. More...
 
struct  Point
 The point class with integer coords. More...
 

Public Member Functions

 DTree (int numPoints)
 constructor More...
 
 ~DTree ()
 destructor More...
 
void adjustPointInfo (int curr)
 used to update the first and numPoints of inner nodes by linkNodes More...
 
void build ()
 Does all required steps except the allocate, deallocate, randomPoints. More...
 
int child (int i, int j) const
 returns the index of the j th child of node i More...
 
int countPoints () const
 Just for fun: traverse the tree and count the points in the leaves. More...
 
int countPoints (int curr) const
 Just for fun: traverse the tree and count the points in the leaves. More...
 
void linkNodes ()
 The Recursive Bottom-Up Construction (recursion start) More...
 
int linkNodes (int curr, int maxLevel)
 The Recursive Bottom-Up Construction. More...
 
int maxNumNodes () const
 returns the maximum number of nodes (and the max index of a node) More...
 
void mergeWithNext (int curr)
 Merges curr with next node in the chain (used by linkNodes) More...
 
Nodenode (int i)
 Just to access the nodes a little bit easier. More...
 
const Nodenode (int i) const
 Just to access the nodes a little bit easier. More...
 
int numChilds (int i) const
 returns the number of children of node i More...
 
int numPoints () const
 returns the number of points the quadtree contains More...
 
int numPoints (int i) const
 returns the number of points covered by this subtree More...
 
const Pointpoint (int i) const
 returns the ith point in the input sequence More...
 
int point (int i, int j) const
 returns the index of the jth point covered by i's subtree. More...
 
void prepareMortonOrder ()
 Prepares the morton numbers for sorting. More...
 
void prepareNodeLayer ()
 Prepares both the leaf and inner node layer. More...
 
int rootIndex () const
 returns the index of the root node More...
 
void setPoint (int i, int d, IntType value)
 sets the point to the given grid coords More...
 
void sortMortonNumbers ()
 Sorts the points by morton number. More...
 

Static Public Attributes

static constexpr int MaxNumChildrenPerNode = (1 << Dim)
 the maximum number of children per node = 2^d More...
 

Private Member Functions

void allocate (int n)
 Allocates memory for n points. More...
 
void deallocate ()
 Releases memory. More...
 

Private Attributes

int m_maxLevel
 
MortonEntrym_mortonOrder = nullptr
 The order to be sorted. More...
 
Nodem_nodes = nullptr
 Memory for all nodes. More...
 
int m_numPoints
 Total number of points. More...
 
Pointm_points = nullptr
 The input set. More...
 
int m_rootIndex
 The index of the root node. More...
 

Detailed Description

template<typename IntType, int Dim>
class ogdf::energybased::dtree::DTree< IntType, Dim >

Implentation of the reduced quadtree for Dim dimensions.

Definition at line 40 of file DTree.h.

Constructor & Destructor Documentation

◆ DTree()

template<typename IntType , int Dim>
ogdf::energybased::dtree::DTree< IntType, Dim >::DTree ( int  numPoints)
inlineexplicit

constructor

Definition at line 48 of file DTree.h.

◆ ~DTree()

template<typename IntType , int Dim>
ogdf::energybased::dtree::DTree< IntType, Dim >::~DTree ( )
inline

destructor

Definition at line 57 of file DTree.h.

Member Function Documentation

◆ adjustPointInfo()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::adjustPointInfo ( int  curr)
inline

used to update the first and numPoints of inner nodes by linkNodes

Definition at line 301 of file DTree.h.

◆ allocate()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::allocate ( int  n)
private

Allocates memory for n points.

allocates memory for n points

Definition at line 180 of file DTree.h.

◆ build()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::build

Does all required steps except the allocate, deallocate, randomPoints.

link the inner nodes using the recursive bottom-up method

Definition at line 373 of file DTree.h.

◆ child()

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::child ( int  i,
int  j 
) const
inline

returns the index of the j th child of node i

Definition at line 109 of file DTree.h.

◆ countPoints() [1/2]

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::countPoints ( ) const
inline

Just for fun: traverse the tree and count the points in the leaves.

Definition at line 157 of file DTree.h.

◆ countPoints() [2/2]

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::countPoints ( int  curr) const

Just for fun: traverse the tree and count the points in the leaves.

Definition at line 357 of file DTree.h.

◆ deallocate()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::deallocate
private

Releases memory.

releases memory

Definition at line 191 of file DTree.h.

◆ linkNodes() [1/2]

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::linkNodes

The Recursive Bottom-Up Construction (recursion start)

Definition at line 350 of file DTree.h.

◆ linkNodes() [2/2]

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::linkNodes ( int  curr,
int  maxLevel 
)

The Recursive Bottom-Up Construction.

Definition at line 315 of file DTree.h.

◆ maxNumNodes()

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::maxNumNodes ( ) const
inline

returns the maximum number of nodes (and the max index of a node)

Definition at line 124 of file DTree.h.

◆ mergeWithNext()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::mergeWithNext ( int  curr)
inline

Merges curr with next node in the chain (used by linkNodes)

Definition at line 287 of file DTree.h.

◆ node() [1/2]

template<typename IntType , int Dim>
Node& ogdf::energybased::dtree::DTree< IntType, Dim >::node ( int  i)
inline

Just to access the nodes a little bit easier.

Definition at line 103 of file DTree.h.

◆ node() [2/2]

template<typename IntType , int Dim>
const Node& ogdf::energybased::dtree::DTree< IntType, Dim >::node ( int  i) const
inline

Just to access the nodes a little bit easier.

Definition at line 100 of file DTree.h.

◆ numChilds()

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::numChilds ( int  i) const
inline

returns the number of children of node i

Definition at line 106 of file DTree.h.

◆ numPoints() [1/2]

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::numPoints ( ) const
inline

returns the number of points the quadtree contains

Definition at line 121 of file DTree.h.

◆ numPoints() [2/2]

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::numPoints ( int  i) const
inline

returns the number of points covered by this subtree

Definition at line 112 of file DTree.h.

◆ point() [1/2]

template<typename IntType , int Dim>
const Point& ogdf::energybased::dtree::DTree< IntType, Dim >::point ( int  i) const
inline

returns the ith point in the input sequence

Definition at line 127 of file DTree.h.

◆ point() [2/2]

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::point ( int  i,
int  j 
) const
inline

returns the index of the jth point covered by i's subtree.

Definition at line 115 of file DTree.h.

◆ prepareMortonOrder()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::prepareMortonOrder

Prepares the morton numbers for sorting.

Definition at line 207 of file DTree.h.

◆ prepareNodeLayer()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::prepareNodeLayer

Prepares both the leaf and inner node layer.

Definition at line 230 of file DTree.h.

◆ rootIndex()

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::rootIndex ( ) const
inline

returns the index of the root node

Definition at line 160 of file DTree.h.

◆ setPoint()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::setPoint ( int  i,
int  d,
IntType  value 
)

sets the point to the given grid coords

Definition at line 199 of file DTree.h.

◆ sortMortonNumbers()

template<typename IntType , int Dim>
void ogdf::energybased::dtree::DTree< IntType, Dim >::sortMortonNumbers

Sorts the points by morton number.

Definition at line 221 of file DTree.h.

Member Data Documentation

◆ m_maxLevel

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::m_maxLevel
private

Definition at line 170 of file DTree.h.

◆ m_mortonOrder

template<typename IntType , int Dim>
MortonEntry* ogdf::energybased::dtree::DTree< IntType, Dim >::m_mortonOrder = nullptr
private

The order to be sorted.

Definition at line 173 of file DTree.h.

◆ m_nodes

template<typename IntType , int Dim>
Node* ogdf::energybased::dtree::DTree< IntType, Dim >::m_nodes = nullptr
private

Memory for all nodes.

Definition at line 174 of file DTree.h.

◆ m_numPoints

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::m_numPoints
private

Total number of points.

Definition at line 172 of file DTree.h.

◆ m_points

template<typename IntType , int Dim>
Point* ogdf::energybased::dtree::DTree< IntType, Dim >::m_points = nullptr
private

The input set.

Definition at line 171 of file DTree.h.

◆ m_rootIndex

template<typename IntType , int Dim>
int ogdf::energybased::dtree::DTree< IntType, Dim >::m_rootIndex
private

The index of the root node.

Definition at line 175 of file DTree.h.

◆ MaxNumChildrenPerNode

template<typename IntType , int Dim>
constexpr int ogdf::energybased::dtree::DTree< IntType, Dim >::MaxNumChildrenPerNode = (1 << Dim)
staticconstexpr

the maximum number of children per node = 2^d

Definition at line 45 of file DTree.h.


The documentation for this class was generated from the following file: