Open
Graph Drawing
Framework

  v.2007.11
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files
Search for: 

ogdf::NMM

ogdf::NMM Class Reference

#include <NMM.h>

List of all members.

Public Member Functions

 NMM ()
 ~NMM ()
void calculate_repulsive_forces (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
void make_initialisations (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep, double boxlength, DPoint down_left_corner, int particles_in_leaves, int precision, int tree_construction_way, int find_small_cell)
void deallocate_memory ()
void update_boxlength_and_cornercoordinate (double b_l, DPoint d_l_c)

Private Member Functions

void init_power_of_2_array (void)
void free_power_of_2_array ()
int power_of_two (int i)
int maxboxindex (int level)
void calculate_repulsive_forces_by_NMM (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
void calculate_repulsive_forces_by_exact_method (const Graph &G, NodeArray< NodeAttributes > &A, NodeArray< DPoint > &F_rep)
void build_up_red_quad_tree_path_by_path (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
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)
void build_up_root_node (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
void create_sorted_coordinate_Lists (const Graph &G, NodeArray< NodeAttributes > &A, List< ParticleInfo > &L_x, List< ParticleInfo > &L_y)
void decompose_subtreenode (QuadTreeNM &T, List< ParticleInfo > &act_x_List_copy, List< ParticleInfo > &act_y_List_copy, List< QuadTreeNodeNM * > &new_leaf_List)
void calculate_boundaries_of_act_node (QuadTreeNodeNM *act_ptr, double &x_min, double &x_max, double &y_min, double &y_max)
bool in_lt_quad (QuadTreeNodeNM *act_ptr, double x_min, double x_max, double y_min, double y_max)
bool in_rt_quad (QuadTreeNodeNM *act_ptr, double x_min, double x_max, double y_min, double y_max)
bool in_lb_quad (QuadTreeNodeNM *act_ptr, double x_min, double x_max, double y_min, double y_max)
bool in_rb_quad (QuadTreeNodeNM *act_ptr, double x_min, double x_max, double y_min, double y_max)
void split_in_x_direction (QuadTreeNodeNM *act_ptr, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_copy, List< ParticleInfo > *&L_x_left_ptr, List< ParticleInfo > *&L_y_left_ptr, List< ParticleInfo > *&L_x_right_ptr, List< ParticleInfo > *&L_y_right_ptr)
void split_in_y_direction (QuadTreeNodeNM *act_ptr, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_copy, List< ParticleInfo > *&L_x_bottom_ptr, List< ParticleInfo > *&L_y_bottom_ptr, List< ParticleInfo > *&L_x_top_ptr, List< ParticleInfo > *&L_y_top_ptr)
void x_delete_right_subLists (QuadTreeNodeNM *act_ptr, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_copy, 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)
void x_delete_left_subLists (QuadTreeNodeNM *act_ptr, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_copy, 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)
void y_delete_right_subLists (QuadTreeNodeNM *act_ptr, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_copy, 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)
void y_delete_left_subLists (QuadTreeNodeNM *act_ptr, List< ParticleInfo > &L_x_copy, List< ParticleInfo > &L_y_copy, 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)
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)
void y_move_left_subLists (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)
void y_move_right_subLists (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)
void build_up_sorted_subLists (List< ParticleInfo > &L_x_copy, List< ParticleInfo > &act_y_List_copy)
void build_up_red_quad_tree_subtree_by_subtree (const Graph &G, NodeArray< NodeAttributes > &A, QuadTreeNM &T)
void build_up_root_vertex (const Graph &G, QuadTreeNM &T)
void construct_subtree (NodeArray< NodeAttributes > &A, QuadTreeNM &T, QuadTreeNodeNM *subtree_root_ptr, List< QuadTreeNodeNM * > &new_subtree_root_List)
void construct_complete_subtree (QuadTreeNM &T, int subtree_depth, Array2D< QuadTreeNodeNM * > &leaf_ptr, int act_depth, int act_x_index, int act_y_index)
void set_contained_nodes_for_leaves (NodeArray< NodeAttributes > &A, QuadTreeNM &T, QuadTreeNodeNM *subtree_root_ptr, Array2D< QuadTreeNodeNM * > &leaf_ptr, int maxindex)
void set_particlenumber_in_subtree_entries (QuadTreeNM &T)
void construct_reduced_subtree (NodeArray< NodeAttributes > &A, QuadTreeNM &T, List< QuadTreeNodeNM * > &new_subtree_root_List)
void delete_empty_subtrees (QuadTreeNM &T)
bool check_and_delete_degenerated_node (QuadTreeNM &T)
void delete_sparse_subtree (QuadTreeNM &T, QuadTreeNodeNM *new_leaf_ptr)
void collect_contained_nodes (QuadTreeNM &T, QuadTreeNodeNM *new_leaf_ptr)
bool find_smallest_quad (NodeArray< NodeAttributes > &A, QuadTreeNM &T)
void find_small_cell_iteratively (QuadTreeNodeNM *act_ptr, double x_min, double x_max, double y_min, double y_max)
void find_small_cell_by_formula (QuadTreeNodeNM *act_ptr, double x_min, double x_max, double y_min, double y_max)
void delete_red_quad_tree_and_count_treenodes (QuadTreeNM &T)
void form_multipole_expansions (NodeArray< NodeAttributes > &A, QuadTreeNM &T, List< QuadTreeNodeNM * > &quad_tree_leaves)
void form_multipole_expansion_of_subtree (NodeArray< NodeAttributes > &A, QuadTreeNM &T, List< QuadTreeNodeNM * > &quad_tree_leaves)
void init_expansion_Lists (QuadTreeNodeNM *act_ptr)
void set_center (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *act_ptr)
void form_multipole_expansion_of_leaf_node (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *act_ptr)
void add_shifted_expansion_to_father_expansion (QuadTreeNodeNM *act_ptr)
void calculate_local_expansions_and_WSPRLS (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *act_node_ptr)
bool well_seperated (QuadTreeNodeNM *ptr_1, QuadTreeNodeNM *ptr_2)
bool bordering (QuadTreeNodeNM *ptr_1, QuadTreeNodeNM *ptr_2)
void add_shifted_local_exp_of_parent (QuadTreeNodeNM *node_ptr)
void add_local_expansion (QuadTreeNodeNM *ptr_1, QuadTreeNodeNM *ptr_2)
void add_local_expansion_of_leaf (NodeArray< NodeAttributes > &A, QuadTreeNodeNM *leaf_ptr, QuadTreeNodeNM *act_ptr)
void transform_local_exp_to_forces (NodeArray< NodeAttributes > &A, List< QuadTreeNodeNM * > &quad_tree_leaves, NodeArray< DPoint > &F_local_exp)
void transform_multipole_exp_to_forces (NodeArray< NodeAttributes > &A, List< QuadTreeNodeNM * > &quad_tree_leaves, NodeArray< DPoint > &F_multipole_exp)
void calculate_neighbourcell_forces (const Graph &G, NodeArray< NodeAttributes > &A, List< QuadTreeNodeNM * > &quad_tree_leaves, NodeArray< DPoint > &F_direct)
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)
double f_rep_scalar (double d)
void init_binko (int t)
void free_binko ()
double binko (int n, int k)
int tree_construction_way () const
void tree_construction_way (int a)
int find_sm_cell () const
void find_sm_cell (int a)
void particles_in_leaves (int b)
int particles_in_leaves () const
void precision (int p)
int precision () const

Private Attributes

int MIN_NODE_NUMBER
bool using_NMM
FruchtermanReingold ExactMethod
int _tree_construction_way
int _find_small_cell
int _particles_in_leaves
int _precision
double boxlength
DPoint down_left_corner
int * power_of_2
int max_power_of_2_index
double ** BK
List< DPoint > rep_forces

Detailed Description

Definition at line 72 of file NMM.h.

Constructor & Destructor Documentation

ogdf::NMM::NMM (  ) 

ogdf::NMM::~NMM (  ) 

Member Function Documentation

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

void ogdf::NMM::make_initialisations ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
NodeArray< DPoint > &  F_rep,
double  boxlength,
DPoint  down_left_corner,
int  particles_in_leaves,
int  precision,
int  tree_construction_way,
int  find_small_cell 
)

