#include <ogdf/energybased/fast_multipole_embedder/LinearQuadtree.h>

Classes
struct	bottom_up_traversal_functor
	bottom up traversal of the subtree of a given node More...

struct	forall_children_functor
	simple functor for iterating over all children of a node More...

struct	forall_ordered_pairs_of_children_functor
	functor for iterating over all ordered pairs of children of a node More...

struct	forall_points_functor
	simple functor for iterating over all points of a node More...

struct	forall_tree_nodes_functor
	simple functor for iterating over all nodes More...

struct	is_fence_condition_functor

struct	is_leaf_condition_functor

struct	LQNode

struct	LQPoint

struct	LQWSPair

struct	StoreDirectNodeFunctor

struct	StoreDirectPairFunctor

struct	StoreWSPairFunctor

struct	top_down_traversal_functor
	top down traversal of the subtree of a given node More...

struct	wspd_functor

Public Types
using	NodeID = unsigned int

using	PointID = unsigned int

Public Member Functions
	LinearQuadtree (uint32_t n, float origXPos, float origYPos, float *origSize)
	constructor. required tree mem will be allocated

	~LinearQuadtree (void)
	destructor. tree mem will be released

template<typename F >
bottom_up_traversal_functor< F >	bottom_up_traversal (F f) const
	creator

template<typename F , typename Cond >
bottom_up_traversal_functor< F, Cond >	bottom_up_traversal (F f, Cond cond) const
	creator

NodeID	child (NodeID nodeID, uint32_t i) const
	returns the `i` th child index of node `nodeID`

void	clear ()
	resets the tree

void	computeCoords (NodeID nodeIndex)

void	computeWSPD ()

void	computeWSPD (NodeID n)

NodeID	directNode (uint32_t i) const

NodeID	directNodeA (uint32_t i) const

NodeID	directNodeB (uint32_t i) const

PointID	findFirstPointInCell (PointID somePointInCell) const

NodeID	firstInnerNode () const

NodeID	firstLeaf () const

PointID	firstPoint (NodeID nodeID) const

template<typename F >
forall_children_functor< F >	forall_children (F f) const
	creator

template<typename F >
forall_ordered_pairs_of_children_functor< F >	forall_ordered_pairs_of_children (F f) const
	creator

template<typename Func >
forall_points_functor< Func >	forall_points (const Func &func) const
	creator

template<typename F >
forall_tree_nodes_functor< F >	forall_tree_nodes (F f, NodeID begin, uint32_t num) const
	creator

template<typename A , typename B , typename C >
wspd_functor< A, B, C >	forall_well_separated_pairs (A a, B b, C c)

template<typename A , typename B , typename C , typename ConditionType >
wspd_functor< A, B, C, ConditionType >	forall_well_separated_pairs (A a, B b, C c, ConditionType cond)

void	init (float min_x, float min_y, float max_x, float max_y)

is_fence_condition_functor	is_fence_condition () const
	creator

is_leaf_condition_functor	is_leaf_condition () const
	creator

bool	isFence (NodeID nodeID) const
	sets the fence flag for node `nodeID`

bool	isLeaf (NodeID nodeID) const
	returns true if the given node index is a leaf

bool	isWS (NodeID a, NodeID b) const

NodeID	level (NodeID nodeID) const

uint32_t	maxNumberOfNodes () const
	the upper bound for a compressed quadtree (2*numPoints)

float	maxX () const

float	maxY () const

float	minX () const

float	minY () const

MortonNR	mortonNr (PointID point) const

NodeID	nextNode (NodeID nodeID) const

void	nodeFence (NodeID nodeID)

NodeID	nodeOfPoint (PointID id) const

float	nodeSize (NodeID nodeID) const

float	nodeX (NodeID nodeID) const

float	nodeY (NodeID nodeID) const

uint32_t	numberOfChilds (NodeID nodeID) const
	returns the number of children of node `nodeID`. for an inner node this is 1..4 and can be accessed by child(i). For a leaf the number of points in this leaf is returned starting with point child(0)

uint32_t	numberOfDirectNodes () const

uint32_t	numberOfDirectPairs () const

uint32_t	numberOfInnerNodes () const

uint32_t	numberOfLeaves () const

uint32_t	numberOfNodes () const
	returns the number of nodes in this tree

uint32_t	numberOfPoints () const
	returns the number of points in this tree

uint32_t	numberOfPoints (NodeID nodeID) const
	returns the number of points contained in the subtree of node `nodeID`

uint32_t	numberOfWSP () const

