# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Loading...
Searching...
No Matches
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

~DTree ()
destructor

void adjustPointInfo (int curr)
used to update the first and numPoints of inner nodes by linkNodes

void build ()
Does all required steps except the allocate, deallocate, randomPoints.

int child (int i, int j) const
returns the index of the j th child of node i

int countPoints () const
Just for fun: traverse the tree and count the points in the leaves.

int countPoints (int curr) const
Just for fun: traverse the tree and count the points in the leaves.

void linkNodes ()
The Recursive Bottom-Up Construction (recursion start)

int linkNodes (int curr, int maxLevel)
The Recursive Bottom-Up Construction.

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

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

Nodenode (int i)
Just to access the nodes a little bit easier.

const Nodenode (int i) const
Just to access the nodes a little bit easier.

int numChilds (int i) const
returns the number of children of node i

int numPoints () const
returns the number of points the quadtree contains

int numPoints (int i) const
returns the number of points covered by this subtree

const Pointpoint (int i) const
returns the ith point in the input sequence

int point (int i, int j) const
returns the index of the jth point covered by i's subtree.

void prepareMortonOrder ()
Prepares the morton numbers for sorting.

void prepareNodeLayer ()
Prepares both the leaf and inner node layer.

int rootIndex () const
returns the index of the root node

void setPoint (int i, int d, IntType value)
sets the point to the given grid coords

void sortMortonNumbers ()
Sorts the points by morton number.

## Static Public Attributes

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

## Private Member Functions

void allocate (int n)
Allocates memory for n points.

void deallocate ()
Releases memory.

## Private Attributes

int m_maxLevel

MortonEntrym_mortonOrder = nullptr
The order to be sorted.

Nodem_nodes = nullptr
Memory for all nodes.

int m_numPoints
Total number of points.

Pointm_points = nullptr
The input set.

int m_rootIndex
The index of the root node.

## 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 41 of file DTree.h.

## ◆ DTree()

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

constructor

Definition at line 47 of file DTree.h.

## ◆ ~DTree()

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

destructor

Definition at line 53 of file DTree.h.

## ◆ 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 281 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 167 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 349 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 97 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 145 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 334 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 176 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 328 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 295 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 112 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 268 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 91 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 88 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 94 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 109 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 100 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 115 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 103 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 190 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 210 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 148 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 183 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 203 of file DTree.h.

## ◆ m_maxLevel

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

Definition at line 157 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 160 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 161 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 159 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 158 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 162 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 44 of file DTree.h.

The documentation for this class was generated from the following file:
• include/ogdf/energybased/dtree/DTree.h