NetworKit::QuadNode< T, poincare > Class Template Reference

`#include <QuadNode.h>`

## Public Member Functions

QuadNode (double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity=1000, bool splitTheoretical=false, double alpha=1, double balance=0.5)
Construct a QuadNode for polar coordinates. More...

void split ()

void addContent (T input, double angle, double R)
Add a point at polar coordinates (angle, R) with content input. More...

bool removeContent (T input, double angle, double R)
Remove content at polar coordinates (angle, R). More...

bool outOfReach (Point2D< double > query, double radius) const
Check whether the region managed by this node lies outside of an Euclidean circle. More...

bool outOfReach (double angle_c, double r_c, double radius) const
Check whether the region managed by this node lies outside of an Euclidean circle. More...

std::pair< double, double > hyperbolicDistances (double phi, double r) const

bool responsible (double angle, double r) const
Does the point at (angle, r) fall inside the region managed by this QuadNode? More...

std::vector< T > getElements () const
Get all Elements in this QuadNode or a descendant of it. More...

void getCoordinates (vector< double > &anglesContainer, vector< double > &radiiContainer) const

QuadNode< T > & getAppropriateLeaf (double angle, double r)
Don't use this! Code is still in here for a unit test. More...

void getElementsInEuclideanCircle (Point2D< double > center, double radius, vector< T > &result, double minAngle=0, double maxAngle=2 *M_PI, double lowR=0, double highR=1) const
Main query method, get points lying in a Euclidean circle around the center point. More...

count getElementsProbabilistically (Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > &result) const

void maybeGetKthElement (double upperBound, Point2D< double > euQuery, std::function< double(double)> prob, index k, vector< T > &circleDenizens) const

void trim ()
Shrink all vectors in this subtree to fit the content. More...

count size () const
Number of points lying in the region managed by this QuadNode. More...

void recount ()

count height () const
Height of subtree hanging from this QuadNode. More...

count countLeaves () const
Leaf cells in the subtree hanging from this QuadNode. More...

double getLeftAngle () const

double getRightAngle () const

double getMinR () const

double getMaxR () const

index getID () const

index indexSubtree (index nextID)

index getCellID (double phi, double r) const

index getMaxIDInSubtree () const

count reindex (count offset)

## Constructor & Destructor Documentation

template<class T, bool poincare = true>
inline
template<class T, bool poincare = true>
 NetworKit::QuadNode< T, poincare >::QuadNode ( double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity = `1000`, bool splitTheoretical = `false`, double alpha = `1`, double balance = `0.5` )
inline

Construct a QuadNode for polar coordinates.

Parameters
 leftAngle Minimal angular coordinate of region, in radians from 0 to 2 minR Minimal radial coordinate of region, between 0 and 1 rightAngle Maximal angular coordinate of region, in radians from 0 to 2 maxR Maximal radial coordinate of region, between 0 and 1 capacity Number of points a leaf cell can store before splitting minDiameter Minimal diameter of a quadtree node. If the node is already smaller, don't split even if over capacity. Default is 0 splitTheoretical Whether to split in a theoretically optimal way or in a way to decrease measured running times alpha dispersion Parameter of the point distribution. Only has an effect if theoretical split is true diagnostics Count how many necessary and unnecessary comparisons happen in leaf cells? Will cause race condition and false sharing in parallel use

## Member Function Documentation

template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::addContent ( T input, double angle, double R )
inline

Add a point at polar coordinates (angle, R) with content input.

May split node if capacity is full

Parameters
 input arbitrary content, in our case an index angle angular coordinate of point, between 0 and 2 pi. R radial coordinate of point, between 0 and 1.
template<class T, bool poincare = true>
 count NetworKit::QuadNode< T, poincare >::countLeaves ( ) const
inline

Leaf cells in the subtree hanging from this QuadNode.

template<class T, bool poincare = true>
inline

Don't use this! Code is still in here for a unit test.

Get copy of the leaf cell responsible for a point at (angle, r). Expensive because it copies the whole subtree, causes assertion failure if called with the wrong arguments

Parameters
 angle Angular coordinate of point r Radial coordinate of point
Returns
Copy of leaf cell containing point, or dummy cell not responsible for point
template<class T, bool poincare = true>
 index NetworKit::QuadNode< T, poincare >::getCellID ( double phi, double r ) const
inline
template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::getCoordinates ( vector< double > & anglesContainer, vector< double > & radiiContainer ) const
inline
template<class T, bool poincare = true>
 std::vector NetworKit::QuadNode< T, poincare >::getElements ( ) const
inline

Get all Elements in this QuadNode or a descendant of it.