LQPoint &	point (PointID pointID)

const LQPoint &	point (PointID pointID) const

LQPoint *	pointArray ()

NodeID	pointLeaf (PointID point) const

float *	pointSize () const

float	pointSize (PointID point) const

float *	pointX () const

float	pointX (PointID point) const

float *	pointY () const

float	pointY (PointID point) const

uint32_t	refOfPoint (PointID id) const

NodeID	root () const
	returns the index of the root

double	scaleInv () const

void	setChild (NodeID nodeID, uint32_t i, NodeID c)
	sets the `i` th child index of node `nodeID`

void	setFirstPoint (NodeID nodeID, PointID firstPoint)

void	setLevel (NodeID nodeID, uint32_t level)

void	setNextNode (NodeID nodeID, NodeID next)

void	setNodeSize (NodeID nodeID, float size)

void	setNodeX (NodeID nodeID, float x)

void	setNodeY (NodeID nodeID, float y)

void	setNumberOfChilds (NodeID nodeID, uint32_t numChilds)
	sets the number of children of a node

void	setNumberOfPoints (NodeID nodeID, uint32_t numPoints)
	sets the number of nodes containted in node `nodeID`

void	setPoint (PointID id, float x, float y, float r)

void	setPoint (PointID id, float x, float y, float r, uint32_t ref)

void	setPoint (PointID id, float x, float y, uint32_t ref)

void	setPointLeaf (PointID point, NodeID leaf)

uint64_t	sizeInBytes () const

StoreDirectNodeFunctor	StoreDirectNodeFunction ()

StoreDirectPairFunctor	StoreDirectPairFunction ()

StoreWSPairFunctor	StoreWSPairFunction ()

template<typename F >
top_down_traversal_functor< F >	top_down_traversal (F f) const
	creator

template<typename F , typename Cond >
top_down_traversal_functor< F, Cond >	top_down_traversal (F f, Cond cond) const
	creator

void	updatePointPositionSize (PointID id)

WSPD *	wspd () const

Private Member Functions
void	addDirect (NodeID s)
	add a direct node to the array list of direct nodes

void	addDirectPair (NodeID s, NodeID t)
	add a direct pair to the array list of direct pairs

void	addWSPD (NodeID s, NodeID t)
	adds a well-separated pair to the wspd

void	allocate (uint32_t n)
	helper function for allocating the array's

void	deallocate ()
	helper function for releasing memory

void	initInnerNode (NodeID nodeID, NodeID leftChild, NodeID rightChild, uint32_t level, NodeID next)

void	initLeaf (NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next)

void	leafAppendPoint (NodeID leaf, PointID point)
	appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf

void	nodeAppendChild (NodeID nodeID, NodeID child)
	appends one child index. Assumes childCount < 4 and not leaf

Private Attributes
double	m_cellSize
	the height and width of a grid cell

NodeID *	m_directNodes

NodeID	m_firstInner
	first inner node in the inner node chain

NodeID	m_firstLeaf
	first leaf in the leaf chain

float	m_max_x
	the x coordinate of the right most point

float	m_max_y
	the y coordinate of the top most point

uint32_t	m_maxNumNodes
	the maximum number of nodes (2n here instead of 2n-1)

float	m_min_x
	the x coordinate of the left most point

float	m_min_y
	the y coordinate of the bottom most point

float *	m_nodeSize
	node size

float *	m_nodeXPos
	node x coord

float *	m_nodeYPos
	node y coord

LQWSPair *	m_notWspd

uint32_t	m_numDirectNodes

uint32_t	m_numInnerNodes
	number of inner nodes in the chain

uint32_t	m_numLeaves
	number of leaves in the chain

uint32_t	m_numNotWSP

uint32_t	m_numPoints
	number of points this quadtree is based on

uint32_t	m_numWSP

float *	m_origSize
	point size in graph order

float *	m_origXPos
	point x coord in graph order

float *	m_origYPos
	point y coord in graph order

LQPoint *	m_points
	the point order in tree order

float *	m_pointSize
	point size in tree order

float *	m_pointXPos
	point x coord in tree order

float *	m_pointYPos
	point y coord in tree order

NodeID	m_root
	the root of the tree

double	m_scaleInv
	the inverse scale to transform

double	m_sideLengthGrid
	the resulting side length of the grid (constant)

double	m_sideLengthPoints
	the maximum of height and width

LQNode *	m_tree
	the main tree array containing all nodes (including leaves)

WSPD *	m_WSPD
	the wspd of this quadtree

