Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::energybased::fmmm::NewMultipoleMethod Class Reference

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

Public Member Functions

 NewMultipoleMethod ()
 Constructor. More...
 
void calculate_repulsive_forces (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
 Calculate rep. forces for each node. More...
 
void deallocate_memory ()
 Dynamically allocated memory is freed here. More...
 
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) More...
 
void update_boxlength_and_cornercoordinate (double b_l, DPoint d_l_c)
 Import updated information of the drawing area. More...
 

Private Member Functions

void add_local_expansion (QuadTreeNodeNM *ptr_1, QuadTreeNodeNM *ptr_2)
 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. More...
 
void add_local_expansion_of_leaf (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *leaf_ptr, QuadTreeNodeNM *act_ptr)
 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. More...
 
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. More...
 
void add_shifted_expansion_to_father_expansion (QuadTreeNodeNM *act_ptr)
 Add the shifted ME Lists of *act_ptr to act_ptr->get_father_ptr() ; precondition *act_ptr has a father_node. More...
 
void add_shifted_local_exp_of_parent (QuadTreeNodeNM *node_ptr)
 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. More...
 
double binko (int n, int k)
 Returns n over k. More...
 
bool bordering (QuadTreeNodeNM *ptr_1, QuadTreeNodeNM *ptr_2)
 If ptr_1 and ptr_2 are nonequal and bordering true is returned; else false. More...
 
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. More...
 
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. More...
 
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). More...
 
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)). More...
 
void delete_red_quad_tree_and_count_treenodes (QuadTreeNM &T)
 The reduced quad tree is deleted; Furthermore the treenode_number is calculated. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
void form_multipole_expansion_of_subtree (NodeArray< NodeAttributes > &A, QuadTreeNM &T, List< QuadTreeNodeNM * > &quad_tree_leaves)
 The multipole expansion List ME for the tree rooted at T.get_act_ptr() is recursively calculated. More...
 
void form_multipole_expansions (NodeArray< NodeAttributes > &A, QuadTreeNM &T, List< QuadTreeNodeNM * > &quad_tree_leaves)
 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). More...
 
void free_binko ()
 Free space for BK. More...
 
void init_binko (int t)
 Init BK -matrix for values n, k in 0 to t. More...
 
void init_expansion_Lists (QuadTreeNodeNM *act_ptr)
 The Lists ME and LE are both initialized to zero entries for *act_ptr. More...
 
int maxboxindex (int level)
 Returns the maximal index of a box in level i. More...
 
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. More...
 
int power_of_two (int i)
 Returns power_of_2[i] for values <= max_power_of_2_index. More...
 
int precision () const
 
void precision (int p)
 The precision p for the p-term multipole expansions. More...
 
void set_center (QuadTreeNodeNM *act_ptr)
 The center of the box of *act_ptr is initialized. More...
 
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. More...
 
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. More...
 
FMMMOptions::ReducedTreeConstruction tree_construction_way () const
 Returns the way to construct the reduced tree. More...
 
void tree_construction_way (FMMMOptions::ReducedTreeConstruction rtc)
 
bool well_separated (QuadTreeNodeNM *ptr_1, QuadTreeNodeNM *ptr_2)
 If the small cell of ptr_1 and ptr_2 are well separated true is returned (else false). More...
 
