# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::energybased::fmmm::NewMultipoleMethod Class Reference

#include <ogdf/energybased/fmmm/NewMultipoleMethod.h>

## Public Member Functions

NewMultipoleMethod ()
Constructor.

void calculate_repulsive_forces (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
Calculate rep. forces for each node.

void deallocate_memory ()
Dynamically allocated memory is freed here.

void make_initialisations (const Graph &G, double boxlength, DPoint down_left_corner, int particles_in_leaves, int precision, FMMMOptions::ReducedTreeConstruction tree_construction_way, FMMMOptions::SmallestCellFinding find_small_cell)
Make all initialisations that are needed for New Multipole Method (NMM)

void update_boxlength_and_cornercoordinate (double b_l, DPoint d_l_c)
Import updated information of the drawing area.

## Private Member Functions

The multipole expansion of *ptr_1 is transformed into a local expansion around the center of *ptr_2 and added to *ptr_2 s local expansion list.

The multipole expansion for every particle of leaf_ptr->contained_nodes (1,0,...) is transformed into a local expansion around the center of *ptr_2 and added to *ptr_2 s local expansion List;precondition: *leaf_ptr is a leaf.

void add_rep_forces (const Graph &G, NodeArray< DPoint > &F_direct, NodeArray< DPoint > &F_multipole_exp, NodeArray< DPoint > &F_local_exp, NodeArray< DPoint > &F_rep)
Add repulsive force contributions for each node.

Add the shifted ME Lists of *act_ptr to act_ptr->get_father_ptr() ; precondition *act_ptr has a father_node.

The shifted local expansion of the father of node_ptr is added to the local expansion of node_ptr;precondition: node_ptr is not the root of T.

double binko (int n, int k)
Returns n over k.

If ptr_1 and ptr_2 are nonequal and bordering true is returned; else false.

void calculate_local_expansions_and_WSPRLS (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *act_node_ptr)
According to NMM T is traversed recursively top-down starting from act_node_ptr == T.get_root_ptr() and thereby the lists D1, D2, M and LE are calculated for all treenodes.

void calculate_neighbourcell_forces (NodeArray< NodeAttributes > &A, List< QuadTreeNodeNM * > &quad_tree_leaves, NodeArray< DPoint > &F_direct)
For each leaf v in quad_tree_leaves the force contributions from all leaves in v.get_D1() and v.get_D2() are calculated.

void calculate_repulsive_forces_by_exact_method (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
Use the exact method for force calculation (used for small Graphs (|V| <= MIN_NODE_NUMBER) for speed reasons).

void calculate_repulsive_forces_by_NMM (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
Use NMM for force calculation (used for large Graphs (|V| > MIN_NODE_NUMBER)).

The reduced quad tree is deleted; Furthermore the treenode_number is calculated.

FMMMOptions::SmallestCellFinding find_sm_cell () const
Returns the way the smallest quadratic cell that surrounds the particles of a node in the reduced bucket quadtree is calculated.

void find_sm_cell (FMMMOptions::SmallestCellFinding scf)

void find_small_cell (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
Finds the small cell of the actual node using the selected algorithm.

void find_small_cell_by_formula (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
Finds the small cell of the actual Node of T by Aluru's Formula, and updates Sm_downleftcorner, Sm_boxlength, and level of *act_ptr.

void find_small_cell_iteratively (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
Finds the small cell of the actual Node of T iteratively,and updates Sm_downleftcorner, Sm_boxlength, and level of *act_ptr.

void form_multipole_expansion_of_leaf_node (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *act_ptr)
Calculate List ME for *act_ptr Precondition: *act_ptr is a leaf.

The multipole expansion List ME for the tree rooted at T.get_act_ptr() is recursively calculated.

The multipole expansion terms ME are calculated for all nodes of T ( centers are initialized for each cell and quad_tree_leaves stores pointers to leaves of T).

void free_binko ()
Free space for BK.

void init_binko (int t)
Init BK -matrix for values n, k in 0 to t.

The Lists ME and LE are both initialized to zero entries for *act_ptr.

int maxboxindex (int level)
Returns the maximal index of a box in level i.

int particles_in_leaves () const

void particles_in_leaves (int b)
Max. number of particles that are contained in a leaf of the red. quadtree.

int power_of_two (int i)
Returns power_of_2[i] for values <= max_power_of_2_index.

int precision () const

void precision (int p)
The precision p for the p-term multipole expansions.

The center of the box of *act_ptr is initialized.

void transform_local_exp_to_forces (NodeArray< NodeAttributes > &A, List< QuadTreeNodeNM * > &quad_tree_leaves, NodeArray< DPoint > &F_local_exp)
For each leaf v in quad_tree_leaves the force contribution defined by v.get_local_exp() is calculated and stored in F_local_exp.

void transform_multipole_exp_to_forces (NodeArray< NodeAttributes > &A, List< QuadTreeNodeNM * > &quad_tree_leaves, NodeArray< DPoint > &F_multipole_exp)
For each leaf v in quad_tree_leaves the force contribution defined by all nodes in v.get_M() is calculated and stored in F_multipole_exp.

FMMMOptions::ReducedTreeConstruction tree_construction_way () const
Returns the way to construct the reduced tree.

void tree_construction_way (FMMMOptions::ReducedTreeConstruction rtc)

If the small cell of ptr_1 and ptr_2 are well separated true is returned (else false).

Functions needed for path by path tree construction
The reduced quadtree is build up path by path (the Lists LE,ME, the centers, D1, D2, M, and quad_tree_leaves are not calculated here.

void make_copy_and_init_Lists (List< ParticleInfo > &L_x_orig, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_orig, List< ParticleInfo > &L_y_copy)
Makes L_x(y)_copy a copy of L_x(y)_orig and sets p.copy_item for each element in L_x(y)_orig to the ListIterator of the corresponding element in L_x(y)_copy. Furthermore, the p.cross_ref_items in L_x(y)_copy are set and p.subList_ptr and p.tmp_cross_ref_item is reset to nullptr in both lists.

void build_up_root_node (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
The root node of T is constructed.

void create_sorted_coordinate_Lists (const Graph &G, NodeArray< NodeAttributes > &A, List< ParticleInfo > &L_x, List< ParticleInfo > &L_y)
The sorted and linked Lists L_x and L_y for the root node are created.

void decompose_subtreenode (QuadTreeNM &T, List< ParticleInfo > &act_x_List_copy, List< ParticleInfo > &act_y_List_copy, List< QuadTreeNodeNM * > &new_leaf_List)
T is extended by a subtree T1 rooted at the T.get_act_node(). The boxlength and down_left_corner of the actual node is reduced if it is not the minimal subquad that contains all the particles in the represented area.

void calculate_boundaries_of_act_node (QuadTreeNodeNM *act_ptr, DPoint &min, DPoint &max)
The extreme coordinates of the particles contained in *act_ptr are calculated.

Returns true if the rectangle defined by min and max lies within the left(right)_top(bottom) quad of the small cell of *act_ptr.

bool quadHelper (DPoint min, DPoint max, DPoint bottomleft, DPoint topright, QuadTreeNodeNM *act_ptr)

void split (QuadTreeNodeNM *act_ptr, List< ParticleInfo > *&L_x_left_ptr, List< ParticleInfo > *&L_y_left_ptr, List< ParticleInfo > *&L_x_right_ptr, List< ParticleInfo > *&L_y_right_ptr, bool isHorizontal)
The Lists *act_ptr->get_x(y)_List_ptr() are split into two sublists containing the particles in the left and right half of the actual quad. The list that is larger is constructed from *act_ptr->get_x(y)_List_ptr() by deleting the other elements; The smaller List stays empty at this point, but the corresponding elements in L_x(y)_copy contain a pointer to the x(y) List, where they belong to. If isHorizontal is true, we are talking about the respective x lists, otherwise about the y lists.

void delete_subLists (QuadTreeNodeNM *act_ptr, List< ParticleInfo > *&L_x_left_ptr, List< ParticleInfo > *&L_y_left_ptr, List< ParticleInfo > *&L_x_right_ptr, List< ParticleInfo > *&L_y_right_ptr, ListIterator< ParticleInfo > last_left_item, bool deleteRight, bool isHorizontal)
The Lists *L_x(y)_left_ptr are constructed from *act_ptr->get_x(y)_List_ptr() by deleting all elements right (if deleteRight is true, otherwise left) from last_left_item in *act_ptr->get_x_List_ptr() the corresponding values in *act_ptr->get_y_List_ptr() are deleted as well. The corresponding List-elements of the deleted elements in the Lists L_x(y)_copy hold the information, that they belong to the Lists *L_x(y)_left_ptr. If isHorizontal is true, we are talking about the respective x lists, otherwise about the y lists.

void split_in_y_direction (QuadTreeNodeNM *act_ptr, List< ParticleInfo > *&L_x_ptr, List< ParticleInfo > *&L_x_b_ptr, List< ParticleInfo > *&L_x_t_ptr, List< ParticleInfo > *&L_y_ptr, List< ParticleInfo > *&L_y_b_ptr, List< ParticleInfo > *&L_y_t_ptr)
The Lists *L_x(y)_b_ptr and *L_x(y)_t_ptr are constructed from the Lists *L_x(y)_ptr.

void move_subLists_vertical (List< ParticleInfo > *&L_x_ptr, List< ParticleInfo > *&L_x_b_ptr, List< ParticleInfo > *&L_x_t_ptr, List< ParticleInfo > *&L_y_ptr, List< ParticleInfo > *&L_y_b_ptr, List< ParticleInfo > *&L_y_t_ptr, ListIterator< ParticleInfo > last_left_item, bool moveRight)
The Lists *L_x(y)_b(t)_ptr are constructed from the Lists *L_x(y)_ptr by moving all List elements from *L_x(y)_ptr that belong to *L_x(y)_l_ptr (moveRight false) or *L_x(y)_r_ptr (moveRight true) to this List. The L_x(y)_right_ptr point to the reduced Lists L_x(y)_ptr afterwards but the elements that belong to *&L_x(y)_right_ptr are moved.

void build_up_sorted_subLists (List< ParticleInfo > &L_x_copy, List< ParticleInfo > &act_y_List_copy)
The sorted subLists, that can be accesssed by the entries in L_x(y)_copy->get_subList_ptr() are constructed.

Functions needed for subtree by subtree tree construction
The reduced quadtree is build up subtree by subtree (the lists LE, ME the centers, D1, D2, M, quad_tree_leaves are not calculated here.

void build_up_root_vertex (const Graph &G, QuadTreeNM &T)
The root node of T is constructed and contained_nodes is set to the list of all nodes of G.

The reduced subtree of T rooted at *subtree_root_ptr containing all the particles of subtree_root_ptr->get_contained_nodes() is constructed; Pointers to leaves of the subtree that contain more than particles_in_leaves() particles in their contained_nodes() lists are added to new_subtree_root_List_ptr; The lists contained_nodes() are nonempty only for the (actual) leaves of T.

void construct_complete_subtree (QuadTreeNM &T, int subtree_depth, Array2D< QuadTreeNodeNM * > &leaf_ptr, int act_depth, int act_x_index, int act_y_index)
A complete subtree of T and of depth subtree_depth, rooted at *T.get_act_ptr() is constructed. Furthermore leaf_ptr[i][j] points to a leaf node of the subtree that represents the quadratic subregion of *T.get_act_ptr() at subtree_depth and position [i][j] i,j in 0,...,maxindex;act_depth(x_index,y_index) are helping variables for recursive calls.

void set_contained_nodes_for_leaves (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *subtree_root_ptr, Array2D< QuadTreeNodeNM * > &leaf_ptr, int maxindex)
The particles in subtree_root_ptr->get_contained_nodes() are assigned to the the contained_nodes lists of the leaves of the subtree by using the information of A,leaf_ptr and maxindex. Afterwards contained_nodes of *subtree_root_ptr is empty.

The subtree of T rooted at *T.get_act_ptr() is traversed bottom up, such that the subtreeparticlenumber of every node in this subtree is set correctly.

void construct_reduced_subtree (NodeArray< NodeAttributes > &A, QuadTreeNM &T, List< QuadTreeNodeNM * > &new_subtree_root_List)
The reduced subtree rooted at *T.get_act_ptr() is calculated ; A pointer to every leaf of this subtree that contains more then particles_in_leaves() particles is added to new_subtree_root_List; The lists contained_nodes are empty for all but the leaves.

All subtrees of *T.get_act_ptr() that have a child c of *T.get_act_ptr() as root and c.get_particlenumber_in_subtree() == 0 are deleted.

If *T.get_act_ptr() is a degenerated node (has only one child c) *T.get_act_ptr() is deleted from T and the child c is linked with the father of *T.get_act_ptr() if *T.get_act_ptr() is the root of T than c is set to the new root of T T.get_act_ptr() points to c afterwards; Furthermore true is returned if *T.get_act_ptr() has been degenerated, else false is returned.

The subtree rooted at new_leaf_ptr is deleted, *new_leaf_ptr is a leaf of T and new_leaf_ptr->get_contained_nodes() contains all the particles contained in the leaves of the deleted subtree; Precondition: T.get_act_ptr() is new_leaf_ptr.

new_leaf_ptr->get_contained_nodes() contains all the particles contained in the leaves of its subtree afterwards; Precondition: T.get_act_ptr() is new_leaf_ptr

If all nodes in T.get_act_ptr()->get_contained_nodes() have the same position false is returned. Else true is returned and the boxlength, down_left_corner and level of *T.get_act_ptr() is updated such that this values are minimal (i.e. the smallest quad that contains all the particles of T.get_act_ptr()->get_contained_nodes(); If all this particles are placed at a point nothing is done.

## Private Attributes

FMMMOptions::SmallestCellFinding _find_small_cell

int _particles_in_leaves
max.

int _precision
precision for p-term multipole expansion

FMMMOptions::ReducedTreeConstruction _tree_construction_way

double ** BK
holds the binomial coefficients

double boxlength
length of drawing box

DPoint down_left_corner
down left corner of drawing box

FruchtermanReingold ExactMethod
needed in case that using_NMM == false

const int max_power_of_2_index
holds max.

int MIN_NODE_NUMBER
The minimum number of nodes for which the forces are calculated using NMM (for lower values the exact calculation is used).

List< DPointrep_forces
stores the rep. forces of the last iteration needed for error calculation)

bool using_NMM
Indicates whether the exact method or NMM is used for force calculation (value depends on MIN_NODE_NUMBER)

## Detailed Description

Definition at line 48 of file NewMultipoleMethod.h.

## ◆ NewMultipoleMethod()

 ogdf::energybased::fmmm::NewMultipoleMethod::NewMultipoleMethod ( )

Constructor.

## Member Function Documentation

private

The multipole expansion of *ptr_1 is transformed into a local expansion around the center of *ptr_2 and added to *ptr_2 s local expansion list.

private

The multipole expansion for every particle of leaf_ptr->contained_nodes (1,0,...) is transformed into a local expansion around the center of *ptr_2 and added to *ptr_2 s local expansion List;precondition: *leaf_ptr is a leaf.

 void ogdf::energybased::fmmm::NewMultipoleMethod::add_rep_forces ( const Graph & G, NodeArray< DPoint > & F_direct, NodeArray< DPoint > & F_multipole_exp, NodeArray< DPoint > & F_local_exp, NodeArray< DPoint > & F_rep )
private

Add repulsive force contributions for each node.

private

Add the shifted ME Lists of *act_ptr to act_ptr->get_father_ptr() ; precondition *act_ptr has a father_node.

private

The shifted local expansion of the father of node_ptr is added to the local expansion of node_ptr;precondition: node_ptr is not the root of T.

## ◆ binko()

 double ogdf::energybased::fmmm::NewMultipoleMethod::binko ( int n, int k )
private

Returns n over k.

## ◆ bordering()

private

If ptr_1 and ptr_2 are nonequal and bordering true is returned; else false.

 void ogdf::energybased::fmmm::NewMultipoleMethod::build_up_red_quad_tree_path_by_path ( const Graph & G, NodeArray< NodeAttributes > & A, QuadTreeNM & T )
private

The reduced quadtree is build up path by path (the Lists LE,ME, the centers, D1, D2, M, and quad_tree_leaves are not calculated here.

 void ogdf::energybased::fmmm::NewMultipoleMethod::build_up_red_quad_tree_subtree_by_subtree ( const Graph & G, NodeArray< NodeAttributes > & A, QuadTreeNM & T )
private

The reduced quadtree is build up subtree by subtree (the lists LE, ME the centers, D1, D2, M, quad_tree_leaves are not calculated here.

## ◆ build_up_root_node()

 void ogdf::energybased::fmmm::NewMultipoleMethod::build_up_root_node ( const Graph & G, NodeArray< NodeAttributes > & A, QuadTreeNM & T )
private

The root node of T is constructed.

## ◆ build_up_root_vertex()

 void ogdf::energybased::fmmm::NewMultipoleMethod::build_up_root_vertex ( const Graph & G, QuadTreeNM & T )
private

The root node of T is constructed and contained_nodes is set to the list of all nodes of G.

## ◆ build_up_sorted_subLists()

 void ogdf::energybased::fmmm::NewMultipoleMethod::build_up_sorted_subLists ( List< ParticleInfo > & L_x_copy, List< ParticleInfo > & act_y_List_copy )
private

The sorted subLists, that can be accesssed by the entries in L_x(y)_copy->get_subList_ptr() are constructed.

## ◆ calculate_boundaries_of_act_node()

 void ogdf::energybased::fmmm::NewMultipoleMethod::calculate_boundaries_of_act_node ( QuadTreeNodeNM * act_ptr, DPoint & min, DPoint & max )
private

The extreme coordinates of the particles contained in *act_ptr are calculated.

## ◆ calculate_local_expansions_and_WSPRLS()

 void ogdf::energybased::fmmm::NewMultipoleMethod::calculate_local_expansions_and_WSPRLS ( NodeArray< NodeAttributes > & A, QuadTreeNodeNM * act_node_ptr )
private

According to NMM T is traversed recursively top-down starting from act_node_ptr == T.get_root_ptr() and thereby the lists D1, D2, M and LE are calculated for all treenodes.

## ◆ calculate_neighbourcell_forces()

 void ogdf::energybased::fmmm::NewMultipoleMethod::calculate_neighbourcell_forces ( NodeArray< NodeAttributes > & A, List< QuadTreeNodeNM * > & quad_tree_leaves, NodeArray< DPoint > & F_direct )
private

For each leaf v in quad_tree_leaves the force contributions from all leaves in v.get_D1() and v.get_D2() are calculated.

## ◆ calculate_repulsive_forces()

 void ogdf::energybased::fmmm::NewMultipoleMethod::calculate_repulsive_forces ( const Graph & G, NodeArray< NodeAttributes > & A, NodeArray< DPoint > & F_rep )

Calculate rep. forces for each node.

## ◆ calculate_repulsive_forces_by_exact_method()

 void ogdf::energybased::fmmm::NewMultipoleMethod::calculate_repulsive_forces_by_exact_method ( const Graph & G, NodeArray< NodeAttributes > & A, NodeArray< DPoint > & F_rep )
private

Use the exact method for force calculation (used for small Graphs (|V| <= MIN_NODE_NUMBER) for speed reasons).

## ◆ calculate_repulsive_forces_by_NMM()

 void ogdf::energybased::fmmm::NewMultipoleMethod::calculate_repulsive_forces_by_NMM ( const Graph & G, NodeArray< NodeAttributes > & A, NodeArray< DPoint > & F_rep )
private

Use NMM for force calculation (used for large Graphs (|V| > MIN_NODE_NUMBER)).

## ◆ check_and_delete_degenerated_node()

 bool ogdf::energybased::fmmm::NewMultipoleMethod::check_and_delete_degenerated_node ( QuadTreeNM & T )
private

If *T.get_act_ptr() is a degenerated node (has only one child c) *T.get_act_ptr() is deleted from T and the child c is linked with the father of *T.get_act_ptr() if *T.get_act_ptr() is the root of T than c is set to the new root of T T.get_act_ptr() points to c afterwards; Furthermore true is returned if *T.get_act_ptr() has been degenerated, else false is returned.

## ◆ collect_contained_nodes()

private

new_leaf_ptr->get_contained_nodes() contains all the particles contained in the leaves of its subtree afterwards; Precondition: T.get_act_ptr() is new_leaf_ptr

## ◆ construct_complete_subtree()

 void ogdf::energybased::fmmm::NewMultipoleMethod::construct_complete_subtree ( QuadTreeNM & T, int subtree_depth, Array2D< QuadTreeNodeNM * > & leaf_ptr, int act_depth, int act_x_index, int act_y_index )
private

A complete subtree of T and of depth subtree_depth, rooted at *T.get_act_ptr() is constructed. Furthermore leaf_ptr[i][j] points to a leaf node of the subtree that represents the quadratic subregion of *T.get_act_ptr() at subtree_depth and position [i][j] i,j in 0,...,maxindex;act_depth(x_index,y_index) are helping variables for recursive calls.

## ◆ construct_reduced_subtree()

 void ogdf::energybased::fmmm::NewMultipoleMethod::construct_reduced_subtree ( NodeArray< NodeAttributes > & A, QuadTreeNM & T, List< QuadTreeNodeNM * > & new_subtree_root_List )
private

The reduced subtree rooted at *T.get_act_ptr() is calculated ; A pointer to every leaf of this subtree that contains more then particles_in_leaves() particles is added to new_subtree_root_List; The lists contained_nodes are empty for all but the leaves.

## ◆ construct_subtree()

 void ogdf::energybased::fmmm::NewMultipoleMethod::construct_subtree ( NodeArray< NodeAttributes > & A, QuadTreeNM & T, QuadTreeNodeNM * subtree_root_ptr, List< QuadTreeNodeNM * > & new_subtree_root_List )
private

The reduced subtree of T rooted at *subtree_root_ptr containing all the particles of subtree_root_ptr->get_contained_nodes() is constructed; Pointers to leaves of the subtree that contain more than particles_in_leaves() particles in their contained_nodes() lists are added to new_subtree_root_List_ptr; The lists contained_nodes() are nonempty only for the (actual) leaves of T.

## ◆ create_sorted_coordinate_Lists()

 void ogdf::energybased::fmmm::NewMultipoleMethod::create_sorted_coordinate_Lists ( const Graph & G, NodeArray< NodeAttributes > & A, List< ParticleInfo > & L_x, List< ParticleInfo > & L_y )
private

The sorted and linked Lists L_x and L_y for the root node are created.

## ◆ deallocate_memory()

 void ogdf::energybased::fmmm::NewMultipoleMethod::deallocate_memory ( )

Dynamically allocated memory is freed here.

## ◆ decompose_subtreenode()

 void ogdf::energybased::fmmm::NewMultipoleMethod::decompose_subtreenode ( QuadTreeNM & T, List< ParticleInfo > & act_x_List_copy, List< ParticleInfo > & act_y_List_copy, List< QuadTreeNodeNM * > & new_leaf_List )
private

T is extended by a subtree T1 rooted at the T.get_act_node(). The boxlength and down_left_corner of the actual node is reduced if it is not the minimal subquad that contains all the particles in the represented area.

## ◆ delete_empty_subtrees()

 void ogdf::energybased::fmmm::NewMultipoleMethod::delete_empty_subtrees ( QuadTreeNM & T )
private

All subtrees of *T.get_act_ptr() that have a child c of *T.get_act_ptr() as root and c.get_particlenumber_in_subtree() == 0 are deleted.

private

The reduced quad tree is deleted; Furthermore the treenode_number is calculated.

## ◆ delete_sparse_subtree()

private

The subtree rooted at new_leaf_ptr is deleted, *new_leaf_ptr is a leaf of T and new_leaf_ptr->get_contained_nodes() contains all the particles contained in the leaves of the deleted subtree; Precondition: T.get_act_ptr() is new_leaf_ptr.

## ◆ delete_subLists()

 void ogdf::energybased::fmmm::NewMultipoleMethod::delete_subLists ( QuadTreeNodeNM * act_ptr, List< ParticleInfo > *& L_x_left_ptr, List< ParticleInfo > *& L_y_left_ptr, List< ParticleInfo > *& L_x_right_ptr, List< ParticleInfo > *& L_y_right_ptr, ListIterator< ParticleInfo > last_left_item, bool deleteRight, bool isHorizontal )
private

The Lists *L_x(y)_left_ptr are constructed from *act_ptr->get_x(y)_List_ptr() by deleting all elements right (if deleteRight is true, otherwise left) from last_left_item in *act_ptr->get_x_List_ptr() the corresponding values in *act_ptr->get_y_List_ptr() are deleted as well. The corresponding List-elements of the deleted elements in the Lists L_x(y)_copy hold the information, that they belong to the Lists *L_x(y)_left_ptr. If isHorizontal is true, we are talking about the respective x lists, otherwise about the y lists.

## ◆ find_sm_cell() [1/2]

 FMMMOptions::SmallestCellFinding ogdf::energybased::fmmm::NewMultipoleMethod::find_sm_cell ( ) const
inlineprivate

Returns the way the smallest quadratic cell that surrounds the particles of a node in the reduced bucket quadtree is calculated.

Definition at line 389 of file NewMultipoleMethod.h.

## ◆ find_sm_cell() [2/2]

 void ogdf::energybased::fmmm::NewMultipoleMethod::find_sm_cell ( FMMMOptions::SmallestCellFinding scf )
inlineprivate

Definition at line 391 of file NewMultipoleMethod.h.

## ◆ find_small_cell()

 void ogdf::energybased::fmmm::NewMultipoleMethod::find_small_cell ( QuadTreeNodeNM * act_ptr, DPoint min, DPoint max )
inlineprivate

Finds the small cell of the actual node using the selected algorithm.

Definition at line 285 of file NewMultipoleMethod.h.

## ◆ find_small_cell_by_formula()

 void ogdf::energybased::fmmm::NewMultipoleMethod::find_small_cell_by_formula ( QuadTreeNodeNM * act_ptr, DPoint min, DPoint max )
private

Finds the small cell of the actual Node of T by Aluru's Formula, and updates Sm_downleftcorner, Sm_boxlength, and level of *act_ptr.

## ◆ find_small_cell_iteratively()

 void ogdf::energybased::fmmm::NewMultipoleMethod::find_small_cell_iteratively ( QuadTreeNodeNM * act_ptr, DPoint min, DPoint max )
private

Finds the small cell of the actual Node of T iteratively,and updates Sm_downleftcorner, Sm_boxlength, and level of *act_ptr.

 bool ogdf::energybased::fmmm::NewMultipoleMethod::find_smallest_quad ( NodeArray< NodeAttributes > & A, QuadTreeNM & T )
private

If all nodes in T.get_act_ptr()->get_contained_nodes() have the same position false is returned. Else true is returned and the boxlength, down_left_corner and level of *T.get_act_ptr() is updated such that this values are minimal (i.e. the smallest quad that contains all the particles of T.get_act_ptr()->get_contained_nodes(); If all this particles are placed at a point nothing is done.

## ◆ form_multipole_expansion_of_leaf_node()

 void ogdf::energybased::fmmm::NewMultipoleMethod::form_multipole_expansion_of_leaf_node ( NodeArray< NodeAttributes > & A, QuadTreeNodeNM * act_ptr )
private

Calculate List ME for *act_ptr Precondition: *act_ptr is a leaf.

## ◆ form_multipole_expansion_of_subtree()

 void ogdf::energybased::fmmm::NewMultipoleMethod::form_multipole_expansion_of_subtree ( NodeArray< NodeAttributes > & A, QuadTreeNM & T, List< QuadTreeNodeNM * > & quad_tree_leaves )
private

The multipole expansion List ME for the tree rooted at T.get_act_ptr() is recursively calculated.

## ◆ form_multipole_expansions()

 void ogdf::energybased::fmmm::NewMultipoleMethod::form_multipole_expansions ( NodeArray< NodeAttributes > & A, QuadTreeNM & T, List< QuadTreeNodeNM * > & quad_tree_leaves )
private

The multipole expansion terms ME are calculated for all nodes of T ( centers are initialized for each cell and quad_tree_leaves stores pointers to leaves of T).

## ◆ free_binko()

 void ogdf::energybased::fmmm::NewMultipoleMethod::free_binko ( )
private

Free space for BK.

private

private

Returns true if the rectangle defined by min and max lies within the left(right)_top(bottom) quad of the small cell of *act_ptr.

private

private

## ◆ init_binko()

 void ogdf::energybased::fmmm::NewMultipoleMethod::init_binko ( int t )
private

Init BK -matrix for values n, k in 0 to t.

## ◆ init_expansion_Lists()

 void ogdf::energybased::fmmm::NewMultipoleMethod::init_expansion_Lists ( QuadTreeNodeNM * act_ptr )
private

The Lists ME and LE are both initialized to zero entries for *act_ptr.

## ◆ make_copy_and_init_Lists()

 void ogdf::energybased::fmmm::NewMultipoleMethod::make_copy_and_init_Lists ( List< ParticleInfo > & L_x_orig, List< ParticleInfo > & L_x_copy, List< ParticleInfo > & L_y_orig, List< ParticleInfo > & L_y_copy )
private

Makes L_x(y)_copy a copy of L_x(y)_orig and sets p.copy_item for each element in L_x(y)_orig to the ListIterator of the corresponding element in L_x(y)_copy. Furthermore, the p.cross_ref_items in L_x(y)_copy are set and p.subList_ptr and p.tmp_cross_ref_item is reset to nullptr in both lists.

## ◆ make_initialisations()

 void ogdf::energybased::fmmm::NewMultipoleMethod::make_initialisations ( const Graph & G, double boxlength, DPoint down_left_corner, int particles_in_leaves, int precision, FMMMOptions::ReducedTreeConstruction tree_construction_way, FMMMOptions::SmallestCellFinding find_small_cell )

Make all initialisations that are needed for New Multipole Method (NMM)

## ◆ maxboxindex()

 int ogdf::energybased::fmmm::NewMultipoleMethod::maxboxindex ( int level )
private

Returns the maximal index of a box in level i.

## ◆ move_subLists_vertical()

 void ogdf::energybased::fmmm::NewMultipoleMethod::move_subLists_vertical ( List< ParticleInfo > *& L_x_ptr, List< ParticleInfo > *& L_x_b_ptr, List< ParticleInfo > *& L_x_t_ptr, List< ParticleInfo > *& L_y_ptr, List< ParticleInfo > *& L_y_b_ptr, List< ParticleInfo > *& L_y_t_ptr, ListIterator< ParticleInfo > last_left_item, bool moveRight )
private

The Lists *L_x(y)_b(t)_ptr are constructed from the Lists *L_x(y)_ptr by moving all List elements from *L_x(y)_ptr that belong to *L_x(y)_l_ptr (moveRight false) or *L_x(y)_r_ptr (moveRight true) to this List. The L_x(y)_right_ptr point to the reduced Lists L_x(y)_ptr afterwards but the elements that belong to *&L_x(y)_right_ptr are moved.

## ◆ particles_in_leaves() [1/2]

 int ogdf::energybased::fmmm::NewMultipoleMethod::particles_in_leaves ( ) const
inlineprivate

Definition at line 396 of file NewMultipoleMethod.h.

## ◆ particles_in_leaves() [2/2]

 void ogdf::energybased::fmmm::NewMultipoleMethod::particles_in_leaves ( int b )
inlineprivate

Max. number of particles that are contained in a leaf of the red. quadtree.

Definition at line 394 of file NewMultipoleMethod.h.

## ◆ power_of_two()

 int ogdf::energybased::fmmm::NewMultipoleMethod::power_of_two ( int i )
private

Returns power_of_2[i] for values <= max_power_of_2_index.

## ◆ precision() [1/2]

 int ogdf::energybased::fmmm::NewMultipoleMethod::precision ( ) const
inlineprivate

Definition at line 401 of file NewMultipoleMethod.h.

## ◆ precision() [2/2]

 void ogdf::energybased::fmmm::NewMultipoleMethod::precision ( int p )
inlineprivate

The precision p for the p-term multipole expansions.

Definition at line 399 of file NewMultipoleMethod.h.

 bool ogdf::energybased::fmmm::NewMultipoleMethod::quadHelper ( DPoint min, DPoint max, DPoint bottomleft, DPoint topright, QuadTreeNodeNM * act_ptr )
private

## ◆ set_center()

 void ogdf::energybased::fmmm::NewMultipoleMethod::set_center ( QuadTreeNodeNM * act_ptr )
private

The center of the box of *act_ptr is initialized.

## ◆ set_contained_nodes_for_leaves()

 void ogdf::energybased::fmmm::NewMultipoleMethod::set_contained_nodes_for_leaves ( NodeArray< NodeAttributes > & A, QuadTreeNodeNM * subtree_root_ptr, Array2D< QuadTreeNodeNM * > & leaf_ptr, int maxindex )
private

The particles in subtree_root_ptr->get_contained_nodes() are assigned to the the contained_nodes lists of the leaves of the subtree by using the information of A,leaf_ptr and maxindex. Afterwards contained_nodes of *subtree_root_ptr is empty.

## ◆ set_particlenumber_in_subtree_entries()

 void ogdf::energybased::fmmm::NewMultipoleMethod::set_particlenumber_in_subtree_entries ( QuadTreeNM & T )
private

The subtree of T rooted at *T.get_act_ptr() is traversed bottom up, such that the subtreeparticlenumber of every node in this subtree is set correctly.

## ◆ split()

 void ogdf::energybased::fmmm::NewMultipoleMethod::split ( QuadTreeNodeNM * act_ptr, List< ParticleInfo > *& L_x_left_ptr, List< ParticleInfo > *& L_y_left_ptr, List< ParticleInfo > *& L_x_right_ptr, List< ParticleInfo > *& L_y_right_ptr, bool isHorizontal )
private

The Lists *act_ptr->get_x(y)_List_ptr() are split into two sublists containing the particles in the left and right half of the actual quad. The list that is larger is constructed from *act_ptr->get_x(y)_List_ptr() by deleting the other elements; The smaller List stays empty at this point, but the corresponding elements in L_x(y)_copy contain a pointer to the x(y) List, where they belong to. If isHorizontal is true, we are talking about the respective x lists, otherwise about the y lists.

## ◆ split_in_y_direction()

 void ogdf::energybased::fmmm::NewMultipoleMethod::split_in_y_direction ( QuadTreeNodeNM * act_ptr, List< ParticleInfo > *& L_x_ptr, List< ParticleInfo > *& L_x_b_ptr, List< ParticleInfo > *& L_x_t_ptr, List< ParticleInfo > *& L_y_ptr, List< ParticleInfo > *& L_y_b_ptr, List< ParticleInfo > *& L_y_t_ptr )
private

The Lists *L_x(y)_b_ptr and *L_x(y)_t_ptr are constructed from the Lists *L_x(y)_ptr.

## ◆ transform_local_exp_to_forces()

 void ogdf::energybased::fmmm::NewMultipoleMethod::transform_local_exp_to_forces ( NodeArray< NodeAttributes > & A, List< QuadTreeNodeNM * > & quad_tree_leaves, NodeArray< DPoint > & F_local_exp )
private

For each leaf v in quad_tree_leaves the force contribution defined by v.get_local_exp() is calculated and stored in F_local_exp.

## ◆ transform_multipole_exp_to_forces()

 void ogdf::energybased::fmmm::NewMultipoleMethod::transform_multipole_exp_to_forces ( NodeArray< NodeAttributes > & A, List< QuadTreeNodeNM * > & quad_tree_leaves, NodeArray< DPoint > & F_multipole_exp )
private

For each leaf v in quad_tree_leaves the force contribution defined by all nodes in v.get_M() is calculated and stored in F_multipole_exp.

## ◆ tree_construction_way() [1/2]

 FMMMOptions::ReducedTreeConstruction ogdf::energybased::fmmm::NewMultipoleMethod::tree_construction_way ( ) const
inlineprivate

Returns the way to construct the reduced tree.

Definition at line 379 of file NewMultipoleMethod.h.

## ◆ tree_construction_way() [2/2]

 void ogdf::energybased::fmmm::NewMultipoleMethod::tree_construction_way ( FMMMOptions::ReducedTreeConstruction rtc )
inlineprivate

Definition at line 383 of file NewMultipoleMethod.h.

## ◆ update_boxlength_and_cornercoordinate()

 void ogdf::energybased::fmmm::NewMultipoleMethod::update_boxlength_and_cornercoordinate ( double b_l, DPoint d_l_c )

Import updated information of the drawing area.

## ◆ well_separated()

private

If the small cell of ptr_1 and ptr_2 are well separated true is returned (else false).

## ◆ _find_small_cell

 FMMMOptions::SmallestCellFinding ogdf::energybased::fmmm::NewMultipoleMethod::_find_small_cell
private

Definition at line 80 of file NewMultipoleMethod.h.

## ◆ _particles_in_leaves

 int ogdf::energybased::fmmm::NewMultipoleMethod::_particles_in_leaves
private

max.

number of particles for leaves of the quadtree

Definition at line 81 of file NewMultipoleMethod.h.

## ◆ _precision

 int ogdf::energybased::fmmm::NewMultipoleMethod::_precision
private

precision for p-term multipole expansion

Definition at line 82 of file NewMultipoleMethod.h.

## ◆ _tree_construction_way

 FMMMOptions::ReducedTreeConstruction ogdf::energybased::fmmm::NewMultipoleMethod::_tree_construction_way
private

Definition at line 79 of file NewMultipoleMethod.h.

## ◆ BK

 double** ogdf::energybased::fmmm::NewMultipoleMethod::BK
private

holds the binomial coefficients

Definition at line 88 of file NewMultipoleMethod.h.

## ◆ boxlength

 double ogdf::energybased::fmmm::NewMultipoleMethod::boxlength
private

length of drawing box

Definition at line 84 of file NewMultipoleMethod.h.

## ◆ down_left_corner

 DPoint ogdf::energybased::fmmm::NewMultipoleMethod::down_left_corner
private

down left corner of drawing box

Definition at line 85 of file NewMultipoleMethod.h.

## ◆ ExactMethod

 FruchtermanReingold ogdf::energybased::fmmm::NewMultipoleMethod::ExactMethod
private

needed in case that using_NMM == false

Definition at line 77 of file NewMultipoleMethod.h.

## ◆ max_power_of_2_index

 const int ogdf::energybased::fmmm::NewMultipoleMethod::max_power_of_2_index
private

holds max.

index for power_of_2 (= 30)

Definition at line 87 of file NewMultipoleMethod.h.

## ◆ MIN_NODE_NUMBER

 int ogdf::energybased::fmmm::NewMultipoleMethod::MIN_NODE_NUMBER
private

The minimum number of nodes for which the forces are calculated using NMM (for lower values the exact calculation is used).

Definition at line 73 of file NewMultipoleMethod.h.

## ◆ rep_forces

 List ogdf::energybased::fmmm::NewMultipoleMethod::rep_forces
private

stores the rep. forces of the last iteration needed for error calculation)

Definition at line 92 of file NewMultipoleMethod.h.

## ◆ using_NMM

 bool ogdf::energybased::fmmm::NewMultipoleMethod::using_NMM
private

Indicates whether the exact method or NMM is used for force calculation (value depends on MIN_NODE_NUMBER)

Definition at line 76 of file NewMultipoleMethod.h.

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