Friends
class	LinearQuadtreeBuilder

class	LinearQuadtreeBuilderList

Detailed Description

Definition at line 47 of file LinearQuadtree.h.

Member Typedef Documentation

◆ NodeID

using ogdf::fast_multipole_embedder::LinearQuadtree::NodeID = unsigned int

Definition at line 52 of file LinearQuadtree.h.

◆ PointID

using ogdf::fast_multipole_embedder::LinearQuadtree::PointID = unsigned int

Definition at line 53 of file LinearQuadtree.h.

Constructor & Destructor Documentation

◆ LinearQuadtree()

ogdf::fast_multipole_embedder::LinearQuadtree::LinearQuadtree	(	uint32_t	n,
		float *	origXPos,
		float *	origYPos,
		float *	origSize
	)

constructor. required tree mem will be allocated

◆ ~LinearQuadtree()

ogdf::fast_multipole_embedder::LinearQuadtree::~LinearQuadtree ( void )

destructor. tree mem will be released

Member Function Documentation

◆ addDirect()

void ogdf::fast_multipole_embedder::LinearQuadtree::addDirect ( NodeID s )

private

add a direct node to the array list of direct nodes

◆ addDirectPair()

void ogdf::fast_multipole_embedder::LinearQuadtree::addDirectPair	(	NodeID	s,
		NodeID	t
	)

private

add a direct pair to the array list of direct pairs

◆ addWSPD()

void ogdf::fast_multipole_embedder::LinearQuadtree::addWSPD	(	NodeID	s,
		NodeID	t
	)

private

adds a well-separated pair to the wspd

◆ allocate()

void ogdf::fast_multipole_embedder::LinearQuadtree::allocate ( uint32_t n )

private

helper function for allocating the array's

◆ bottom_up_traversal() [1/2]

template<typename F >

bottom_up_traversal_functor< F > ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal ( F f ) const

inline

creator

Definition at line 259 of file LinearQuadtree.h.

◆ bottom_up_traversal() [2/2]

template<typename F , typename Cond >

bottom_up_traversal_functor< F, Cond > ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal	(	F	f,
		Cond	cond
	)		const

inline

creator

Definition at line 265 of file LinearQuadtree.h.

◆ child()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::child	(	NodeID	nodeID,
		uint32_t	i
	)		const

inline

returns the i th child index of node nodeID

Definition at line 403 of file LinearQuadtree.h.

◆ clear()

void ogdf::fast_multipole_embedder::LinearQuadtree::clear ( )

resets the tree

◆ computeCoords()

void ogdf::fast_multipole_embedder::LinearQuadtree::computeCoords ( NodeID nodeIndex )

inline

Definition at line 552 of file LinearQuadtree.h.

◆ computeWSPD() [1/2]

void ogdf::fast_multipole_embedder::LinearQuadtree::computeWSPD ( )

◆ computeWSPD() [2/2]

void ogdf::fast_multipole_embedder::LinearQuadtree::computeWSPD ( NodeID n )

◆ deallocate()

void ogdf::fast_multipole_embedder::LinearQuadtree::deallocate ( )

private

helper function for releasing memory

◆ directNode()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::directNode ( uint32_t i ) const

inline

Definition at line 532 of file LinearQuadtree.h.

◆ directNodeA()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::directNodeA ( uint32_t i ) const

inline

Definition at line 534 of file LinearQuadtree.h.

◆ directNodeB()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::directNodeB ( uint32_t i ) const

inline

Definition at line 536 of file LinearQuadtree.h.

◆ findFirstPointInCell()

PointID ogdf::fast_multipole_embedder::LinearQuadtree::findFirstPointInCell ( PointID somePointInCell ) const

◆ firstInnerNode()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::firstInnerNode ( ) const

inline

Definition at line 518 of file LinearQuadtree.h.

◆ firstLeaf()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::firstLeaf ( ) const

inline

Definition at line 522 of file LinearQuadtree.h.

◆ firstPoint()

PointID ogdf::fast_multipole_embedder::LinearQuadtree::firstPoint ( NodeID nodeID ) const

inline

Definition at line 380 of file LinearQuadtree.h.

◆ forall_children()

template<typename F >

forall_children_functor< F > ogdf::fast_multipole_embedder::LinearQuadtree::forall_children ( F f ) const

inline

creator

Definition at line 151 of file LinearQuadtree.h.

◆ forall_ordered_pairs_of_children()

template<typename F >