void ogdf::NMM::deallocate_memory (  ) 

void ogdf::NMM::update_boxlength_and_cornercoordinate ( double  b_l,
DPoint  d_l_c 
)

void ogdf::NMM::init_power_of_2_array ( void   )  [private]

void ogdf::NMM::free_power_of_2_array (  )  [private]

int ogdf::NMM::power_of_two ( int  i  )  [private]

int ogdf::NMM::maxboxindex ( int  level  )  [private]

void ogdf::NMM::calculate_repulsive_forces_by_NMM ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
NodeArray< DPoint > &  F_rep 
) [private]

void ogdf::NMM::calculate_repulsive_forces_by_exact_method ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
NodeArray< DPoint > &  F_rep 
) [private]

void ogdf::NMM::build_up_red_quad_tree_path_by_path ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T 
) [private]

void ogdf::NMM::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]

void ogdf::NMM::build_up_root_node ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T 
) [private]

void ogdf::NMM::create_sorted_coordinate_Lists ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
List< ParticleInfo > &  L_x,
List< ParticleInfo > &  L_y 
) [private]

void ogdf::NMM::decompose_subtreenode ( QuadTreeNM &  T,
List< ParticleInfo > &  act_x_List_copy,
List< ParticleInfo > &  act_y_List_copy,
List< QuadTreeNodeNM * > &  new_leaf_List 
) [private]

void ogdf::NMM::calculate_boundaries_of_act_node ( QuadTreeNodeNM *  act_ptr,
double &  x_min,
double &  x_max,
double &  y_min,
double &  y_max 
) [private]

bool ogdf::NMM::in_lt_quad ( QuadTreeNodeNM *  act_ptr,
double  x_min,
double  x_max,
double  y_min,
double  y_max 
) [private]

