/* * $Revision: 2559 $ * * last checkin: * $Author: gutwenger $ * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $ ***************************************************************/ /** \file * \brief Declaration of class Multlevel (used by FMMMLayout). * * \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_MULTILEVEL_H #define OGDF_MULTILEVEL_H #include "../basic/Graph.h" #include "../basic/NodeArray.h" #include "../basic/EdgeArray.h" #include "../basic/List.h" #include "Edge.h" #include "../internal/energybased/NodeAttributes.h" #include "../internal/energybased/EdgeAttributes.h" namespace ogdf { class Multilevel { public: Multilevel() { } //constructor ~Multilevel() { } //destructor //The multilevel representations *G_mult_ptr/*A_mult_ptr/*E_mult_ptr for //G/A/E are created. The maximum multilevel is calculated, too. void create_multilevel_representations(Graph& G,NodeArray& A, EdgeArray & E, int rand_seed, int galaxy_choice, int min_Graph_size, int rand_tries, Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int & max_level); //The initial placement of the nodes at multilevel level are created by the //placements of the nodes of the graphs at the lower level (if init_placement_way //is 0) or additionally using information of the actual level ( if //init_placement_way == 1). Precondition: level < max_level void find_initial_placement_for_level( int level, int init_placement_way, Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr); //Free dynamically allocated memory. void delete_multilevel_representations( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int max_level); private: //This function returns true if act_level = 0 or if act_level >0 and the //number of edges at the actual level is <= 80% of the number of edges of the //previous level or if the actual edgenumber is >80% of the number of edges of the //previous level, but bad_edgecounter is <= 5. In this case edgecounter is //incremented. In all other cases false is returned. bool edgenumbersum_of_all_levels_is_linear( Array &G_mult_ptr, int act_level, int&bad_edgenr_counter); //The multilevel values of *A_mult_ptr[level][v] are set to the default values //for all nodes v in *G_mult_ptr[level] void init_multilevel_values( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int level); //The nodeset(galaxy) of *G_mult_ptr[act_level] is partitioned in s,p,pm,m nodes. //The dedicated s,p,pm,m nodes define a subgraph (called solar system). //For each solar system a new node is created in *G_mult_ptr[act_level+1] and //it is linked with the corresponding sun node at act_level; the mass of this node //is set to the mass of the solar system. Additionally for each node in *G_mult_ptr //[act_level] the dedicated sun node and the distance to its dedicates sun node is //calculated void partition_galaxy_into_solar_systems( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int rand_seed, int galaxy_choice, int random_tries, int act_level); //The sun and planet nodes are created by choosing the sun nodes randomly with //uniform or weighted probability (depending on galaxy_choice) void create_suns_and_planets( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int rand_seed, int galaxy_choice, int random_tries, int act_level); //Partitions the nodes of *G_mult_ptr[act_level] that have not been assigned yet, //to moon nodes of a nearest planet or pm node and identify this planet as a //pm-node if this has not been done before. void create_moon_nodes_and_pm_nodes( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int act_level); //Using information generated in partition_galaxy_into_solar_systems we //create the edge set of *G_mult_ptr[act_level+1] and for each node at act_level+1 //the list of sun nodes of neighbouring sun systems and the corresponding lambda //values. void collaps_solar_systems( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int act_level); //The mass of all nodes at level act_level+1 is set to the mass of its dedicated //solar_system at level act_level. void calculate_mass_of_collapsed_nodes( Array &G_mult_ptr, Array*> &A_mult_ptr, int act_level); //The edges , new_edgelength and the lambda lists at level act_level+1 are created //(the graph may contain parallel edges afterwards). void create_edges_edgedistances_and_lambda_Lists( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, EdgeArray& new_edgelength, int act_level); //Parallel edges at level act_level+1 are deleted and the edgelength of the //remaining edge is set to the average edgelength of all its parallel edges. void delete_parallel_edges_and_update_edgelength( Array &G_mult_ptr, Array*> &E_mult_ptr, EdgeArray& new_edgelength, int act_level); //The initial positions of all sun_nodes at level level are set. void set_initial_positions_of_sun_nodes( int level, Array &G_mult_ptr, Array*> &A_mult_ptr); //The initial positions of the planet/moon_nodes at level level are calculated here //and a list of all pm_nodes is returned. void set_initial_positions_of_planet_and_moon_nodes( int level, int init_placement_way, Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, List &pm_nodes); //The values of angle_1 and angle_2 that restrict the area of the placement for //all nodes that are not adjacent to other solar systems are created for all nodes //at multilevel level. void create_all_placement_sectors( Array &G_mult_ptr, Array*> &A_mult_ptr, Array*> &E_mult_ptr, int level); //The initial positions of the pm nodes are calculated by the position of the //dedicated sun and moon_nodes. void set_initial_positions_of_pm_nodes( int level, int init_placement_way, Array*> &A_mult_ptr, Array*> &E_mult_ptr, List& pm_nodes); //Returns a random point with radius radius between angle_1 and angle_2. DPoint create_random_pos(DPoint center, double radius, double angle_1, double angle_2); //Returns roughtly the position s +lambda*(t-s) + some random waggling. DPoint get_waggled_inbetween_position(DPoint s, DPoint t, double lambda); //Returns the barycenter position of all points in L (the mass of all point is //regarded as equal). DPoint get_barycenter_position(List& L); //Creates a waggled position on the line PQ, depending on dist_P and dist_Q //needed in case init_placement_way() == 1. DPoint calculate_position(DPoint P,DPoint Q, double dist_P, double dist_Q); //Calculates the angle between PQ and PS in [0,2pi) double angle(DPoint& P, DPoint& Q, DPoint& R); }; }//namespace ogdf #endif