forall_ordered_pairs_of_children_functor< F > ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children ( F f ) const

inline

creator

Definition at line 201 of file LinearQuadtree.h.

◆ forall_points()

template<typename Func >

forall_points_functor< Func > ogdf::fast_multipole_embedder::LinearQuadtree::forall_points ( const Func & func ) const

inline

creator

Definition at line 174 of file LinearQuadtree.h.

◆ forall_tree_nodes()

template<typename F >

forall_tree_nodes_functor< F > ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes	(	F	f,
		NodeID	begin,
		uint32_t	num
	)		const

inline

creator

Definition at line 127 of file LinearQuadtree.h.

◆ forall_well_separated_pairs() [1/2]

template<typename A , typename B , typename C >

wspd_functor< A, B, C > ogdf::fast_multipole_embedder::LinearQuadtree::forall_well_separated_pairs	(	A	a,
		B	b,
		C	c
	)

inline

Definition at line 334 of file LinearQuadtree.h.

◆ forall_well_separated_pairs() [2/2]

template<typename A , typename B , typename C , typename ConditionType >

wspd_functor< A, B, C, ConditionType > ogdf::fast_multipole_embedder::LinearQuadtree::forall_well_separated_pairs	(	A	a,
		B	b,
		C	c,
		ConditionType	cond
	)

inline

Definition at line 328 of file LinearQuadtree.h.

◆ init()

void ogdf::fast_multipole_embedder::LinearQuadtree::init	(	float	min_x,
		float	min_y,
		float	max_x,
		float	max_y
	)

◆ initInnerNode()

void ogdf::fast_multipole_embedder::LinearQuadtree::initInnerNode	(	NodeID	nodeID,
		NodeID	leftChild,
		NodeID	rightChild,
		uint32_t	level,
		NodeID	next
	)

inlineprivate

Definition at line 589 of file LinearQuadtree.h.

◆ initLeaf()

void ogdf::fast_multipole_embedder::LinearQuadtree::initLeaf	(	NodeID	leaf,
		PointID	firstPoint,
		uint32_t	numPoints,
		NodeID	next
	)

inlineprivate

Definition at line 580 of file LinearQuadtree.h.

◆ is_fence_condition()

is_fence_condition_functor ogdf::fast_multipole_embedder::LinearQuadtree::is_fence_condition ( ) const

inline

creator

Definition at line 88 of file LinearQuadtree.h.

◆ is_leaf_condition()

is_leaf_condition_functor ogdf::fast_multipole_embedder::LinearQuadtree::is_leaf_condition ( ) const

inline

creator

Definition at line 101 of file LinearQuadtree.h.

◆ isFence()

bool ogdf::fast_multipole_embedder::LinearQuadtree::isFence ( NodeID nodeID ) const

inline

sets the fence flag for node nodeID

Definition at line 412 of file LinearQuadtree.h.

◆ isLeaf()

bool ogdf::fast_multipole_embedder::LinearQuadtree::isLeaf ( NodeID nodeID ) const

inline

returns true if the given node index is a leaf

Definition at line 409 of file LinearQuadtree.h.

◆ isWS()

bool ogdf::fast_multipole_embedder::LinearQuadtree::isWS	(	NodeID	a,
		NodeID	b
	)		const

inline

Definition at line 505 of file LinearQuadtree.h.

◆ leafAppendPoint()

void ogdf::fast_multipole_embedder::LinearQuadtree::leafAppendPoint	(	NodeID	leaf,
		PointID	point
	)

inlineprivate

appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf

Definition at line 608 of file LinearQuadtree.h.

◆ level()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::level ( NodeID nodeID ) const

inline

Definition at line 372 of file LinearQuadtree.h.

◆ maxNumberOfNodes()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::maxNumberOfNodes ( ) const

inline

the upper bound for a compressed quadtree (2*numPoints)

Definition at line 432 of file LinearQuadtree.h.

◆ maxX()

float ogdf::fast_multipole_embedder::LinearQuadtree::maxX ( ) const

inline

Definition at line 546 of file LinearQuadtree.h.

◆ maxY()

float ogdf::fast_multipole_embedder::LinearQuadtree::maxY ( ) const

inline

Definition at line 548 of file LinearQuadtree.h.

◆ minX()

float ogdf::fast_multipole_embedder::LinearQuadtree::minX ( ) const

inline

Definition at line 542 of file LinearQuadtree.h.

◆ minY()

float ogdf::fast_multipole_embedder::LinearQuadtree::minY ( ) const

inline