Functions needed for path by path tree construction @{
void build_up_red_quad_tree_path_by_path (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
 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. More...
 
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. More...
 
void build_up_root_node (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
 The root node of T is constructed. More...
 
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. More...
 
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. More...
 
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. More...
 
bool in_lt_quad (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
 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. More...
 
bool in_rt_quad (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
 
bool in_lb_quad (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
 
bool in_rb_quad (QuadTreeNodeNM *act_ptr, DPoint min, DPoint max)
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
Functions needed for subtree by subtree tree construction
void build_up_red_quad_tree_subtree_by_subtree (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
 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. More...
 
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. More...
 
void construct_subtree (NodeArray< NodeAttributes > &A, QuadTreeNM &T, QuadTreeNodeNM *subtree_root_ptr, List< QuadTreeNodeNM * > &new_subtree_root_List)
 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. More...
 
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. More...
 
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. More...
 
void set_particlenumber_in_subtree_entries (QuadTreeNM &T)
 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. More...
 
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. More...
 
void delete_empty_subtrees (QuadTreeNM &T)
 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. More...
 
bool check_and_delete_degenerated_node (QuadTreeNM &T)
 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. More...
 
void delete_sparse_subtree (QuadTreeNM &T, QuadTreeNodeNM *new_leaf_ptr)
 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. More...
 
void collect_contained_nodes (QuadTreeNM &T, QuadTreeNodeNM *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 More...
 
bool find_smallest_quad (NodeArray< NodeAttributes > &A, QuadTreeNM &T)
 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. More...
 

Private Attributes

FMMMOptions::SmallestCellFinding _find_small_cell
 
int _particles_in_leaves
 max. More...
 
int _precision
 precision for p-term multipole expansion More...
 
FMMMOptions::ReducedTreeConstruction _tree_construction_way
 
double ** BK
 holds the binomial coefficients More...
 
double boxlength
 length of drawing box More...
 
DPoint down_left_corner
 down left corner of drawing box More...
 
FruchtermanReingold ExactMethod
 needed in case that using_NMM == false More...
 
const int max_power_of_2_index
 holds max. More...
 
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). More...
 
List< DPointrep_forces
 stores the rep. forces of the last iteration needed for error calculation) More...
 
bool using_NMM
 Indicates whether the exact method or NMM is used for force calculation (value depends on MIN_NODE_NUMBER) More...
 

Detailed Description

Definition at line 47 of file NewMultipoleMethod.h.

Constructor & Destructor Documentation

◆ NewMultipoleMethod()

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

Constructor.

Member Function Documentation

◆ add_local_expansion()

void ogdf::energybased::fmmm::NewMultipoleMethod::add_local_expansion ( QuadTreeNodeNM ptr_1,
QuadTreeNodeNM ptr_2 
)
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.

◆ add_local_expansion_of_leaf()

void ogdf::energybased::fmmm::NewMultipoleMethod::add_local_expansion_of_leaf ( NodeArray< NodeAttributes > &  A,
QuadTreeNodeNM leaf_ptr,
QuadTreeNodeNM act_ptr 
)
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.

◆ add_rep_forces()

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.

◆ add_shifted_expansion_to_father_expansion()

void ogdf::energybased::fmmm::NewMultipoleMethod::add_shifted_expansion_to_father_expansion ( QuadTreeNodeNM act_ptr)
private

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

◆ add_shifted_local_exp_of_parent()

void ogdf::energybased::fmmm::NewMultipoleMethod::add_shifted_local_exp_of_parent ( QuadTreeNodeNM node_ptr)
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()

bool ogdf::energybased::fmmm::NewMultipoleMethod::bordering ( QuadTreeNodeNM ptr_1,
QuadTreeNodeNM ptr_2 
)
private

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

◆ build_up_red_quad_tree_path_by_path()

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.

◆ build_up_red_quad_tree_subtree_by_subtree()

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()

void ogdf::energybased::fmmm::NewMultipoleMethod::collect_contained_nodes ( QuadTreeNM T,
QuadTreeNodeNM new_leaf_ptr 
)
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.

◆ delete_red_quad_tree_and_count_treenodes()

void ogdf::energybased::fmmm::NewMultipoleMethod::delete_red_quad_tree_and_count_treenodes ( QuadTreeNM T)
private

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

◆ delete_sparse_subtree()

void ogdf::energybased::fmmm::NewMultipoleMethod::delete_sparse_subtree ( QuadTreeNM T,
QuadTreeNodeNM new_leaf_ptr 
)
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 433 of file NewMultipoleMethod.h.

◆ find_sm_cell() [2/2]

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

Definition at line 435 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 322 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.

◆ find_smallest_quad()

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.

◆ in_lb_quad()

bool ogdf::energybased::fmmm::NewMultipoleMethod::in_lb_quad ( QuadTreeNodeNM act_ptr,
DPoint  min,
DPoint  max 
)
private

◆ in_lt_quad()

bool ogdf::energybased::fmmm::NewMultipoleMethod::in_lt_quad ( QuadTreeNodeNM act_ptr,
DPoint  min,
DPoint  max 
)
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.

◆ in_rb_quad()

bool ogdf::energybased::fmmm::NewMultipoleMethod::in_rb_quad ( QuadTreeNodeNM act_ptr,
DPoint  min,
DPoint  max 
)
private

◆ in_rt_quad()

bool ogdf::energybased::fmmm::NewMultipoleMethod::in_rt_quad ( QuadTreeNodeNM act_ptr,
DPoint  min,
DPoint  max 
)
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 441 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 440 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 445 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 444 of file NewMultipoleMethod.h.

◆ quadHelper()

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 425 of file NewMultipoleMethod.h.

◆ tree_construction_way() [2/2]

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

Definition at line 427 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()

bool ogdf::energybased::fmmm::NewMultipoleMethod::well_separated ( QuadTreeNodeNM ptr_1,
QuadTreeNodeNM ptr_2 
)
private

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

Member Data Documentation

◆ _find_small_cell

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

Definition at line 84 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 85 of file NewMultipoleMethod.h.

◆ _precision

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

precision for p-term multipole expansion

Definition at line 86 of file NewMultipoleMethod.h.

◆ _tree_construction_way

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

Definition at line 83 of file NewMultipoleMethod.h.

◆ BK

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

holds the binomial coefficients

Definition at line 92 of file NewMultipoleMethod.h.

◆ boxlength

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

length of drawing box

Definition at line 88 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 89 of file NewMultipoleMethod.h.

◆ ExactMethod

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

needed in case that using_NMM == false

Definition at line 81 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 91 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 77 of file NewMultipoleMethod.h.

◆ rep_forces

List<DPoint> ogdf::energybased::fmmm::NewMultipoleMethod::rep_forces
private

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

Definition at line 96 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 80 of file NewMultipoleMethod.h.


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