1 /** \file 2 * \brief Declaration of class Multilevel (used by FMMMLayout). 3 * 4 * \author Stefan Hachul 5 * 6 * \par License: 7 * This file is part of the Open Graph Drawing Framework (OGDF). 8 * 9 * \par 10 * Copyright (C)<br> 11 * See README.md in the OGDF root directory for details. 12 * 13 * \par 14 * This program is free software; you can redistribute it and/or 15 * modify it under the terms of the GNU General Public License 16 * Version 2 or 3 as published by the Free Software Foundation; 17 * see the file LICENSE.txt included in the packaging of this file 18 * for details. 19 * 20 * \par 21 * This program is distributed in the hope that it will be useful, 22 * but WITHOUT ANY WARRANTY; without even the implied warranty of 23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 * GNU General Public License for more details. 25 * 26 * \par 27 * You should have received a copy of the GNU General Public 28 * License along with this program; if not, see 29 * http://www.gnu.org/copyleft/gpl.html 30 */ 31 32 #pragma once 33 34 #include <ogdf/basic/Graph.h> 35 #include <ogdf/basic/NodeArray.h> 36 #include <ogdf/basic/EdgeArray.h> 37 #include <ogdf/basic/List.h> 38 #include <ogdf/energybased/fmmm/multilevel/Edge.h> 39 #include <ogdf/energybased/fmmm/NodeAttributes.h> 40 #include <ogdf/energybased/fmmm/EdgeAttributes.h> 41 #include <ogdf/energybased/fmmm/FMMMOptions.h> 42 43 namespace ogdf { 44 namespace energybased { 45 namespace fmmm { 46 47 class Multilevel 48 { 49 public: 50 //! The multilevel representations *G_mult_ptr/*A_mult_ptr/*E_mult_ptr for 51 //! G/A/E are created. The maximum multilevel is calculated, too. 52 void create_multilevel_representations(Graph& G,NodeArray<NodeAttributes>& A, 53 EdgeArray <EdgeAttributes>& E, 54 int rand_seed, 55 FMMMOptions::GalaxyChoice galaxy_choice, 56 int min_Graph_size, 57 int rand_tries, 58 Array<Graph*> &G_mult_ptr, 59 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 60 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 61 int & max_level); 62 63 //! The initial placement of the nodes at multilevel level are created by the 64 //! placements of the nodes of the graphs at the lower level (if init_placement_way 65 //! is 0) or additionally using information of the actual level ( if 66 //! init_placement_way == 1). Precondition: level < max_level 67 void find_initial_placement_for_level( 68 int level, 69 FMMMOptions::InitialPlacementMult init_placement_way, 70 Array<Graph*> &G_mult_ptr, 71 Array<NodeArray <NodeAttributes>*> &A_mult_ptr, 72 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr); 73 74 //! Free dynamically allocated memory. 75 void delete_multilevel_representations( 76 Array<Graph*> &G_mult_ptr, 77 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 78 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 79 int max_level); 80 81 private: 82 83 //! This function returns true if act_level = 0 or if act_level >0 and the 84 //! number of edges at the actual level is <= 80% of the number of edges of the 85 //! previous level or if the actual edgenumber is >80% of the number of edges of the 86 //! previous level, but bad_edgecounter is <= 5. In this case edgecounter is 87 //! incremented. In all other cases false is returned. 88 bool edgenumbersum_of_all_levels_is_linear( 89 Array<Graph*> &G_mult_ptr, 90 int act_level, 91 int&bad_edgenr_counter); 92 93 //! Sets the default multilevel values for all nodes and edges in G_mult 94 void init_multilevel_values(const Graph &G_mult, 95 NodeArray<NodeAttributes> &A_mult, 96 EdgeArray<EdgeAttributes> &E_mult); 97 98 //! The nodeset(galaxy) of *G_mult_ptr[act_level] is partitioned in s,p,pm,m nodes. 99 //! The dedicated s,p,pm,m nodes define a subgraph (called solar system). 100 //! For each solar system a new node is created in *G_mult_ptr[act_level+1] and 101 //! it is linked with the corresponding sun node at act_level; the mass of this node 102 //! is set to the mass of the solar system. Additionally for each node in *G_mult_ptr 103 //! [act_level] the dedicated sun node and the distance to its dedicates sun node is 104 //! calculated 105 void partition_galaxy_into_solar_systems( 106 Array<Graph*> &G_mult_ptr, 107 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 108 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 109 int rand_seed, 110 FMMMOptions::GalaxyChoice galaxy_choice, 111 int random_tries, 112 int act_level); 113 114 //! The sun and planet nodes are created by choosing the sun nodes randomly with 115 //! uniform or weighted probability (depending on galaxy_choice) 116 void create_suns_and_planets( 117 Array<Graph*> &G_mult_ptr, 118 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 119 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 120 int rand_seed, 121 FMMMOptions::GalaxyChoice galaxy_choice, 122 int random_tries, 123 int act_level); 124 125 //! Partitions the nodes of G_mult that have not been assigned yet, 126 //! to moon nodes of a nearest planet or pm node and identify this planet as a 127 //! pm-node if this has not been done before. 128 void create_moon_nodes_and_pm_nodes(const Graph &G_mult, 129 NodeArray<NodeAttributes> &A_mult, 130 EdgeArray<EdgeAttributes> &E_mult); 131 132 //! Using information generated in partition_galaxy_into_solar_systems we 133 //! create the edge set of *G_mult_ptr[act_level+1] and for each node at act_level+1 134 //! the list of sun nodes of neighbouring sun systems and the corresponding lambda 135 //! values. 136 void collaps_solar_systems( 137 Array<Graph*> &G_mult_ptr, 138 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 139 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 140 int act_level); 141 142 //! The mass of all nodes at level act_level+1 is set to the mass of its dedicated 143 //! solar_system at level act_level. 144 void calculate_mass_of_collapsed_nodes( 145 Array<Graph*> &G_mult_ptr, 146 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 147 int act_level); 148 149 //! The edges , new_edgelength and the lambda lists at level act_level+1 are created 150 //! (the graph may contain parallel edges afterwards). 151 void create_edges_edgedistances_and_lambda_Lists( 152 Array<Graph*> &G_mult_ptr, 153 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 154 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 155 EdgeArray<double>& new_edgelength, 156 int act_level); 157 158 //! Parallel edges at level act_level+1 are deleted and the edgelength of the 159 //! remaining edge is set to the average edgelength of all its parallel edges. 160 void delete_parallel_edges_and_update_edgelength( 161 Array<Graph*> &G_mult_ptr, 162 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 163 EdgeArray<double>& new_edgelength, 164 int act_level); 165 166 //! The initial positions of all sun_nodes at level level are set. 167 void set_initial_positions_of_sun_nodes( 168 int level, 169 Array<Graph*> &G_mult_ptr, 170 Array<NodeArray<NodeAttributes>*> &A_mult_ptr); 171 172 //! The initial positions of the planet/moon_nodes at level level are calculated here 173 //! and a list of all pm_nodes is returned. 174 void set_initial_positions_of_planet_and_moon_nodes( 175 int level, 176 FMMMOptions::InitialPlacementMult init_placement_way, 177 Array<Graph*> &G_mult_ptr, 178 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 179 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 180 List<node> &pm_nodes); 181 182 //! The values of angle_1 and angle_2 that restrict the area of the placement for 183 //! all nodes that are not adjacent to other solar systems are created for all nodes 184 //! at multilevel level. 185 void create_all_placement_sectors( 186 Array<Graph*> &G_mult_ptr, 187 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 188 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 189 int level); 190 191 //! The initial positions of the pm nodes are calculated by the position of the 192 //! dedicated sun and moon_nodes. 193 void set_initial_positions_of_pm_nodes( 194 int level, 195 FMMMOptions::InitialPlacementMult init_placement_way, 196 Array<NodeArray<NodeAttributes>*> &A_mult_ptr, 197 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr, 198 List<node>& pm_nodes); 199 200 //! Returns a random point with radius radius between angle_1 and angle_2. 201 DPoint create_random_pos(DPoint center, double radius, double angle_1, double angle_2); 202 203 //! Returns roughtly the position s +lambda*(t-s) + some random waggling. 204 DPoint get_waggled_inbetween_position(DPoint s, DPoint t, double lambda); 205 206 //! Returns the barycenter position of all points in L (the mass of all point is 207 //! regarded as equal). 208 DPoint get_barycenter_position(List<DPoint>& L); 209 210 //! Creates a waggled position on the line PQ, depending on dist_P and dist_Q 211 //! needed in case init_placement_way() == 1. 212 DPoint calculate_position(DPoint P,DPoint Q, double dist_P, double dist_Q); 213 }; 214 215 } 216 } 217 } 218