Definition at line 544 of file LinearQuadtree.h.

◆ mortonNr()

MortonNR ogdf::fast_multipole_embedder::LinearQuadtree::mortonNr ( PointID point ) const

inline

Definition at line 390 of file LinearQuadtree.h.

◆ nextNode()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::nextNode ( NodeID nodeID ) const

inline

Definition at line 374 of file LinearQuadtree.h.

◆ nodeAppendChild()

void ogdf::fast_multipole_embedder::LinearQuadtree::nodeAppendChild	(	NodeID	nodeID,
		NodeID	child
	)

inlineprivate

appends one child index. Assumes childCount < 4 and not leaf

Definition at line 602 of file LinearQuadtree.h.

◆ nodeFence()

void ogdf::fast_multipole_embedder::LinearQuadtree::nodeFence ( NodeID nodeID )

inline

Definition at line 503 of file LinearQuadtree.h.

◆ nodeOfPoint()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::nodeOfPoint ( PointID id ) const

inline

Definition at line 501 of file LinearQuadtree.h.

◆ nodeSize()

float ogdf::fast_multipole_embedder::LinearQuadtree::nodeSize ( NodeID nodeID ) const

inline

Definition at line 469 of file LinearQuadtree.h.

◆ nodeX()

float ogdf::fast_multipole_embedder::LinearQuadtree::nodeX ( NodeID nodeID ) const

inline

Definition at line 461 of file LinearQuadtree.h.

◆ nodeY()

float ogdf::fast_multipole_embedder::LinearQuadtree::nodeY ( NodeID nodeID ) const

inline

Definition at line 465 of file LinearQuadtree.h.

◆ numberOfChilds()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfChilds ( NodeID nodeID ) const

inline

returns the number of children of node nodeID. for an inner node this is 1..4 and can be accessed by child(i). For a leaf the number of points in this leaf is returned starting with point child(0)

Definition at line 395 of file LinearQuadtree.h.

◆ numberOfDirectNodes()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfDirectNodes ( ) const

inline

Definition at line 530 of file LinearQuadtree.h.

◆ numberOfDirectPairs()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfDirectPairs ( ) const

inline

Definition at line 528 of file LinearQuadtree.h.

◆ numberOfInnerNodes()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfInnerNodes ( ) const

inline

Definition at line 520 of file LinearQuadtree.h.

◆ numberOfLeaves()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfLeaves ( ) const

inline

Definition at line 524 of file LinearQuadtree.h.

◆ numberOfNodes()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfNodes ( ) const

inline

returns the number of nodes in this tree

Definition at line 429 of file LinearQuadtree.h.

◆ numberOfPoints() [1/2]

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfPoints ( ) const

inline

returns the number of points in this tree

Definition at line 426 of file LinearQuadtree.h.

◆ numberOfPoints() [2/2]

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfPoints ( NodeID nodeID ) const

inline

returns the number of points contained in the subtree of node nodeID

Definition at line 415 of file LinearQuadtree.h.

◆ numberOfWSP()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::numberOfWSP ( ) const

inline

Definition at line 526 of file LinearQuadtree.h.

◆ point() [1/2]

LQPoint & ogdf::fast_multipole_embedder::LinearQuadtree::point ( PointID pointID )

inline

Definition at line 386 of file LinearQuadtree.h.

◆ point() [2/2]

const LQPoint & ogdf::fast_multipole_embedder::LinearQuadtree::point ( PointID pointID ) const

inline

Definition at line 388 of file LinearQuadtree.h.

◆ pointArray()

LQPoint * ogdf::fast_multipole_embedder::LinearQuadtree::pointArray ( )

inline

Definition at line 569 of file LinearQuadtree.h.

◆ pointLeaf()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::pointLeaf ( PointID point ) const

inline

Definition at line 445 of file LinearQuadtree.h.

◆ pointSize() [1/2]

float * ogdf::fast_multipole_embedder::LinearQuadtree::pointSize ( ) const

inline

Definition at line 459 of file LinearQuadtree.h.

◆ pointSize() [2/2]

float ogdf::fast_multipole_embedder::LinearQuadtree::pointSize ( PointID point ) const

inline

Definition at line 453 of file LinearQuadtree.h.

◆ pointX() [1/2]

float * ogdf::fast_multipole_embedder::LinearQuadtree::pointX ( ) const

inline

Definition at line 455 of file LinearQuadtree.h.

◆ pointX() [2/2]

float ogdf::fast_multipole_embedder::LinearQuadtree::pointX ( PointID point ) const

