/*
* $Revision: 2564 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
***************************************************************/
/** \file
* \brief Declaration of class NMM (New Multipole Method).
*
* \author Stefan Hachul
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_NMM_H
#define OGDF_NMM_H
#include "../../basic/Graph.h"
#include "../..//basic/List.h"
#include "../..//basic/Array2D.h"
#include "../..//basic/geometry.h"
#include "NodeAttributes.h"
#include "EdgeAttributes.h"
#include "QuadTreeNM.h"
#include "ParticleInfo.h"
#include "FruchtermanReingold.h"
#include
namespace ogdf {
class OGDF_EXPORT NMM
{
public:
NMM(); //constructor
~NMM() { } //destructor
//Calculate rep. forces for each node.
void calculate_repulsive_forces(const Graph &G,
NodeArray& A,
NodeArray& F_rep);
//Make all initialisations that are needed for New Multipole Method (NMM)
void make_initialisations (const Graph &G,
double boxlength,
DPoint down_left_corner,
int particles_in_leaves,
int precision,
int tree_construction_way,
int find_small_cell);
//Dynamically allocated memory is freed here.
void deallocate_memory();
//Import updated information of the drawing area.
void update_boxlength_and_cornercoordinate(double b_l,DPoint d_l_c);
private:
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).
bool using_NMM; //Indicates whether the exact method or NMM is used for force
//calculation (value depends on MIN_NODE_NUMBER)
FruchtermanReingold ExactMethod; //needed in case that using_NMM == false
int _tree_construction_way;//1 = pathwise;2 = subtreewise
int _find_small_cell;//0 = iterative; 1= Aluru
int _particles_in_leaves;//max. number of particles for leaves of the quadtree
int _precision; //precision for p-term multipole expansion
double boxlength;//length of drawing box
DPoint down_left_corner;//down left corner of drawing box
int* power_of_2; //holds the powers of 2 (for speed reasons to calculate the
//maximal boxindex (index is from 0 to max_power_of_2_index)
int max_power_of_2_index;//holds max. index for power_of_2 (= 30)
double ** BK; //holds the binomial coefficients
List rep_forces; //stores the rep. forces of the last iteration
//(needed for error calculation)
//private helping functions
//The array power_of_2 is calculated for values from 0 to max_power_of_2_index
//which is set here to 30.
void init_power_of_2_array();
//The space of power_of_2 is freed.
void free_power_of_2_array();
//Returns power_of_2[i] for values <= max_power_of_2_index else it returns
//pow(2,i).
int power_of_two(int i);
//Returns the maximal index of a box in level i.
int maxboxindex (int level);
//Use NMM for force calculation (used for large Graphs (|V| > MIN_NODE_NUMBER)).
void calculate_repulsive_forces_by_NMM(const Graph &G, NodeArray
& A, NodeArray& 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_exact_method(const Graph &G,
NodeArray& A,
NodeArray& F_rep);
// *********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 build_up_red_quad_tree_path_by_path(const Graph& G,
NodeArray& A,
QuadTreeNM& T);
//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 NULL in both lists.
void make_copy_and_init_Lists(List& L_x_orig,
List& L_x_copy,
List& L_y_orig,
List& L_y_copy);
//The root node of T is constructed.
void build_up_root_node(const Graph& G,NodeArray& A, QuadTreeNM& T);
//The sorted and linked Lists L_x and L_y for the root node are created.
void create_sorted_coordinate_Lists(const Graph& G,NodeArray& A,
List& L_x, List& L_y);
//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 decompose_subtreenode(QuadTreeNM& T,
List& act_x_List_copy,
List& act_y_List_copy,
List& new_leaf_List);
//The extreme coordinates of the particles contained in *act_ptr are calculated.
void calculate_boundaries_of_act_node(QuadTreeNodeNM* act_ptr,
double& x_min,
double& x_max,
double& y_min,
double& y_max);
//Returns true if the rectangle defined by x_min,...,y_max lies within the
//left(right)_top(bottom) quad of the small cell of *act_ptr.
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);
//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.
void split_in_x_direction(
QuadTreeNodeNM* act_ptr,
List*& L_x_left_ptr,
List*& L_y_left_ptr,
List*& L_x_right_ptr,
List *& L_y_right_ptr);
//The Lists *act_ptr->get_x(y)_List_ptr() are split into two subLists containing
//the particles in the top /bottom half ...
void split_in_y_direction(
QuadTreeNodeNM* act_ptr,
List*& L_x_bottom_ptr,
List*& L_y_bottom_ptr,
List*& L_x_top_ptr,
List*& L_y_top_ptr);
//The Lists *L_x(y)_left_ptr are constructed from *act_ptr->get_x(y)_List_ptr()
//by deleting all elements right 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.
void x_delete_right_subLists(
QuadTreeNodeNM* act_ptr,
List*& L_x_left_ptr,
List *& L_y_left_ptr,
List*& L_x_right_ptr,
List *& L_y_right_ptr,
ListIterator last_left_item);
//Analogue as above.
void x_delete_left_subLists(
QuadTreeNodeNM* act_ptr,
List*& L_x_left_ptr,
List *& L_y_left_ptr,
List*& L_x_right_ptr,
List *& L_y_right_ptr,
ListIterator last_left_item);
//The Lists *L_x(y)_left_ptr are constructed from *act_ptr->get_x(y)_List_ptr()
//by deleting all elements right from last_left_item in *act_ptr->get_y_List_ptr()
//the ...
void y_delete_right_subLists(
QuadTreeNodeNM* act_ptr,
List*& L_x_left_ptr,
List*& L_y_left_ptr,
List*& L_x_right_ptr,
List *& L_y_right_ptr,
ListIterator last_left_item);
//Analogue as above.
void y_delete_left_subLists(
QuadTreeNodeNM* act_ptr,
List*& L_x_left_ptr,
List*& L_y_left_ptr,
List*& L_x_right_ptr,
List *& L_y_right_ptr,
ListIterator last_left_item);
//The Lists *L_x(y)_b_ptr and *L_x(y)_t_ptr are constructed from the Lists
// *L_x(y)_ptr.
void split_in_y_direction(
QuadTreeNodeNM* act_ptr,
List*& L_x_ptr,
List*& L_x_b_ptr,
List*& L_x_t_ptr,
List*& L_y_ptr,
List*& L_y_b_ptr,
List*& L_y_t_ptr);
//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
//to this List. the L_x(y)_right_ptr point to the reduced Lists L_x(y)_ptr
//afterwards.
void y_move_left_subLists(List*& L_x_ptr,
List*& L_x_b_ptr,
List*& L_x_t_ptr,
List*& L_y_ptr,
List *& L_y_b_ptr,
List*& L_y_t_ptr,
ListIterator last_left_item);
//Same as above but the elements that belong to *&L_x(y)_right_ptr are moved.
void y_move_right_subLists(List*& L_x_ptr,
List*& L_x_b_ptr,
List*& L_x_t_ptr,
List*&L_y_ptr,
List *& L_y_b_ptr,
List*& L_y_t_ptr,
ListIterator last_left_item);
//The sorted subLists, that can be accesssed by the entries in L_x(y)_copy->
//get_subList_ptr() are constructed.
void build_up_sorted_subLists(List& L_x_copy,
List& act_y_List_copy);
// ************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_red_quad_tree_subtree_by_subtree(const Graph& G,
NodeArray& A,
QuadTreeNM& T);
//The root node of T is constructed and contained_nodes is set to the list of
//all nodes of G.
void build_up_root_vertex(const Graph&G, QuadTreeNM& T);
//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_subtree(NodeArray& A,
QuadTreeNM& T,
QuadTreeNodeNM* subtree_root_ptr,
List& new_subtree_root_List);
//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 construct_complete_subtree(QuadTreeNM& T,
int subtree_depth,
Array2D& leaf_ptr,
int act_depth,
int act_x_index,
int act_y_index);
//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.
void set_contained_nodes_for_leaves(NodeArray& A,
QuadTreeNodeNM* subtree_root_ptr,
Array2D& leaf_ptr,
int maxindex);
//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 set_particlenumber_in_subtree_entries(QuadTreeNM& T);
//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.
void construct_reduced_subtree(NodeArray& A,
QuadTreeNM& T,
List& new_subtree_root_List);
//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.
void delete_empty_subtrees(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.
bool check_and_delete_degenerated_node(QuadTreeNM& T);
//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.
void delete_sparse_subtree(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
void collect_contained_nodes(QuadTreeNM& T, QuadTreeNodeNM* 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.
bool find_smallest_quad(NodeArray& A, QuadTreeNM& T);
// *********functions needed for subtree by subtree tree construction(end) ********
//Finds the small cell of the actual Node of T iteratively,and updates
//Sm_downleftcorner, Sm_boxlength, and level of *act_ptr.
void find_small_cell_iteratively(QuadTreeNodeNM* act_ptr,
double x_min,
double x_max,
double y_min,
double y_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_by_formula(QuadTreeNodeNM* act_ptr,
double x_min,
double x_max,
double y_min,
double y_max);
//The reduced quad tree is deleted; Furthermore the treenode_number is calculated.
void delete_red_quad_tree_and_count_treenodes(QuadTreeNM& T);
//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 form_multipole_expansions(NodeArray& A,
QuadTreeNM& T,
List& quad_tree_leaves);
//The multipole expansion List ME for the tree rooted at T.get_act_ptr() is
//recursively calculated.
void form_multipole_expansion_of_subtree(NodeArray& A,
QuadTreeNM& T,
List& quad_tree_leaves);
//The Lists ME and LE are both initialized to zero entries for *act_ptr.
void init_expansion_Lists(QuadTreeNodeNM* act_ptr);
//The center of the box of *act_ptr is initialized.
void set_center(QuadTreeNodeNM* act_ptr);
//Calculate List ME for *act_ptr Precondition: *act_ptr is a leaf.
void form_multipole_expansion_of_leaf_node(NodeArray& A,
QuadTreeNodeNM* act_ptr);
//Add the shifted ME Lists of *act_ptr to act_ptr->get_father_ptr() ; precondition
// *act_ptr has a father_node.
void add_shifted_expansion_to_father_expansion(QuadTreeNodeNM* act_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_local_expansions_and_WSPRLS(NodeArray&A,
QuadTreeNodeNM* act_node_ptr);
//If the small cell of ptr_1 and ptr_2 are well separated true is returned (else
//false).
bool well_separated(QuadTreeNodeNM* ptr_1, QuadTreeNodeNM* ptr_2);
//If ptr_1 and ptr_2 are nonequal and bordering true is returned; else false.
bool bordering(QuadTreeNodeNM* ptr_1, QuadTreeNodeNM* ptr_2);
//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.
void add_shifted_local_exp_of_parent(QuadTreeNodeNM* node_ptr);
//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.
void add_local_expansion(QuadTreeNodeNM* ptr_1, QuadTreeNodeNM* ptr_2);
//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_local_expansion_of_leaf(NodeArray&A,
QuadTreeNodeNM* leaf_ptr,
QuadTreeNodeNM* act_ptr);
//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_local_exp_to_forces(NodeArray &A,
List& quad_tree_leaves,
NodeArray& F_local_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.
void transform_multipole_exp_to_forces(NodeArray& A,
List& quad_tree_leaves,
NodeArray& F_multipole_exp);
//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_neighbourcell_forces(NodeArray& A,
List& quad_tree_leaves,
NodeArray& F_direct);
//Add repulsive force contributions for each node.
void add_rep_forces(const Graph& G,
NodeArray& F_direct,
NodeArray& F_multipole_exp,
NodeArray& F_local_exp,
NodeArray& F_rep);
//Returns the repulsing force_function_value of scalar d.
double f_rep_scalar (double d);
//Init BK -matrix for values n, k in 0 to t.
void init_binko(int t);
//Free space for BK.
void free_binko();
//Returns n over k.
double binko(int n, int k);
//The way to construct the reduced tree (0) = level by level (1) path by path
//(2) subtree by subtree
int tree_construction_way() const { return _tree_construction_way; }
void tree_construction_way(int a) {
_tree_construction_way = (((0<=a)&&(a<=2)) ? a : 0);
}
//(0) means that the smallest quadratic cell that surrounds a node of the
//quadtree is calculated iteratively in constant time (1) means that it is
//calculated by the formula of Aluru et al. in constant time
int find_sm_cell() const { return _find_small_cell; }
void find_sm_cell(int a) {
_find_small_cell = (((0<=a)&&(a<=1)) ? a : 0);
}
//Max. number of particles that are contained in a leaf of the red. quadtree.
void particles_in_leaves (int b) { _particles_in_leaves = ((b>= 1)? b : 1); }
int particles_in_leaves () const { return _particles_in_leaves; }
//The precision p for the p-term multipole expansions.
void precision (int p) { _precision = ((p >= 1 ) ? p : 1); }
int precision () const { return _precision; }
};
}//namespace ogdf
#endif