?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Drop unused resource strings
[TortoiseGit.git] / ext / OGDF / src / energybased / Multilevel.cpp
blobd02424ead370b0da76bb0f763d3982605aac3569
1 /*
2 * $Revision: 2552 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of class Multlevel (used by FMMMLayout).
11 *
12 * \author Stefan Hachul
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
42
43
44 #include "Multilevel.h"
45 #include "Set.h"
46 #include "Node.h"
47 #include <ogdf/basic/Array.h>
48 #include <ogdf/basic/Math.h>
49 #include <ogdf/basic/simple_graph_alg.h>
50 #include <ogdf/energybased/FMMMLayout.h>
51
52
53 namespace ogdf {
54
55 void Multilevel::create_multilevel_representations(
56 Graph& G,
57 NodeArray<NodeAttributes>& A,
58 EdgeArray<EdgeAttributes>& E,
59 int rand_seed,
60 int galaxy_choice,
61 int min_Graph_size,
62 int random_tries,
63 Array<Graph*> &G_mult_ptr,
64 Array<NodeArray <NodeAttributes>*> &A_mult_ptr,
65 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
66 int & max_level)
67 {
68 //make initialisations;
69 srand(rand_seed);
70 G_mult_ptr[0] = &G; //init graph at level 0 to the original undirected simple
71 A_mult_ptr[0] = &A; //and loopfree connected graph G/A/E
72 E_mult_ptr[0] = &E;
73
74 int bad_edgenr_counter = 0;
75 int act_level = 0;
76 Graph* act_Graph_ptr = G_mult_ptr[0];
77
78 while( (act_Graph_ptr->numberOfNodes() > min_Graph_size) &&
79 edgenumbersum_of_all_levels_is_linear(G_mult_ptr,act_level,bad_edgenr_counter) )
80 {
81 Graph* G_new = new (Graph);
82 NodeArray<NodeAttributes>* A_new = OGDF_NEW NodeArray<NodeAttributes>;
83 EdgeArray<EdgeAttributes>* E_new = OGDF_NEW EdgeArray<EdgeAttributes>;
84 G_mult_ptr[act_level+1] = G_new;
85 A_mult_ptr[act_level+1] = A_new;
86 E_mult_ptr[act_level+1] = E_new;
87
88 init_multilevel_values(G_mult_ptr,A_mult_ptr,E_mult_ptr,act_level);
89 partition_galaxy_into_solar_systems(G_mult_ptr,A_mult_ptr,E_mult_ptr,rand_seed,
90 galaxy_choice,random_tries,act_level);
91 collaps_solar_systems(G_mult_ptr,A_mult_ptr,E_mult_ptr,act_level);
92
93 act_level++;
94 act_Graph_ptr = G_mult_ptr[act_level];
95 }
96 max_level = act_level;
97 }
98
99
100 bool Multilevel::edgenumbersum_of_all_levels_is_linear(
101 Array<Graph*> &G_mult_ptr,
102 int act_level,
103 int& bad_edgenr_counter)
104 {
105 if(act_level == 0)
106 return true;
107 else
108 {
109 if(G_mult_ptr[act_level]->numberOfEdges()<=
110 0.8 * double (G_mult_ptr[act_level-1]->numberOfEdges()))
111 return true;
112 else if(bad_edgenr_counter < 5)
113 {
114 bad_edgenr_counter++;
115 return true;
116 }
117 else
118 return false;
119 }
120 }
121
122
123 inline void Multilevel::init_multilevel_values(
124 Array<Graph*> &G_mult_ptr,
125 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
126 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
127 int level)
128 {
129 node v;
130 forall_nodes(v,*G_mult_ptr[level])
131 (*A_mult_ptr[level])[v].init_mult_values();
132
133 edge e;
134 forall_edges(e,*G_mult_ptr[level])
135 (*E_mult_ptr[level])[e].init_mult_values();
136 }
137
138
139 inline void Multilevel::partition_galaxy_into_solar_systems(
140 Array<Graph*> &G_mult_ptr,
141 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
142 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
143 int rand_seed,
144 int galaxy_choice,
145 int random_tries,
146 int act_level)
147 {
148 create_suns_and_planets(G_mult_ptr, A_mult_ptr, E_mult_ptr, rand_seed, galaxy_choice,
149 random_tries, act_level);
150 create_moon_nodes_and_pm_nodes(G_mult_ptr, A_mult_ptr, E_mult_ptr, act_level);
151 }
152
153
154 void Multilevel::create_suns_and_planets(
155 Array<Graph*> &G_mult_ptr,
156 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
157 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
158 int rand_seed,
159 int galaxy_choice,
160 int random_tries,
161 int act_level)
162 {
163 Set Node_Set;
164 node v, sun_node, planet_node, newNode, pos_moon_node;
165 edge sun_edge, e;
166 double dist_to_sun;
167 List<node> planet_nodes;
168 List<node> sun_nodes;
169
170 //make initialisations
171 sun_nodes.clear();
172 Node_Set.set_seed(rand_seed); //set seed for random number generator
173 forall_nodes(v,*G_mult_ptr[act_level])
174 if(act_level == 0) (*A_mult_ptr[act_level])[v].set_mass(1);
175 if(galaxy_choice == FMMMLayout::gcUniformProb)
176 Node_Set.init_node_set(*G_mult_ptr[act_level]);
177 else //galaxy_choice != gcUniformProb in FMMMLayout
178 Node_Set.init_node_set(*G_mult_ptr[act_level],*A_mult_ptr[act_level]);
179
180
181 while (!Node_Set.empty_node_set())
182 {//while
183 //randomly select a sun node
184 planet_nodes.clear();
185 if(galaxy_choice == FMMMLayout::gcUniformProb)
186 sun_node = Node_Set.get_random_node();
187 else if (galaxy_choice == FMMMLayout::gcNonUniformProbLowerMass)
188 sun_node = Node_Set.get_random_node_with_lowest_star_mass(random_tries);
189 else //galaxy_choice == FMMMLayout::gcNonUniformProbHigherMass
190 sun_node = Node_Set.get_random_node_with_highest_star_mass(random_tries);
191 sun_nodes.pushBack(sun_node);
192
193 //create new node at higher level that represents the collapsed solar_system
194 newNode = G_mult_ptr[act_level+1]->newNode();
195
196 //update information for sun_node
197 (*A_mult_ptr[act_level])[sun_node].set_higher_level_node(newNode);
198 (*A_mult_ptr[act_level])[sun_node].set_type(1);
199 (*A_mult_ptr[act_level])[sun_node].set_dedicated_sun_node(sun_node);
200 (*A_mult_ptr[act_level])[sun_node].set_dedicated_sun_distance(0);
201
202 //update information for planet_nodes
203 forall_adj_edges(sun_edge,sun_node)
204 {
205 dist_to_sun = (*E_mult_ptr[act_level])[sun_edge].get_length();
206 if (sun_edge->source() != sun_node)
207 planet_node = sun_edge->source();
208 else
209 planet_node = sun_edge->target();
210 (*A_mult_ptr[act_level])[planet_node].set_type(2);
211 (*A_mult_ptr[act_level])[planet_node].set_dedicated_sun_node(sun_node);
212 (*A_mult_ptr[act_level])[planet_node].set_dedicated_sun_distance(dist_to_sun);
213 planet_nodes.pushBack(planet_node);
214 }
215
216 //delete all planet_nodes and possible_moon_nodes from Node_Set
217
218 ListConstIterator<node> planet_node_ptr;
219 //forall_listiterators(node,planet_node_ptr,planet_nodes)
220 for(planet_node_ptr = planet_nodes.begin(); planet_node_ptr.valid(); ++planet_node_ptr)
221 if(!Node_Set.is_deleted(*planet_node_ptr))
222 Node_Set.delete_node(*planet_node_ptr);
223
224 for(planet_node_ptr = planet_nodes.begin(); planet_node_ptr.valid(); ++planet_node_ptr)
225 //forall_listiterators(node,planet_node_ptr,planet_nodes)
226 {
227 forall_adj_edges(e,*planet_node_ptr)
228 {
229 if(e->source() == *planet_node_ptr)
230 pos_moon_node = e->target();
231 else
232 pos_moon_node = e->source();
233 if(!Node_Set.is_deleted(pos_moon_node))
234 Node_Set.delete_node(pos_moon_node);
235 }
236 }
237 }//while
238
239 //init *A_mult_ptr[act_level+1] and set NodeAttributes information for new nodes
240 A_mult_ptr[act_level+1]->init(*G_mult_ptr[act_level+1]);
241 forall_listiterators(node, sun_node_ptr, sun_nodes)
242 {
243 newNode = (*A_mult_ptr[act_level])[*sun_node_ptr].get_higher_level_node();
244 (*A_mult_ptr[act_level+1])[newNode].set_NodeAttributes((*A_mult_ptr[act_level])
245 [*sun_node_ptr].get_width(),
246 (*A_mult_ptr[act_level])
247 [*sun_node_ptr].get_height(),
248 (*A_mult_ptr[act_level])
249 [*sun_node_ptr].get_position(),
250 *sun_node_ptr,NULL);
251 (*A_mult_ptr[act_level+1])[newNode].set_mass(0);
252 }
253 }
254
255
256 void Multilevel::create_moon_nodes_and_pm_nodes(
257 Array<Graph*> &G_mult_ptr,
258 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
259 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
260 int act_level)
261 {
262 edge e;
263 node v, nearest_neighbour_node, neighbour_node, dedicated_sun_node;
264 double dist_to_nearest_neighbour, dedicated_sun_distance;
265 bool first_adj_edge;
266 int neighbour_type;
267 edge moon_edge;
268
269 forall_nodes(v,*G_mult_ptr[act_level])
270 if((*A_mult_ptr[act_level])[v].get_type() == 0) //a moon node
271 {//forall
272 //find nearest neighbour node
273 first_adj_edge = true;
274 forall_adj_edges(e,v)
275 {//forall2
276 if(v == e->source())
277 neighbour_node = e->target();
278 else
279 neighbour_node = e->source();
280 neighbour_type = (*A_mult_ptr[act_level])[neighbour_node].get_type();
281 if( (neighbour_type == 2) || (neighbour_type == 3) )
282 {//if_1
283 if(first_adj_edge)
284 {//if
285 first_adj_edge = false;
286 moon_edge = e;
287 dist_to_nearest_neighbour = (*E_mult_ptr[act_level])[e].get_length();
288 nearest_neighbour_node = neighbour_node;
289 }//if
290 else if(dist_to_nearest_neighbour >(*E_mult_ptr[act_level])[e].get_length())
291 {//else
292 moon_edge = e;
293 dist_to_nearest_neighbour = (*E_mult_ptr[act_level])[e].get_length();
294 nearest_neighbour_node = neighbour_node;
295 }//else
296 }//if_1
297 }//forall2
298 //find dedic. solar system for v and update information in *A_mult_ptr[act_level]
299 //and *E_mult_ptr[act_level]
300
301 (*E_mult_ptr[act_level])[moon_edge].make_moon_edge(); //mark this edge
302 dedicated_sun_node = (*A_mult_ptr[act_level])[nearest_neighbour_node].
303 get_dedicated_sun_node();
304 dedicated_sun_distance = dist_to_nearest_neighbour + (*A_mult_ptr[act_level])
305 [nearest_neighbour_node].get_dedicated_sun_distance();
306 (*A_mult_ptr[act_level])[v].set_type(4);
307 (*A_mult_ptr[act_level])[v].set_dedicated_sun_node(dedicated_sun_node);
308 (*A_mult_ptr[act_level])[v].set_dedicated_sun_distance(dedicated_sun_distance);
309 (*A_mult_ptr[act_level])[v].set_dedicated_pm_node(nearest_neighbour_node);
310
311 //identify nearest_neighbour_node as a pm_node and update its information
312
313 (*A_mult_ptr[act_level])[nearest_neighbour_node].set_type(3);
314 (*A_mult_ptr[act_level])[nearest_neighbour_node].
315 get_dedicated_moon_node_List_ptr()->pushBack(v);
316 }//forall
317 }
318
319
320 inline void Multilevel::collaps_solar_systems(
321 Array<Graph*> &G_mult_ptr,
322 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
323 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
324 int act_level)
325 {
326 EdgeArray<double> new_edgelength;
327 calculate_mass_of_collapsed_nodes(G_mult_ptr, A_mult_ptr, act_level);
328 create_edges_edgedistances_and_lambda_Lists(G_mult_ptr, A_mult_ptr, E_mult_ptr,
329 new_edgelength, act_level);
330 delete_parallel_edges_and_update_edgelength(G_mult_ptr, E_mult_ptr, new_edgelength,
331 act_level);
332 }
333
334
335 inline void Multilevel::calculate_mass_of_collapsed_nodes(
336 Array<Graph*> &G_mult_ptr,
337 Array<NodeArray <NodeAttributes>*> &A_mult_ptr,
338 int act_level)
339 {
340 node v;
341 node dedicated_sun,high_level_node;
342
343 forall_nodes(v,*G_mult_ptr[act_level])
344 {
345 dedicated_sun = (*A_mult_ptr[act_level])[v].get_dedicated_sun_node();
346 high_level_node = (*A_mult_ptr[act_level])[dedicated_sun].get_higher_level_node();
347 (*A_mult_ptr[act_level+1])[high_level_node].set_mass((*A_mult_ptr[act_level+1])
348 [high_level_node].get_mass()+1);
349 }
350 }
351
352
353 void Multilevel::create_edges_edgedistances_and_lambda_Lists(
354 Array<Graph*> &G_mult_ptr,
355 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
356 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
357 EdgeArray<double>& new_edgelength,int
358 act_level)
359 {
360 edge e, e_new;
361 node s_node, t_node;
362 node s_sun_node, t_sun_node;
363 node high_level_sun_s, high_level_sun_t;
364 double length_e, length_s_edge, length_t_edge, newlength;
365 double lambda_s, lambda_t;
366 List<edge> inter_solar_system_edges;
367
368 //create new edges at act_level+1 and create for each inter solar system edge at
369 //act_level a link to its corresponding edge
370
371 forall_edges(e,*G_mult_ptr[act_level])
372 {//forall
373 s_node = e->source();
374 t_node = e->target();
375 s_sun_node = (*A_mult_ptr[act_level])[s_node].get_dedicated_sun_node();
376 t_sun_node = (*A_mult_ptr[act_level])[t_node].get_dedicated_sun_node();
377 if( s_sun_node != t_sun_node) //a inter solar system edge
378 {//if
379 high_level_sun_s = (*A_mult_ptr[act_level])[s_sun_node].get_higher_level_node();
380 high_level_sun_t = (*A_mult_ptr[act_level])[t_sun_node].get_higher_level_node();
381
382 //create new edge in *G_mult_ptr[act_level+1]
383 e_new = G_mult_ptr[act_level+1]->newEdge(high_level_sun_s,high_level_sun_t);
384 (*E_mult_ptr[act_level])[e].set_higher_level_edge(e_new);
385 inter_solar_system_edges.pushBack(e);
386 }//if
387 }//forall
388
389 //init new_edgelength calculate the values of new_edgelength and the lambda Lists
390
391 new_edgelength.init(*G_mult_ptr[act_level+1]);
392 forall_listiterators(edge, e_ptr, inter_solar_system_edges)
393 {//forall
394 s_node = (*e_ptr)->source();
395 t_node = (*e_ptr)->target();
396 s_sun_node = (*A_mult_ptr[act_level])[s_node].get_dedicated_sun_node();
397 t_sun_node = (*A_mult_ptr[act_level])[t_node].get_dedicated_sun_node();
398 length_e = (*E_mult_ptr[act_level])[*e_ptr].get_length();
399 length_s_edge =(*A_mult_ptr[act_level])[s_node].get_dedicated_sun_distance();
400 length_t_edge =(*A_mult_ptr[act_level])[t_node].get_dedicated_sun_distance();
401 newlength = length_s_edge + length_e + length_t_edge;
402
403 //set new edge_length in *G_mult_ptr[act_level+1]
404 e_new = (*E_mult_ptr[act_level])[*e_ptr].get_higher_level_edge();
405 new_edgelength[e_new] = newlength;
406
407 //create entries in lambda Lists
408 lambda_s = length_s_edge/newlength;
409 lambda_t = length_t_edge/newlength;
410 (*A_mult_ptr[act_level])[s_node].get_lambda_List_ptr()->pushBack(lambda_s);
411 (*A_mult_ptr[act_level])[t_node].get_lambda_List_ptr()->pushBack(lambda_t);
412 (*A_mult_ptr[act_level])[s_node].get_neighbour_sun_node_List_ptr()->pushBack(
413 t_sun_node);
414 (*A_mult_ptr[act_level])[t_node].get_neighbour_sun_node_List_ptr()->pushBack(
415 s_sun_node);
416 }//forall
417 }
418
419
420 void Multilevel::delete_parallel_edges_and_update_edgelength(
421 Array<Graph*> &G_mult_ptr,
422 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
423 EdgeArray<double>& new_edgelength,int
424 act_level)
425 {
426 EdgeMaxBucketFunc get_max_index;
427 EdgeMinBucketFunc get_min_index;
428 edge e_act, e_save;
429 Edge f_act;
430 List<Edge> sorted_edges;
431 Graph* Graph_ptr = G_mult_ptr[act_level+1];
432 int save_s_index,save_t_index,act_s_index,act_t_index;
433 int counter = 1;
434
435 //make *G_mult_ptr[act_level+1] undirected
436 makeSimpleUndirected(*G_mult_ptr[act_level+1]);
437
438 //sort the List sorted_edges
439 forall_edges(e_act,*Graph_ptr)
440 {
441 f_act.set_Edge(e_act,Graph_ptr);
442 sorted_edges.pushBack(f_act);
443 }
444
445 sorted_edges.bucketSort(0,Graph_ptr->numberOfNodes()-1,get_max_index);
446 sorted_edges.bucketSort(0,Graph_ptr->numberOfNodes()-1,get_min_index);
447
448 //now parallel edges are consecutive in sorted_edges
449 forall_listiterators(Edge, EdgeIterator,sorted_edges)
450 {//for
451 e_act = (*EdgeIterator).get_edge();
452 act_s_index = e_act->source()->index();
453 act_t_index = e_act->target()->index();
454
455 if(EdgeIterator != sorted_edges.begin())
456 {//if
457 if( (act_s_index == save_s_index && act_t_index == save_t_index) ||
458 (act_s_index == save_t_index && act_t_index == save_s_index) )
459 {
460 new_edgelength[e_save] += new_edgelength[e_act];
461 Graph_ptr->delEdge(e_act);
462 counter++;
463 }
464 else
465 {
466 if (counter > 1)
467 {
468 new_edgelength[e_save] /= counter;
469 counter = 1;
470 }
471 save_s_index = act_s_index;
472 save_t_index = act_t_index;
473 e_save = e_act;
474 }
475 }//if
476 else //first edge
477 {
478 save_s_index = act_s_index;
479 save_t_index = act_t_index;
480 e_save = e_act;
481 }
482 }//for
483
484 //treat special case (last edges were multiple edges)
485 if(counter >1)
486 new_edgelength[e_save] /= counter;
487
488 //init *E_mult_ptr[act_level+1] and import EdgeAttributes
489 E_mult_ptr[act_level+1]->init(*G_mult_ptr[act_level+1]);
490 forall_edges(e_act,*Graph_ptr)
491 (*E_mult_ptr[act_level+1])[e_act].set_length(new_edgelength[e_act]);
492 }
493
494
495 void Multilevel::find_initial_placement_for_level(
496 int level,
497 int init_placement_way,
498 Array<Graph*> &G_mult_ptr,
499 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
500 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr)
501 {
502 List<node> pm_nodes;
503 set_initial_positions_of_sun_nodes(level, G_mult_ptr, A_mult_ptr);
504 set_initial_positions_of_planet_and_moon_nodes(level, init_placement_way, G_mult_ptr,
505 A_mult_ptr, E_mult_ptr, pm_nodes);
506 set_initial_positions_of_pm_nodes(level, init_placement_way, A_mult_ptr,
507 E_mult_ptr, pm_nodes);
508 }
509
510
511 void Multilevel::set_initial_positions_of_sun_nodes(
512 int level,
513 Array<Graph*> &G_mult_ptr,
514 Array<NodeArray <NodeAttributes>*> &A_mult_ptr)
515 {
516 node v_high, v_act;
517 DPoint new_pos;
518 forall_nodes(v_high,*G_mult_ptr[level+1])
519 {
520 v_act = (*A_mult_ptr[level+1])[v_high].get_lower_level_node();
521 new_pos = (*A_mult_ptr[level+1])[v_high].get_position();
522 (*A_mult_ptr[level])[v_act].set_position(new_pos);
523 (*A_mult_ptr[level])[v_act].place();
524 }
525 }
526
527
528 void Multilevel::set_initial_positions_of_planet_and_moon_nodes(
529 int level,
530 int init_placement_way,
531 Array<Graph*> &G_mult_ptr,
532 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
533 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
534 List<node>& pm_nodes)
535 {
536 double lambda, dedicated_sun_distance;
537 int node_type;
538 node v, v_adj, dedicated_sun;
539 edge e;
540 DPoint new_pos,dedicated_sun_pos, adj_sun_pos;
541 List<DPoint> L;
542 ListIterator<double> lambdaIterator;
543
544 create_all_placement_sectors(G_mult_ptr,A_mult_ptr,E_mult_ptr,level);
545 forall_nodes(v,*G_mult_ptr[level])
546 {//for
547 node_type = (*A_mult_ptr[level])[v].get_type();
548 if(node_type == 3)
549 pm_nodes.pushBack(v);
550 else if(node_type == 2 || node_type == 4) //a planet_node or moon_node
551 {//else
552 L.clear();
553 dedicated_sun = (*A_mult_ptr[level])[v].get_dedicated_sun_node();
554 dedicated_sun_pos = (*A_mult_ptr[level])[dedicated_sun].get_position();
555 dedicated_sun_distance = (*A_mult_ptr[level])[v].get_dedicated_sun_distance();
556
557 if(init_placement_way == FMMMLayout::ipmAdvanced)
558 {
559 forall_adj_edges(e,v)
560 {
561 if(e->source() != v)
562 v_adj = e->source();
563 else
564 v_adj = e->target();
565 if( ( (*A_mult_ptr[level])[v].get_dedicated_sun_node() ==
566 (*A_mult_ptr[level])[v_adj].get_dedicated_sun_node() ) &&
567 ( (*A_mult_ptr[level])[v_adj].get_type() != 1 ) &&
568 ( (*A_mult_ptr[level])[v_adj].is_placed() ) )
569 {
570 new_pos = calculate_position(dedicated_sun_pos,(*A_mult_ptr[level])
571 [v_adj].get_position(),dedicated_sun_distance,
572 (*E_mult_ptr[level])[e].get_length());
573 L.pushBack(new_pos);
574 }
575 }
576 }
577 if ((*A_mult_ptr[level])[v].get_lambda_List_ptr()->empty())
578 {//special case
579 if(L.empty())
580 {
581 new_pos = create_random_pos(dedicated_sun_pos,(*A_mult_ptr[level])
582 [v].get_dedicated_sun_distance(),
583 (*A_mult_ptr[level])[v].get_angle_1(),
584 (*A_mult_ptr[level])[v].get_angle_2());
585 L.pushBack(new_pos);
586 }
587 }//special case
588 else
589 {//usual case
590 lambdaIterator = (*A_mult_ptr[level])[v].get_lambda_List_ptr()->begin();
591
592 forall_listiterators(node, adj_sun_ptr,*(*A_mult_ptr[level])[v].
593 get_neighbour_sun_node_List_ptr())
594 {
595 lambda = *lambdaIterator;
596 adj_sun_pos = (*A_mult_ptr[level])[*adj_sun_ptr].get_position();
597 new_pos = get_waggled_inbetween_position(dedicated_sun_pos,adj_sun_pos,
598 lambda);
599 L.pushBack(new_pos);
600 if(lambdaIterator != (*A_mult_ptr[level])[v].get_lambda_List_ptr()
601 ->rbegin())
602 lambdaIterator = (*A_mult_ptr[level])[v].get_lambda_List_ptr()
603 ->cyclicSucc(lambdaIterator);
604 }
605 }//usual case
606
607 (*A_mult_ptr[level])[v].set_position(get_barycenter_position(L));
608 (*A_mult_ptr[level])[v].place();
609 }//else
610 }//for
611 }
612
613
614 void Multilevel::create_all_placement_sectors(
615 Array<Graph*> &G_mult_ptr,
616 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
617 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
618 int level)
619 {
620 node v_high, w_high, sun_node, v, ded_sun;
621 edge e_high;
622 List<DPoint> adj_pos;
623 double angle_1, angle_2, act_angle_1, act_angle_2, next_angle, min_next_angle;
624 DPoint start_pos, end_pos;
625 int MAX = 10; //the biggest of at most MAX random selected sectors is choosen
626 int steps;
627 ListIterator<DPoint> it, next_pos_ptr;
628 bool first_angle;
629
630
631 forall_nodes(v_high,(*G_mult_ptr[level+1]))
632 {//forall
633 //find pos of adjacent nodes
634 adj_pos.clear();
635 DPoint v_high_pos ((*A_mult_ptr[level+1])[v_high].get_x(),
636 (*A_mult_ptr[level+1])[v_high].get_y());
637 forall_adj_edges(e_high,v_high)
638 if(!(*E_mult_ptr[level+1])[e_high].is_extra_edge())
639 {
640 if(v_high == e_high->source())
641 w_high = e_high->target();
642 else
643 w_high = e_high->source();
644
645 DPoint w_high_pos ((*A_mult_ptr[level+1])[w_high].get_x(),
646 (*A_mult_ptr[level+1])[w_high].get_y());
647 adj_pos.pushBack(w_high_pos);
648 }
649 if(adj_pos.empty()) //easy case
650 {
651 angle_1 = 0;
652 angle_2 = 6.2831853;
653 }
654 else if(adj_pos.size() == 1) //special case
655 {
656 //create angle_1
657 start_pos = *adj_pos.begin();
658 DPoint x_parallel_pos (v_high_pos.m_x + 1, v_high_pos.m_y);
659 angle_1 = angle(v_high_pos,x_parallel_pos,start_pos);
660 //create angle_2
661 angle_2 = angle_1 + Math::pi;
662 }
663 else //usual case
664 {//else
665 steps = 1;
666 it = adj_pos.begin();
667 do
668 {
669 //create act_angle_1
670 start_pos = *it;
671 DPoint x_parallel_pos (v_high_pos.m_x + 1, v_high_pos.m_y);
672 act_angle_1 = angle(v_high_pos,x_parallel_pos,start_pos);
673 //create act_angle_2
674 first_angle = true;
675
676 for(next_pos_ptr = adj_pos.begin();next_pos_ptr.valid();++next_pos_ptr)
677 {
678 next_angle = angle(v_high_pos,start_pos,*next_pos_ptr);
679
680 if(start_pos != *next_pos_ptr && (first_angle || next_angle <
681 min_next_angle))
682 {
683 min_next_angle = next_angle;
684 first_angle = false;
685 }
686 }
687 act_angle_2 = act_angle_1 + min_next_angle;
688 if((it == adj_pos.begin())||((act_angle_2-act_angle_1)>(angle_2-angle_1)))
689 {
690 angle_1 = act_angle_1;
691 angle_2 = act_angle_2;
692 }
693 if(it != adj_pos.rbegin())
694 it = adj_pos.cyclicSucc(it);
695 steps++;
696 }
697 while((steps <= MAX) && (it != adj_pos.rbegin()));
698
699 if(angle_1 == angle_2)
700 angle_2 = angle_1 + Math::pi;
701 }//else
702
703 //import angle_1 and angle_2 to the dedicated suns at level level
704 sun_node = (*A_mult_ptr[level+1])[v_high].get_lower_level_node();
705 (*A_mult_ptr[level])[sun_node].set_angle_1(angle_1);
706 (*A_mult_ptr[level])[sun_node].set_angle_2(angle_2);
707 }//forall
708
709 //import the angle values from the values of the dedicated sun nodes
710 forall_nodes(v,*G_mult_ptr[level])
711 {
712 ded_sun = (*A_mult_ptr[level])[v].get_dedicated_sun_node();
713 (*A_mult_ptr[level])[v].set_angle_1((*A_mult_ptr[level])[ded_sun].get_angle_1());
714 (*A_mult_ptr[level])[v].set_angle_2((*A_mult_ptr[level])[ded_sun].get_angle_2());
715 }
716 }
717
718
719 void Multilevel::set_initial_positions_of_pm_nodes(
720 int level,
721 int init_placement_way,
722 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
723 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
724 List<node>& pm_nodes)
725 {
726 double moon_dist, sun_dist, lambda;
727 node v_adj, sun_node;
728 edge e;
729 DPoint sun_pos, moon_pos, new_pos, adj_sun_pos;
730 List<DPoint> L;
731 ListIterator<double> lambdaIterator;
732
733 forall_listiterators(node,v_ptr,pm_nodes)
734 {//forall
735 L.clear();
736 sun_node = (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_node();
737 sun_pos = (*A_mult_ptr[level])[sun_node].get_position();
738 sun_dist = (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_distance();
739
740 if(init_placement_way == FMMMLayout::ipmAdvanced)
741 {//if
742 forall_adj_edges(e,*v_ptr)
743 {
744 if(e->source() != *v_ptr)
745 v_adj = e->source();
746 else
747 v_adj = e->target();
748 if( (!(*E_mult_ptr[level])[e].is_moon_edge()) &&
749 ( (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_node() ==
750 (*A_mult_ptr[level])[v_adj].get_dedicated_sun_node() ) &&
751 ( (*A_mult_ptr[level])[v_adj].get_type() != 1 ) &&
752 ( (*A_mult_ptr[level])[v_adj].is_placed() ) )
753 {
754 new_pos = calculate_position(sun_pos,(*A_mult_ptr[level])[v_adj].
755 get_position(),sun_dist,(*E_mult_ptr[level])
756 [e].get_length());
757 L.pushBack(new_pos);
758 }
759 }
760 }//if
761 forall_listiterators(node, moon_node_ptr,*(*A_mult_ptr[level])[*v_ptr].
762 get_dedicated_moon_node_List_ptr())
763 {
764 moon_pos = (*A_mult_ptr[level])[*moon_node_ptr].get_position();
765 moon_dist = (*A_mult_ptr[level])[*moon_node_ptr].get_dedicated_sun_distance();
766 lambda = sun_dist/moon_dist;
767 new_pos = get_waggled_inbetween_position(sun_pos,moon_pos,lambda);
768 L.pushBack(new_pos);
769 }
770
771 if (!(*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()->empty())
772 {
773 lambdaIterator = (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()->begin();
774
775 forall_listiterators(node,adj_sun_ptr,*(*A_mult_ptr[level])[*v_ptr].
776 get_neighbour_sun_node_List_ptr())
777 {
778 lambda = *lambdaIterator;
779 adj_sun_pos = (*A_mult_ptr[level])[*adj_sun_ptr].get_position();
780 new_pos = get_waggled_inbetween_position(sun_pos,adj_sun_pos,lambda);
781 L.pushBack(new_pos);
782 if(lambdaIterator != (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()
783 ->rbegin())
784 lambdaIterator = (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()
785 ->cyclicSucc(lambdaIterator);
786 }
787 }
788
789 (*A_mult_ptr[level])[*v_ptr].set_position(get_barycenter_position(L));
790 (*A_mult_ptr[level])[*v_ptr].place();
791 }//forall
792 }
793
794
795 inline DPoint Multilevel::create_random_pos(DPoint center,double radius,double angle_1,
796 double angle_2)
797 {
798 const int BILLION = 1000000000;
799 DPoint new_point;
800 double rnd = double(randomNumber(1,BILLION)+1)/(BILLION+2);//rand number in (0,1)
801 double rnd_angle = angle_1 +(angle_2-angle_1)*rnd;
802 double dx = cos(rnd_angle) * radius;
803 double dy = sin(rnd_angle) * radius;
804 new_point.m_x = center.m_x + dx ;
805 new_point.m_y = center.m_y + dy;
806 return new_point;
807 }
808
809
810 inline DPoint Multilevel::get_waggled_inbetween_position(DPoint s, DPoint t, double lambda)
811 {
812 const double WAGGLEFACTOR = 0.05;
813 const int BILLION = 1000000000;
814 DPoint inbetween_point;
815 inbetween_point.m_x = s.m_x + lambda*(t.m_x - s.m_x);
816 inbetween_point.m_y = s.m_y + lambda*(t.m_y - s.m_y);
817 double radius = WAGGLEFACTOR * (t-s).norm();
818 double rnd = double(randomNumber(1,BILLION)+1)/(BILLION+2);//rand number in (0,1)
819 double rand_radius = radius * rnd;
820 return create_random_pos(inbetween_point,rand_radius,0,6.2831853);
821 }
822
823
824 inline DPoint Multilevel::get_barycenter_position(List<DPoint>& L)
825 {
826 DPoint sum (0,0);
827 DPoint barycenter;
828
829 forall_listiterators(DPoint, act_point_ptr,L)
830 sum = sum + (*act_point_ptr);
831 barycenter.m_x = sum.m_x/L.size();
832 barycenter.m_y = sum.m_y/L.size();
833 return barycenter;
834 }
835
836
837 inline DPoint Multilevel::calculate_position(DPoint P, DPoint Q, double dist_P, double dist_Q)
838 {
839 double dist_PQ = (P-Q).norm();
840 double lambda = (dist_P + (dist_PQ - dist_P - dist_Q)/2)/dist_PQ;
841 return get_waggled_inbetween_position(P,Q,lambda);
842 }
843
844
845 void Multilevel::delete_multilevel_representations(
846 Array<Graph*> &G_mult_ptr,
847 Array<NodeArray<NodeAttributes>*> &A_mult_ptr,
848 Array<EdgeArray<EdgeAttributes>*> &E_mult_ptr,
849 int max_level)
850 {
851 for(int i=1; i<= max_level; i++)
852 {
853 delete G_mult_ptr[i];
854 delete A_mult_ptr[i];
855 delete E_mult_ptr[i];
856 }
857 }
858
859
860 double Multilevel::angle(DPoint& P, DPoint& Q, DPoint& R)
861 {
862 double dx1 = Q.m_x - P.m_x;
863 double dy1 = Q.m_y - P.m_y;
864 double dx2 = R.m_x - P.m_x;
865 double dy2 = R.m_y - P.m_y;
866 double fi;//the angle
867
868 if ((dx1 == 0 && dy1 == 0) || (dx2 == 0 && dy2 == 0))
869 cout<<"Multilevel::angle()"<<endl;
870
871 double norm = (dx1*dx1+dy1*dy1)*(dx2*dx2+dy2*dy2);
872 double cosfi = (dx1*dx2+dy1*dy2) / sqrt(norm);
873
874 if (cosfi >= 1.0 ) fi = 0;
875 if (cosfi <= -1.0 ) fi = Math::pi;
876 else
877 {
878 fi = acos(cosfi);
879 if (dx1*dy2 < dy1*dx2) fi = -fi;
880 if (fi < 0) fi += 2*Math::pi;
881 }
882 return fi;
883 }
884
885 }//namespace ogdf
Windows Explorer Extension to Operate Git