inline

Definition at line 449 of file LinearQuadtree.h.

◆ pointY() [1/2]

float * ogdf::fast_multipole_embedder::LinearQuadtree::pointY ( ) const

inline

Definition at line 457 of file LinearQuadtree.h.

◆ pointY() [2/2]

float ogdf::fast_multipole_embedder::LinearQuadtree::pointY ( PointID point ) const

inline

Definition at line 451 of file LinearQuadtree.h.

◆ refOfPoint()

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::refOfPoint ( PointID id ) const

inline

Definition at line 499 of file LinearQuadtree.h.

◆ root()

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::root ( ) const

inline

returns the index of the root

Definition at line 423 of file LinearQuadtree.h.

◆ scaleInv()

double ogdf::fast_multipole_embedder::LinearQuadtree::scaleInv ( ) const

inline

Definition at line 550 of file LinearQuadtree.h.

◆ setChild()

void ogdf::fast_multipole_embedder::LinearQuadtree::setChild	(	NodeID	nodeID,
		uint32_t	i,
		NodeID	c
	)

inline

sets the i th child index of node nodeID

Definition at line 406 of file LinearQuadtree.h.

◆ setFirstPoint()

void ogdf::fast_multipole_embedder::LinearQuadtree::setFirstPoint	(	NodeID	nodeID,
		PointID	firstPoint
	)

inline

Definition at line 382 of file LinearQuadtree.h.

◆ setLevel()

void ogdf::fast_multipole_embedder::LinearQuadtree::setLevel	(	NodeID	nodeID,
		uint32_t	level
	)

inline

Definition at line 378 of file LinearQuadtree.h.

◆ setNextNode()

void ogdf::fast_multipole_embedder::LinearQuadtree::setNextNode	(	NodeID	nodeID,
		NodeID	next
	)

inline

Definition at line 376 of file LinearQuadtree.h.

◆ setNodeSize()

void ogdf::fast_multipole_embedder::LinearQuadtree::setNodeSize	(	NodeID	nodeID,
		float	size
	)

inline

Definition at line 471 of file LinearQuadtree.h.

◆ setNodeX()

void ogdf::fast_multipole_embedder::LinearQuadtree::setNodeX	(	NodeID	nodeID,
		float	x
	)

inline

Definition at line 463 of file LinearQuadtree.h.

◆ setNodeY()

void ogdf::fast_multipole_embedder::LinearQuadtree::setNodeY	(	NodeID	nodeID,
		float	y
	)

inline

Definition at line 467 of file LinearQuadtree.h.

◆ setNumberOfChilds()

void ogdf::fast_multipole_embedder::LinearQuadtree::setNumberOfChilds	(	NodeID	nodeID,
		uint32_t	numChilds
	)

inline

sets the number of children of a node

Definition at line 398 of file LinearQuadtree.h.

◆ setNumberOfPoints()

void ogdf::fast_multipole_embedder::LinearQuadtree::setNumberOfPoints	(	NodeID	nodeID,
		uint32_t	numPoints
	)

inline

sets the number of nodes containted in node nodeID

Definition at line 418 of file LinearQuadtree.h.

◆ setPoint() [1/3]

void ogdf::fast_multipole_embedder::LinearQuadtree::setPoint	(	PointID	id,
		float	x,
		float	y,
		float	r
	)

inline

Definition at line 493 of file LinearQuadtree.h.

◆ setPoint() [2/3]

void ogdf::fast_multipole_embedder::LinearQuadtree::setPoint	(	PointID	id,
		float	x,
		float	y,
		float	r,
		uint32_t	ref
	)

inline

Definition at line 486 of file LinearQuadtree.h.

◆ setPoint() [3/3]

void ogdf::fast_multipole_embedder::LinearQuadtree::setPoint	(	PointID	id,
		float	x,
		float	y,
		uint32_t	ref
	)

inline

Definition at line 473 of file LinearQuadtree.h.

◆ setPointLeaf()

void ogdf::fast_multipole_embedder::LinearQuadtree::setPointLeaf	(	PointID	point,
		NodeID	leaf
	)

inline

Definition at line 447 of file LinearQuadtree.h.

◆ sizeInBytes()

uint64_t ogdf::fast_multipole_embedder::LinearQuadtree::sizeInBytes ( ) const

◆ StoreDirectNodeFunction()

StoreDirectNodeFunctor ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectNodeFunction ( )

inline

Definition at line 368 of file LinearQuadtree.h.

◆ StoreDirectPairFunction()