Returns
vector of content type T
template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::getElementsInEuclideanCircle ( Point2D< double > center, double radius, vector< T > & result, double minAngle = `0`, double maxAngle = `2*M_PI`, double lowR = `0`, double highR = `1` ) const
inline

Main query method, get points lying in a Euclidean circle around the center point.

Optional limits can be given to get a different result or to reduce unnecessary comparisons

Elements are pushed onto a vector which is a required argument. This is done to reduce copying

Safe to call in parallel if diagnostics are disabled

Parameters
 center Center of the query circle radius Radius of the query circle result Reference to the vector where the results will be stored minAngle Optional value for the minimum angular coordinate of the query region maxAngle Optional value for the maximum angular coordinate of the query region lowR Optional value for the minimum radial coordinate of the query region highR Optional value for the maximum radial coordinate of the query region
template<class T, bool poincare = true>
 count NetworKit::QuadNode< T, poincare >::getElementsProbabilistically ( Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > & result ) const
inline
template<class T, bool poincare = true>
 index NetworKit::QuadNode< T, poincare >::getID ( ) const
inline
template<class T, bool poincare = true>
 double NetworKit::QuadNode< T, poincare >::getLeftAngle ( ) const
inline
template<class T, bool poincare = true>
 index NetworKit::QuadNode< T, poincare >::getMaxIDInSubtree ( ) const
inline
template<class T, bool poincare = true>
 double NetworKit::QuadNode< T, poincare >::getMaxR ( ) const
inline
template<class T, bool poincare = true>
 double NetworKit::QuadNode< T, poincare >::getMinR ( ) const
inline
template<class T, bool poincare = true>
 double NetworKit::QuadNode< T, poincare >::getRightAngle ( ) const
inline
template<class T, bool poincare = true>
 count NetworKit::QuadNode< T, poincare >::height ( ) const
inline

Height of subtree hanging from this QuadNode.

template<class T, bool poincare = true>
 std::pair NetworKit::QuadNode< T, poincare >::hyperbolicDistances ( double phi, double r ) const
inline
Parameters
 phi Angular coordinate of query point r_h radial coordinate of query point in poincare disk

If the query point is not within the quadnode, the distance minimum is on the border. Need to check whether extremum is between corners:

cosh is a function from [0,) to [1, ) Variables thus need

template<class T, bool poincare = true>
 index NetworKit::QuadNode< T, poincare >::indexSubtree ( index nextID )
inline
template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::maybeGetKthElement ( double upperBound, Point2D< double > euQuery, std::function< double(double)> prob, index k, vector< T > & circleDenizens ) const
inline
template<class T, bool poincare = true>
 bool NetworKit::QuadNode< T, poincare >::outOfReach ( Point2D< double > query, double radius ) const
inline

Check whether the region managed by this node lies outside of an Euclidean circle.

Parameters
 query Center of the Euclidean query circle, given in Cartesian coordinates radius Radius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T, bool poincare = true>
 bool NetworKit::QuadNode< T, poincare >::outOfReach ( double angle_c, double r_c, double radius ) const
inline

Check whether the region managed by this node lies outside of an Euclidean circle.

Functionality is the same as in the method above, but it takes polar coordinates instead of Cartesian ones

Parameters
 angle_c Angular coordinate of the Euclidean query circle's center r_c Radial coordinate of the Euclidean query circle's center radius Radius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::recount ( )
inline
template<class T, bool poincare = true>
 count NetworKit::QuadNode< T, poincare >::reindex ( count offset )
inline
template<class T, bool poincare = true>
 bool NetworKit::QuadNode< T, poincare >::removeContent ( T input, double angle, double R )
inline

Remove content at polar coordinates (angle, R).

May cause coarsening of the quadtree

Parameters
 input Content to be removed angle Angular coordinate R Radial coordinate
Returns
True if content was found and removed, false otherwise
template<class T, bool poincare = true>
 bool NetworKit::QuadNode< T, poincare >::responsible ( double angle, double r ) const
inline

Does the point at (angle, r) fall inside the region managed by this QuadNode?

Parameters
 angle Angular coordinate of input point r Radial coordinate of input points
Returns
True if input point lies within the region of this QuadNode
template<class T, bool poincare = true>
 count NetworKit::QuadNode< T, poincare >::size ( ) const
inline

Number of points lying in the region managed by this QuadNode.

template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::split ( )
inline

we want to make sure the space is evenly divided to obtain a balanced tree Simply halving the radius will cause a larger space for the outer Quadnode, resulting in an unbalanced tree

template<class T, bool poincare = true>
 void NetworKit::QuadNode< T, poincare >::trim ( )
inline

Shrink all vectors in this subtree to fit the content.

Call after quadtree construction is complete, causes better memory usage and cache efficiency

## Friends And Related Function Documentation

template<class T, bool poincare = true>