bool ogdf::NMM::in_rt_quad ( QuadTreeNodeNM *  act_ptr,
double  x_min,
double  x_max,
double  y_min,
double  y_max 
) [private]

bool ogdf::NMM::in_lb_quad ( QuadTreeNodeNM *  act_ptr,
double  x_min,
double  x_max,
double  y_min,
double  y_max 
) [private]

bool ogdf::NMM::in_rb_quad ( QuadTreeNodeNM *  act_ptr,
double  x_min,
double  x_max,
double  y_min,
double  y_max 
) [private]

void ogdf::NMM::split_in_x_direction ( QuadTreeNodeNM *  act_ptr,
List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  L_y_copy,
List< ParticleInfo > *&  L_x_left_ptr,
List< ParticleInfo > *&  L_y_left_ptr,
List< ParticleInfo > *&  L_x_right_ptr,
List< ParticleInfo > *&  L_y_right_ptr 
) [private]

void ogdf::NMM::split_in_y_direction ( QuadTreeNodeNM *  act_ptr,
List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  L_y_copy,
List< ParticleInfo > *&  L_x_bottom_ptr,
List< ParticleInfo > *&  L_y_bottom_ptr,
List< ParticleInfo > *&  L_x_top_ptr,
List< ParticleInfo > *&  L_y_top_ptr 
) [private]

void ogdf::NMM::x_delete_right_subLists ( QuadTreeNodeNM *  act_ptr,
List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  L_y_copy,
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 
) [private]

void ogdf::NMM::x_delete_left_subLists ( QuadTreeNodeNM *  act_ptr,
List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  L_y_copy,
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 
) [private]

void ogdf::NMM::y_delete_right_subLists ( QuadTreeNodeNM *  act_ptr,
List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  L_y_copy,
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 
) [private]

void ogdf::NMM::y_delete_left_subLists ( QuadTreeNodeNM *  act_ptr,
List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  L_y_copy,
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 
) [private]

void ogdf::NMM::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]

void ogdf::NMM::y_move_left_subLists ( 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 
) [private]

void ogdf::NMM::y_move_right_subLists ( 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 
) [private]

void ogdf::NMM::build_up_sorted_subLists ( List< ParticleInfo > &  L_x_copy,
List< ParticleInfo > &  act_y_List_copy 
) [private]

void ogdf::NMM::build_up_red_quad_tree_subtree_by_subtree ( const Graph &  G,
NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T 
) [private]

void ogdf::NMM::build_up_root_vertex ( const Graph &  G,
QuadTreeNM &  T 
) [private]

void ogdf::NMM::construct_subtree ( NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T,
QuadTreeNodeNM *  subtree_root_ptr,
List< QuadTreeNodeNM * > &  new_subtree_root_List 
) [private]

void ogdf::NMM::construct_complete_subtree ( QuadTreeNM &  T,
int  subtree_depth,
Array2D< QuadTreeNodeNM * > &  leaf_ptr,
int  act_depth,
int  act_x_index,
int  act_y_index 
) [private]

void ogdf::NMM::set_contained_nodes_for_leaves ( NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T,
QuadTreeNodeNM *  subtree_root_ptr,
Array2D< QuadTreeNodeNM * > &  leaf_ptr,
int  maxindex 
) [private]

void ogdf::NMM::set_particlenumber_in_subtree_entries ( QuadTreeNM &  T  )  [private]

void ogdf::NMM::construct_reduced_subtree ( NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T,
List< QuadTreeNodeNM * > &  new_subtree_root_List 
) [private]

void ogdf::NMM::delete_empty_subtrees ( QuadTreeNM &  T  )  [private]

bool ogdf::NMM::check_and_delete_degenerated_node ( QuadTreeNM &  T  )  [private]

void ogdf::NMM::delete_sparse_subtree ( QuadTreeNM &  T,
QuadTreeNodeNM *  new_leaf_ptr 
) [private]

void ogdf::NMM::collect_contained_nodes ( QuadTreeNM &  T,
QuadTreeNodeNM *  new_leaf_ptr 
) [private]

bool ogdf::NMM::find_smallest_quad ( NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T 
) [private]

void ogdf::NMM::find_small_cell_iteratively ( QuadTreeNodeNM *  act_ptr,
double  x_min,
double  x_max,
double  y_min,
double  y_max 
) [private]

void ogdf::NMM::find_small_cell_by_formula ( QuadTreeNodeNM *  act_ptr,
double  x_min,
double  x_max,
double  y_min,
double  y_max 
) [private]

void ogdf::NMM::delete_red_quad_tree_and_count_treenodes ( QuadTreeNM &  T  )  [private]

void ogdf::NMM::form_multipole_expansions ( NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T,
List< QuadTreeNodeNM * > &  quad_tree_leaves 
) [private]

void ogdf::NMM::form_multipole_expansion_of_subtree ( NodeArray< NodeAttributes > &  A,
QuadTreeNM &  T,
List< QuadTreeNodeNM * > &  quad_tree_leaves 
) [private]

void ogdf::NMM::init_expansion_Lists ( QuadTreeNodeNM *  act_ptr  )  [private]