StoreDirectPairFunctor ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectPairFunction ( )

inline

Definition at line 356 of file LinearQuadtree.h.

◆ StoreWSPairFunction()

StoreWSPairFunctor ogdf::fast_multipole_embedder::LinearQuadtree::StoreWSPairFunction ( )

inline

Definition at line 346 of file LinearQuadtree.h.

◆ top_down_traversal() [1/2]

template<typename F >

top_down_traversal_functor< F > ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal ( F f ) const

inline

creator

Definition at line 227 of file LinearQuadtree.h.

◆ top_down_traversal() [2/2]

template<typename F , typename Cond >

top_down_traversal_functor< F, Cond > ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal	(	F	f,
		Cond	cond
	)		const

inline

creator

Definition at line 233 of file LinearQuadtree.h.

◆ updatePointPositionSize()

void ogdf::fast_multipole_embedder::LinearQuadtree::updatePointPositionSize ( PointID id )

inline

Definition at line 479 of file LinearQuadtree.h.

◆ wspd()

WSPD * ogdf::fast_multipole_embedder::LinearQuadtree::wspd ( ) const

inline

Definition at line 538 of file LinearQuadtree.h.

Friends And Related Symbol Documentation

◆ LinearQuadtreeBuilder

friend class LinearQuadtreeBuilder

friend

Definition at line 48 of file LinearQuadtree.h.

◆ LinearQuadtreeBuilderList

friend class LinearQuadtreeBuilderList

friend

Definition at line 49 of file LinearQuadtree.h.

Member Data Documentation

◆ m_cellSize

double ogdf::fast_multipole_embedder::LinearQuadtree::m_cellSize

private

the height and width of a grid cell

Definition at line 635 of file LinearQuadtree.h.

◆ m_directNodes

NodeID* ogdf::fast_multipole_embedder::LinearQuadtree::m_directNodes

private

Definition at line 691 of file LinearQuadtree.h.

◆ m_firstInner

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::m_firstInner

private

first inner node in the inner node chain

Definition at line 707 of file LinearQuadtree.h.

◆ m_firstLeaf

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::m_firstLeaf

private

first leaf in the leaf chain

Definition at line 701 of file LinearQuadtree.h.

◆ m_max_x

float ogdf::fast_multipole_embedder::LinearQuadtree::m_max_x

private

the x coordinate of the right most point

Definition at line 629 of file LinearQuadtree.h.

◆ m_max_y

float ogdf::fast_multipole_embedder::LinearQuadtree::m_max_y

private

the y coordinate of the top most point

Definition at line 632 of file LinearQuadtree.h.

◆ m_maxNumNodes

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_maxNumNodes

private

the maximum number of nodes (2*n here instead of 2*n-1)

Definition at line 678 of file LinearQuadtree.h.

◆ m_min_x

float ogdf::fast_multipole_embedder::LinearQuadtree::m_min_x

private

the x coordinate of the left most point

Definition at line 623 of file LinearQuadtree.h.

◆ m_min_y

float ogdf::fast_multipole_embedder::LinearQuadtree::m_min_y

private

the y coordinate of the bottom most point

Definition at line 626 of file LinearQuadtree.h.

◆ m_nodeSize

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_nodeSize

private

node size

Definition at line 672 of file LinearQuadtree.h.

◆ m_nodeXPos

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_nodeXPos

private

node x coord

Definition at line 665 of file LinearQuadtree.h.

◆ m_nodeYPos

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_nodeYPos

private

node y coord

Definition at line 669 of file LinearQuadtree.h.

◆ m_notWspd

LQWSPair* ogdf::fast_multipole_embedder::LinearQuadtree::m_notWspd

private

Definition at line 688 of file LinearQuadtree.h.

◆ m_numDirectNodes

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_numDirectNodes

private

Definition at line 692 of file LinearQuadtree.h.

◆ m_numInnerNodes

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_numInnerNodes

private

number of inner nodes in the chain

Definition at line 710 of file LinearQuadtree.h.

◆ m_numLeaves

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_numLeaves

private

number of leaves in the chain

Definition at line 704 of file LinearQuadtree.h.

◆ m_numNotWSP

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_numNotWSP

private

Definition at line 689 of file LinearQuadtree.h.

◆ m_numPoints

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_numPoints

private

number of points this quadtree is based on

Definition at line 684 of file LinearQuadtree.h.

◆ m_numWSP

uint32_t ogdf::fast_multipole_embedder::LinearQuadtree::m_numWSP

