NewMultipoleMethod.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/geometry.h>
#include <ogdf/energybased/fmmm/FMMMOptions.h>
#include <ogdf/energybased/fmmm/FruchtermanReingold.h>
 
namespace ogdf::energybased::fmmm {
class NodeAttributes;
class ParticleInfo;
class QuadTreeNM;
class QuadTreeNodeNM;
} // namespace ogdf::energybased::fmmm
 
namespace ogdf {
template<class E>
class Array2D;
 
namespace energybased {
namespace fmmm {
 
class OGDF_EXPORT NewMultipoleMethod {
public:
    NewMultipoleMethod();
 
    void calculate_repulsive_forces(const Graph& G, NodeArray<NodeAttributes>& A,
            NodeArray<DPoint>& F_rep);
 
    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);
 
    void deallocate_memory();
 
    void update_boxlength_and_cornercoordinate(double b_l, DPoint d_l_c);
 
private:
    int MIN_NODE_NUMBER;
    bool using_NMM;
    FruchtermanReingold ExactMethod; 
 
    FMMMOptions::ReducedTreeConstruction _tree_construction_way;
    FMMMOptions::SmallestCellFinding _find_small_cell;
    int _particles_in_leaves; 
    int _precision; 
 
    double boxlength; 
    DPoint down_left_corner; 
 
    const int max_power_of_2_index; 
    double** BK; 
 
    List<DPoint> rep_forces;
 
    // private helping functions
 
    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, DPoint& min, DPoint& max);
 
    bool in_lt_quad(QuadTreeNodeNM* act_ptr, DPoint min, DPoint max);
    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);
 
    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);
 
    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 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);
 
    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,
            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, DPoint min, DPoint max);
 
    void find_small_cell_by_formula(QuadTreeNodeNM* act_ptr, DPoint min, DPoint max);
 
    void find_small_cell(QuadTreeNodeNM* act_ptr, DPoint min, DPoint max) {
        switch (find_sm_cell()) {
        case FMMMOptions::SmallestCellFinding::Iteratively:
            find_small_cell_iteratively(act_ptr, min, max);
            break;
        case FMMMOptions::SmallestCellFinding::Aluru:
            find_small_cell_by_formula(act_ptr, min, max);
            break;
        }
    }
 
    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(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_separated(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(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);
 
    void init_binko(int t);
 
    void free_binko();
 
    double binko(int n, int k);
 
    FMMMOptions::ReducedTreeConstruction tree_construction_way() const {
        return _tree_construction_way;
    }
 
    void tree_construction_way(FMMMOptions::ReducedTreeConstruction rtc) {
        _tree_construction_way = rtc;
    }
 
    FMMMOptions::SmallestCellFinding find_sm_cell() const { return _find_small_cell; }
 
    void find_sm_cell(FMMMOptions::SmallestCellFinding scf) { _find_small_cell = scf; }
 
    void particles_in_leaves(int b) { _particles_in_leaves = ((b >= 1) ? b : 1); }
 
    int particles_in_leaves() const { return _particles_in_leaves; }
 
    void precision(int p) { _precision = ((p >= 1) ? p : 1); }
 
    int precision() const { return _precision; }
};
 
}
}
}