private

Definition at line 686 of file LinearQuadtree.h.

◆ m_origSize

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_origSize

private

point size in graph order

Definition at line 653 of file LinearQuadtree.h.

◆ m_origXPos

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_origXPos

private

point x coord in graph order

Definition at line 647 of file LinearQuadtree.h.

◆ m_origYPos

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_origYPos

private

point y coord in graph order

Definition at line 650 of file LinearQuadtree.h.

◆ m_points

LQPoint* ogdf::fast_multipole_embedder::LinearQuadtree::m_points

private

the point order in tree order

Definition at line 681 of file LinearQuadtree.h.

◆ m_pointSize

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_pointSize

private

point size in tree order

Definition at line 662 of file LinearQuadtree.h.

◆ m_pointXPos

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_pointXPos

private

point x coord in tree order

Definition at line 656 of file LinearQuadtree.h.

◆ m_pointYPos

float* ogdf::fast_multipole_embedder::LinearQuadtree::m_pointYPos

private

point y coord in tree order

Definition at line 659 of file LinearQuadtree.h.

◆ m_root

NodeID ogdf::fast_multipole_embedder::LinearQuadtree::m_root

private

the root of the tree

Definition at line 698 of file LinearQuadtree.h.

◆ m_scaleInv

double ogdf::fast_multipole_embedder::LinearQuadtree::m_scaleInv

private

the inverse scale to transform

Definition at line 638 of file LinearQuadtree.h.

◆ m_sideLengthGrid

double ogdf::fast_multipole_embedder::LinearQuadtree::m_sideLengthGrid

private

the resulting side length of the grid (constant)

Definition at line 644 of file LinearQuadtree.h.

◆ m_sideLengthPoints

double ogdf::fast_multipole_embedder::LinearQuadtree::m_sideLengthPoints

private

the maximum of height and width

Definition at line 641 of file LinearQuadtree.h.

◆ m_tree

LQNode* ogdf::fast_multipole_embedder::LinearQuadtree::m_tree

private

the main tree array containing all nodes (including leaves)

Definition at line 675 of file LinearQuadtree.h.

◆ m_WSPD

WSPD* ogdf::fast_multipole_embedder::LinearQuadtree::m_WSPD

private

the wspd of this quadtree

Definition at line 695 of file LinearQuadtree.h.

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

include/ogdf/energybased/fast_multipole_embedder/LinearQuadtree.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ NodeID

◆ PointID

Constructor & Destructor Documentation

◆ LinearQuadtree()

◆ ~LinearQuadtree()

Member Function Documentation

◆ addDirect()

◆ addDirectPair()

◆ addWSPD()

◆ allocate()

◆ bottom_up_traversal() [1/2]

◆ bottom_up_traversal() [2/2]

◆ child()

◆ clear()

◆ computeCoords()

◆ computeWSPD() [1/2]

◆ computeWSPD() [2/2]

◆ deallocate()

◆ directNode()

◆ directNodeA()

◆ directNodeB()

◆ findFirstPointInCell()

◆ firstInnerNode()

◆ firstLeaf()

◆ firstPoint()

◆ forall_children()

◆ forall_ordered_pairs_of_children()

◆ forall_points()

◆ forall_tree_nodes()

◆ forall_well_separated_pairs() [1/2]

◆ forall_well_separated_pairs() [2/2]

◆ init()

◆ initInnerNode()

◆ initLeaf()

◆ is_fence_condition()

◆ is_leaf_condition()

◆ isFence()

◆ isLeaf()

◆ isWS()

◆ leafAppendPoint()

◆ level()

◆ maxNumberOfNodes()

◆ maxX()

◆ maxY()

◆ minX()

◆ minY()

◆ mortonNr()

◆ nextNode()

◆ nodeAppendChild()

◆ nodeFence()

◆ nodeOfPoint()

◆ nodeSize()

◆ nodeX()

◆ nodeY()

◆ numberOfChilds()

◆ numberOfDirectNodes()

◆ numberOfDirectPairs()

◆ numberOfInnerNodes()

◆ numberOfLeaves()

◆ numberOfNodes()

◆ numberOfPoints() [1/2]

◆ numberOfPoints() [2/2]

◆ numberOfWSP()

◆ point() [1/2]

◆ point() [2/2]

◆ pointArray()

◆ pointLeaf()

◆ pointSize() [1/2]

◆ pointSize() [2/2]

◆ pointX() [1/2]

◆ pointX() [2/2]

Open
Graph Drawing
Framework