/*
* $Revision: 2552 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
***************************************************************/
/** \file
* \brief Implementation 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
***************************************************************/
#include "Multilevel.h"
#include "Set.h"
#include "Node.h"
#include "../basic/Array.h"
#include "../basic/Math.h"
#include "../basic/simple_graph_alg.h"
#include "FMMMLayout.h"
namespace ogdf {
void Multilevel::create_multilevel_representations(
Graph& G,
NodeArray& A,
EdgeArray& E,
int rand_seed,
int galaxy_choice,
int min_Graph_size,
int random_tries,
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
int & max_level)
{
//make initialisations;
srand(rand_seed);
G_mult_ptr[0] = &G; //init graph at level 0 to the original undirected simple
A_mult_ptr[0] = &A; //and loopfree connected graph G/A/E
E_mult_ptr[0] = &E;
int bad_edgenr_counter = 0;
int act_level = 0;
Graph* act_Graph_ptr = G_mult_ptr[0];
while( (act_Graph_ptr->numberOfNodes() > min_Graph_size) &&
edgenumbersum_of_all_levels_is_linear(G_mult_ptr,act_level,bad_edgenr_counter) )
{
Graph* G_new = new (Graph);
NodeArray* A_new = OGDF_NEW NodeArray;
EdgeArray* E_new = OGDF_NEW EdgeArray;
G_mult_ptr[act_level+1] = G_new;
A_mult_ptr[act_level+1] = A_new;
E_mult_ptr[act_level+1] = E_new;
init_multilevel_values(G_mult_ptr,A_mult_ptr,E_mult_ptr,act_level);
partition_galaxy_into_solar_systems(G_mult_ptr,A_mult_ptr,E_mult_ptr,rand_seed,
galaxy_choice,random_tries,act_level);
collaps_solar_systems(G_mult_ptr,A_mult_ptr,E_mult_ptr,act_level);
act_level++;
act_Graph_ptr = G_mult_ptr[act_level];
}
max_level = act_level;
}
bool Multilevel::edgenumbersum_of_all_levels_is_linear(
Array &G_mult_ptr,
int act_level,
int& bad_edgenr_counter)
{
if(act_level == 0)
return true;
else
{
if(G_mult_ptr[act_level]->numberOfEdges()<=
0.8 * double (G_mult_ptr[act_level-1]->numberOfEdges()))
return true;
else if(bad_edgenr_counter < 5)
{
bad_edgenr_counter++;
return true;
}
else
return false;
}
}
inline void Multilevel::init_multilevel_values(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
int level)
{
node v;
forall_nodes(v,*G_mult_ptr[level])
(*A_mult_ptr[level])[v].init_mult_values();
edge e;
forall_edges(e,*G_mult_ptr[level])
(*E_mult_ptr[level])[e].init_mult_values();
}
inline void Multilevel::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)
{
create_suns_and_planets(G_mult_ptr, A_mult_ptr, E_mult_ptr, rand_seed, galaxy_choice,
random_tries, act_level);
create_moon_nodes_and_pm_nodes(G_mult_ptr, A_mult_ptr, E_mult_ptr, act_level);
}
void Multilevel::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)
{
Set Node_Set;
node v, sun_node, planet_node, newNode, pos_moon_node;
edge sun_edge, e;
double dist_to_sun;
List planet_nodes;
List sun_nodes;
//make initialisations
sun_nodes.clear();
Node_Set.set_seed(rand_seed); //set seed for random number generator
forall_nodes(v,*G_mult_ptr[act_level])
if(act_level == 0) (*A_mult_ptr[act_level])[v].set_mass(1);
if(galaxy_choice == FMMMLayout::gcUniformProb)
Node_Set.init_node_set(*G_mult_ptr[act_level]);
else //galaxy_choice != gcUniformProb in FMMMLayout
Node_Set.init_node_set(*G_mult_ptr[act_level],*A_mult_ptr[act_level]);
while (!Node_Set.empty_node_set())
{//while
//randomly select a sun node
planet_nodes.clear();
if(galaxy_choice == FMMMLayout::gcUniformProb)
sun_node = Node_Set.get_random_node();
else if (galaxy_choice == FMMMLayout::gcNonUniformProbLowerMass)
sun_node = Node_Set.get_random_node_with_lowest_star_mass(random_tries);
else //galaxy_choice == FMMMLayout::gcNonUniformProbHigherMass
sun_node = Node_Set.get_random_node_with_highest_star_mass(random_tries);
sun_nodes.pushBack(sun_node);
//create new node at higher level that represents the collapsed solar_system
newNode = G_mult_ptr[act_level+1]->newNode();
//update information for sun_node
(*A_mult_ptr[act_level])[sun_node].set_higher_level_node(newNode);
(*A_mult_ptr[act_level])[sun_node].set_type(1);
(*A_mult_ptr[act_level])[sun_node].set_dedicated_sun_node(sun_node);
(*A_mult_ptr[act_level])[sun_node].set_dedicated_sun_distance(0);
//update information for planet_nodes
forall_adj_edges(sun_edge,sun_node)
{
dist_to_sun = (*E_mult_ptr[act_level])[sun_edge].get_length();
if (sun_edge->source() != sun_node)
planet_node = sun_edge->source();
else
planet_node = sun_edge->target();
(*A_mult_ptr[act_level])[planet_node].set_type(2);
(*A_mult_ptr[act_level])[planet_node].set_dedicated_sun_node(sun_node);
(*A_mult_ptr[act_level])[planet_node].set_dedicated_sun_distance(dist_to_sun);
planet_nodes.pushBack(planet_node);
}
//delete all planet_nodes and possible_moon_nodes from Node_Set
ListConstIterator planet_node_ptr;
//forall_listiterators(node,planet_node_ptr,planet_nodes)
for(planet_node_ptr = planet_nodes.begin(); planet_node_ptr.valid(); ++planet_node_ptr)
if(!Node_Set.is_deleted(*planet_node_ptr))
Node_Set.delete_node(*planet_node_ptr);
for(planet_node_ptr = planet_nodes.begin(); planet_node_ptr.valid(); ++planet_node_ptr)
//forall_listiterators(node,planet_node_ptr,planet_nodes)
{
forall_adj_edges(e,*planet_node_ptr)
{
if(e->source() == *planet_node_ptr)
pos_moon_node = e->target();
else
pos_moon_node = e->source();
if(!Node_Set.is_deleted(pos_moon_node))
Node_Set.delete_node(pos_moon_node);
}
}
}//while
//init *A_mult_ptr[act_level+1] and set NodeAttributes information for new nodes
A_mult_ptr[act_level+1]->init(*G_mult_ptr[act_level+1]);
forall_listiterators(node, sun_node_ptr, sun_nodes)
{
newNode = (*A_mult_ptr[act_level])[*sun_node_ptr].get_higher_level_node();
(*A_mult_ptr[act_level+1])[newNode].set_NodeAttributes((*A_mult_ptr[act_level])
[*sun_node_ptr].get_width(),
(*A_mult_ptr[act_level])
[*sun_node_ptr].get_height(),
(*A_mult_ptr[act_level])
[*sun_node_ptr].get_position(),
*sun_node_ptr,NULL);
(*A_mult_ptr[act_level+1])[newNode].set_mass(0);
}
}
void Multilevel::create_moon_nodes_and_pm_nodes(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
int act_level)
{
edge e;
node v, nearest_neighbour_node = node(), neighbour_node, dedicated_sun_node;
double dist_to_nearest_neighbour = 0, dedicated_sun_distance;
bool first_adj_edge;
int neighbour_type;
edge moon_edge = edge();
forall_nodes(v,*G_mult_ptr[act_level])
if((*A_mult_ptr[act_level])[v].get_type() == 0) //a moon node
{//forall
//find nearest neighbour node
first_adj_edge = true;
forall_adj_edges(e,v)
{//forall2
if(v == e->source())
neighbour_node = e->target();
else
neighbour_node = e->source();
neighbour_type = (*A_mult_ptr[act_level])[neighbour_node].get_type();
if( (neighbour_type == 2) || (neighbour_type == 3) )
{//if_1
if(first_adj_edge)
{//if
first_adj_edge = false;
moon_edge = e;
dist_to_nearest_neighbour = (*E_mult_ptr[act_level])[e].get_length();
nearest_neighbour_node = neighbour_node;
}//if
else if(dist_to_nearest_neighbour >(*E_mult_ptr[act_level])[e].get_length())
{//else
moon_edge = e;
dist_to_nearest_neighbour = (*E_mult_ptr[act_level])[e].get_length();
nearest_neighbour_node = neighbour_node;
}//else
}//if_1
}//forall2
//find dedic. solar system for v and update information in *A_mult_ptr[act_level]
//and *E_mult_ptr[act_level]
(*E_mult_ptr[act_level])[moon_edge].make_moon_edge(); //mark this edge
dedicated_sun_node = (*A_mult_ptr[act_level])[nearest_neighbour_node].
get_dedicated_sun_node();
dedicated_sun_distance = dist_to_nearest_neighbour + (*A_mult_ptr[act_level])
[nearest_neighbour_node].get_dedicated_sun_distance();
(*A_mult_ptr[act_level])[v].set_type(4);
(*A_mult_ptr[act_level])[v].set_dedicated_sun_node(dedicated_sun_node);
(*A_mult_ptr[act_level])[v].set_dedicated_sun_distance(dedicated_sun_distance);
(*A_mult_ptr[act_level])[v].set_dedicated_pm_node(nearest_neighbour_node);
//identify nearest_neighbour_node as a pm_node and update its information
(*A_mult_ptr[act_level])[nearest_neighbour_node].set_type(3);
(*A_mult_ptr[act_level])[nearest_neighbour_node].
get_dedicated_moon_node_List_ptr()->pushBack(v);
}//forall
}
inline void Multilevel::collaps_solar_systems(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
int act_level)
{
EdgeArray new_edgelength;
calculate_mass_of_collapsed_nodes(G_mult_ptr, A_mult_ptr, act_level);
create_edges_edgedistances_and_lambda_Lists(G_mult_ptr, A_mult_ptr, E_mult_ptr,
new_edgelength, act_level);
delete_parallel_edges_and_update_edgelength(G_mult_ptr, E_mult_ptr, new_edgelength,
act_level);
}
inline void Multilevel::calculate_mass_of_collapsed_nodes(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
int act_level)
{
node v;
node dedicated_sun,high_level_node;
forall_nodes(v,*G_mult_ptr[act_level])
{
dedicated_sun = (*A_mult_ptr[act_level])[v].get_dedicated_sun_node();
high_level_node = (*A_mult_ptr[act_level])[dedicated_sun].get_higher_level_node();
(*A_mult_ptr[act_level+1])[high_level_node].set_mass((*A_mult_ptr[act_level+1])
[high_level_node].get_mass()+1);
}
}
void Multilevel::create_edges_edgedistances_and_lambda_Lists(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
EdgeArray& new_edgelength,int
act_level)
{
edge e, e_new;
node s_node, t_node;
node s_sun_node, t_sun_node;
node high_level_sun_s, high_level_sun_t;
double length_e, length_s_edge, length_t_edge, newlength;
double lambda_s, lambda_t;
List inter_solar_system_edges;
//create new edges at act_level+1 and create for each inter solar system edge at
//act_level a link to its corresponding edge
forall_edges(e,*G_mult_ptr[act_level])
{//forall
s_node = e->source();
t_node = e->target();
s_sun_node = (*A_mult_ptr[act_level])[s_node].get_dedicated_sun_node();
t_sun_node = (*A_mult_ptr[act_level])[t_node].get_dedicated_sun_node();
if( s_sun_node != t_sun_node) //a inter solar system edge
{//if
high_level_sun_s = (*A_mult_ptr[act_level])[s_sun_node].get_higher_level_node();
high_level_sun_t = (*A_mult_ptr[act_level])[t_sun_node].get_higher_level_node();
//create new edge in *G_mult_ptr[act_level+1]
e_new = G_mult_ptr[act_level+1]->newEdge(high_level_sun_s,high_level_sun_t);
(*E_mult_ptr[act_level])[e].set_higher_level_edge(e_new);
inter_solar_system_edges.pushBack(e);
}//if
}//forall
//init new_edgelength calculate the values of new_edgelength and the lambda Lists
new_edgelength.init(*G_mult_ptr[act_level+1]);
forall_listiterators(edge, e_ptr, inter_solar_system_edges)
{//forall
s_node = (*e_ptr)->source();
t_node = (*e_ptr)->target();
s_sun_node = (*A_mult_ptr[act_level])[s_node].get_dedicated_sun_node();
t_sun_node = (*A_mult_ptr[act_level])[t_node].get_dedicated_sun_node();
length_e = (*E_mult_ptr[act_level])[*e_ptr].get_length();
length_s_edge =(*A_mult_ptr[act_level])[s_node].get_dedicated_sun_distance();
length_t_edge =(*A_mult_ptr[act_level])[t_node].get_dedicated_sun_distance();
newlength = length_s_edge + length_e + length_t_edge;
//set new edge_length in *G_mult_ptr[act_level+1]
e_new = (*E_mult_ptr[act_level])[*e_ptr].get_higher_level_edge();
new_edgelength[e_new] = newlength;
//create entries in lambda Lists
lambda_s = length_s_edge/newlength;
lambda_t = length_t_edge/newlength;
(*A_mult_ptr[act_level])[s_node].get_lambda_List_ptr()->pushBack(lambda_s);
(*A_mult_ptr[act_level])[t_node].get_lambda_List_ptr()->pushBack(lambda_t);
(*A_mult_ptr[act_level])[s_node].get_neighbour_sun_node_List_ptr()->pushBack(
t_sun_node);
(*A_mult_ptr[act_level])[t_node].get_neighbour_sun_node_List_ptr()->pushBack(
s_sun_node);
}//forall
}
void Multilevel::delete_parallel_edges_and_update_edgelength(
Array &G_mult_ptr,
Array*> &E_mult_ptr,
EdgeArray& new_edgelength,int
act_level)
{
EdgeMaxBucketFunc get_max_index;
EdgeMinBucketFunc get_min_index;
edge e_act, e_save = 0;
Edge f_act;
List sorted_edges;
Graph* Graph_ptr = G_mult_ptr[act_level+1];
int save_s_index = 0, save_t_index = 0, act_s_index, act_t_index;
int counter = 1;
//make *G_mult_ptr[act_level+1] undirected
makeSimpleUndirected(*G_mult_ptr[act_level+1]);
//sort the List sorted_edges
forall_edges(e_act,*Graph_ptr)
{
f_act.set_Edge(e_act,Graph_ptr);
sorted_edges.pushBack(f_act);
}
sorted_edges.bucketSort(0,Graph_ptr->numberOfNodes()-1,get_max_index);
sorted_edges.bucketSort(0,Graph_ptr->numberOfNodes()-1,get_min_index);
//now parallel edges are consecutive in sorted_edges
forall_listiterators(Edge, EdgeIterator,sorted_edges)
{//for
e_act = (*EdgeIterator).get_edge();
act_s_index = e_act->source()->index();
act_t_index = e_act->target()->index();
if(EdgeIterator != sorted_edges.begin())
{//if
if( (act_s_index == save_s_index && act_t_index == save_t_index) ||
(act_s_index == save_t_index && act_t_index == save_s_index) )
{
new_edgelength[e_save] += new_edgelength[e_act];
Graph_ptr->delEdge(e_act);
counter++;
}
else
{
if (counter > 1)
{
new_edgelength[e_save] /= counter;
counter = 1;
}
save_s_index = act_s_index;
save_t_index = act_t_index;
e_save = e_act;
}
}//if
else //first edge
{
save_s_index = act_s_index;
save_t_index = act_t_index;
e_save = e_act;
}
}//for
//treat special case (last edges were multiple edges)
if(counter >1)
new_edgelength[e_save] /= counter;
//init *E_mult_ptr[act_level+1] and import EdgeAttributes
E_mult_ptr[act_level+1]->init(*G_mult_ptr[act_level+1]);
forall_edges(e_act,*Graph_ptr)
(*E_mult_ptr[act_level+1])[e_act].set_length(new_edgelength[e_act]);
}
void Multilevel::find_initial_placement_for_level(
int level,
int init_placement_way,
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr)
{
List pm_nodes;
set_initial_positions_of_sun_nodes(level, G_mult_ptr, A_mult_ptr);
set_initial_positions_of_planet_and_moon_nodes(level, init_placement_way, G_mult_ptr,
A_mult_ptr, E_mult_ptr, pm_nodes);
set_initial_positions_of_pm_nodes(level, init_placement_way, A_mult_ptr,
E_mult_ptr, pm_nodes);
}
void Multilevel::set_initial_positions_of_sun_nodes(
int level,
Array &G_mult_ptr,
Array*> &A_mult_ptr)
{
node v_high, v_act;
DPoint new_pos;
forall_nodes(v_high,*G_mult_ptr[level+1])
{
v_act = (*A_mult_ptr[level+1])[v_high].get_lower_level_node();
new_pos = (*A_mult_ptr[level+1])[v_high].get_position();
(*A_mult_ptr[level])[v_act].set_position(new_pos);
(*A_mult_ptr[level])[v_act].place();
}
}
void Multilevel::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)
{
double lambda, dedicated_sun_distance;
int node_type;
node v, v_adj, dedicated_sun;
edge e;
DPoint new_pos,dedicated_sun_pos, adj_sun_pos;
List L;
ListIterator lambdaIterator;
create_all_placement_sectors(G_mult_ptr,A_mult_ptr,E_mult_ptr,level);
forall_nodes(v,*G_mult_ptr[level])
{//for
node_type = (*A_mult_ptr[level])[v].get_type();
if(node_type == 3)
pm_nodes.pushBack(v);
else if(node_type == 2 || node_type == 4) //a planet_node or moon_node
{//else
L.clear();
dedicated_sun = (*A_mult_ptr[level])[v].get_dedicated_sun_node();
dedicated_sun_pos = (*A_mult_ptr[level])[dedicated_sun].get_position();
dedicated_sun_distance = (*A_mult_ptr[level])[v].get_dedicated_sun_distance();
if(init_placement_way == FMMMLayout::ipmAdvanced)
{
forall_adj_edges(e,v)
{
if(e->source() != v)
v_adj = e->source();
else
v_adj = e->target();
if( ( (*A_mult_ptr[level])[v].get_dedicated_sun_node() ==
(*A_mult_ptr[level])[v_adj].get_dedicated_sun_node() ) &&
( (*A_mult_ptr[level])[v_adj].get_type() != 1 ) &&
( (*A_mult_ptr[level])[v_adj].is_placed() ) )
{
new_pos = calculate_position(dedicated_sun_pos,(*A_mult_ptr[level])
[v_adj].get_position(),dedicated_sun_distance,
(*E_mult_ptr[level])[e].get_length());
L.pushBack(new_pos);
}
}
}
if ((*A_mult_ptr[level])[v].get_lambda_List_ptr()->empty())
{//special case
if(L.empty())
{
new_pos = create_random_pos(dedicated_sun_pos,(*A_mult_ptr[level])
[v].get_dedicated_sun_distance(),
(*A_mult_ptr[level])[v].get_angle_1(),
(*A_mult_ptr[level])[v].get_angle_2());
L.pushBack(new_pos);
}
}//special case
else
{//usual case
lambdaIterator = (*A_mult_ptr[level])[v].get_lambda_List_ptr()->begin();
forall_listiterators(node, adj_sun_ptr,*(*A_mult_ptr[level])[v].
get_neighbour_sun_node_List_ptr())
{
lambda = *lambdaIterator;
adj_sun_pos = (*A_mult_ptr[level])[*adj_sun_ptr].get_position();
new_pos = get_waggled_inbetween_position(dedicated_sun_pos,adj_sun_pos,
lambda);
L.pushBack(new_pos);
if(lambdaIterator != (*A_mult_ptr[level])[v].get_lambda_List_ptr()
->rbegin())
lambdaIterator = (*A_mult_ptr[level])[v].get_lambda_List_ptr()
->cyclicSucc(lambdaIterator);
}
}//usual case
(*A_mult_ptr[level])[v].set_position(get_barycenter_position(L));
(*A_mult_ptr[level])[v].place();
}//else
}//for
}
void Multilevel::create_all_placement_sectors(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
int level)
{
node v_high, w_high, sun_node, v, ded_sun;
edge e_high;
List adj_pos;
double angle_1 = 0.0, angle_2 = 0.0, act_angle_1, act_angle_2, next_angle, min_next_angle = 0.0;
DPoint start_pos, end_pos;
int MAX = 10; //the biggest of at most MAX random selected sectors is choosen
int steps;
ListIterator it, next_pos_ptr;
bool first_angle;
forall_nodes(v_high,(*G_mult_ptr[level+1]))
{//forall
//find pos of adjacent nodes
adj_pos.clear();
DPoint v_high_pos ((*A_mult_ptr[level+1])[v_high].get_x(),
(*A_mult_ptr[level+1])[v_high].get_y());
forall_adj_edges(e_high,v_high)
if(!(*E_mult_ptr[level+1])[e_high].is_extra_edge())
{
if(v_high == e_high->source())
w_high = e_high->target();
else
w_high = e_high->source();
DPoint w_high_pos ((*A_mult_ptr[level+1])[w_high].get_x(),
(*A_mult_ptr[level+1])[w_high].get_y());
adj_pos.pushBack(w_high_pos);
}
if(adj_pos.empty()) //easy case
{
angle_1 = 0;
angle_2 = 6.2831853;
}
else if(adj_pos.size() == 1) //special case
{
//create angle_1
start_pos = *adj_pos.begin();
DPoint x_parallel_pos (v_high_pos.m_x + 1, v_high_pos.m_y);
angle_1 = angle(v_high_pos,x_parallel_pos,start_pos);
//create angle_2
angle_2 = angle_1 + Math::pi;
}
else //usual case
{//else
steps = 1;
it = adj_pos.begin();
do
{
//create act_angle_1
start_pos = *it;
DPoint x_parallel_pos (v_high_pos.m_x + 1, v_high_pos.m_y);
act_angle_1 = angle(v_high_pos,x_parallel_pos,start_pos);
//create act_angle_2
first_angle = true;
for(next_pos_ptr = adj_pos.begin();next_pos_ptr.valid();++next_pos_ptr)
{
next_angle = angle(v_high_pos,start_pos,*next_pos_ptr);
if(start_pos != *next_pos_ptr && (first_angle || next_angle <
min_next_angle))
{
min_next_angle = next_angle;
first_angle = false;
}
}
act_angle_2 = act_angle_1 + min_next_angle;
if((it == adj_pos.begin())||((act_angle_2-act_angle_1)>(angle_2-angle_1)))
{
angle_1 = act_angle_1;
angle_2 = act_angle_2;
}
if(it != adj_pos.rbegin())
it = adj_pos.cyclicSucc(it);
steps++;
}
while((steps <= MAX) && (it != adj_pos.rbegin()));
if(angle_1 == angle_2)
angle_2 = angle_1 + Math::pi;
}//else
//import angle_1 and angle_2 to the dedicated suns at level level
sun_node = (*A_mult_ptr[level+1])[v_high].get_lower_level_node();
(*A_mult_ptr[level])[sun_node].set_angle_1(angle_1);
(*A_mult_ptr[level])[sun_node].set_angle_2(angle_2);
}//forall
//import the angle values from the values of the dedicated sun nodes
forall_nodes(v,*G_mult_ptr[level])
{
ded_sun = (*A_mult_ptr[level])[v].get_dedicated_sun_node();
(*A_mult_ptr[level])[v].set_angle_1((*A_mult_ptr[level])[ded_sun].get_angle_1());
(*A_mult_ptr[level])[v].set_angle_2((*A_mult_ptr[level])[ded_sun].get_angle_2());
}
}
void Multilevel::set_initial_positions_of_pm_nodes(
int level,
int init_placement_way,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
List& pm_nodes)
{
double moon_dist, sun_dist, lambda;
node v_adj, sun_node;
edge e;
DPoint sun_pos, moon_pos, new_pos, adj_sun_pos;
List L;
ListIterator lambdaIterator;
forall_listiterators(node,v_ptr,pm_nodes)
{//forall
L.clear();
sun_node = (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_node();
sun_pos = (*A_mult_ptr[level])[sun_node].get_position();
sun_dist = (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_distance();
if(init_placement_way == FMMMLayout::ipmAdvanced)
{//if
forall_adj_edges(e,*v_ptr)
{
if(e->source() != *v_ptr)
v_adj = e->source();
else
v_adj = e->target();
if( (!(*E_mult_ptr[level])[e].is_moon_edge()) &&
( (*A_mult_ptr[level])[*v_ptr].get_dedicated_sun_node() ==
(*A_mult_ptr[level])[v_adj].get_dedicated_sun_node() ) &&
( (*A_mult_ptr[level])[v_adj].get_type() != 1 ) &&
( (*A_mult_ptr[level])[v_adj].is_placed() ) )
{
new_pos = calculate_position(sun_pos,(*A_mult_ptr[level])[v_adj].
get_position(),sun_dist,(*E_mult_ptr[level])
[e].get_length());
L.pushBack(new_pos);
}
}
}//if
forall_listiterators(node, moon_node_ptr,*(*A_mult_ptr[level])[*v_ptr].
get_dedicated_moon_node_List_ptr())
{
moon_pos = (*A_mult_ptr[level])[*moon_node_ptr].get_position();
moon_dist = (*A_mult_ptr[level])[*moon_node_ptr].get_dedicated_sun_distance();
lambda = sun_dist/moon_dist;
new_pos = get_waggled_inbetween_position(sun_pos,moon_pos,lambda);
L.pushBack(new_pos);
}
if (!(*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()->empty())
{
lambdaIterator = (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()->begin();
forall_listiterators(node,adj_sun_ptr,*(*A_mult_ptr[level])[*v_ptr].
get_neighbour_sun_node_List_ptr())
{
lambda = *lambdaIterator;
adj_sun_pos = (*A_mult_ptr[level])[*adj_sun_ptr].get_position();
new_pos = get_waggled_inbetween_position(sun_pos,adj_sun_pos,lambda);
L.pushBack(new_pos);
if(lambdaIterator != (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()
->rbegin())
lambdaIterator = (*A_mult_ptr[level])[*v_ptr].get_lambda_List_ptr()
->cyclicSucc(lambdaIterator);
}
}
(*A_mult_ptr[level])[*v_ptr].set_position(get_barycenter_position(L));
(*A_mult_ptr[level])[*v_ptr].place();
}//forall
}
inline DPoint Multilevel::create_random_pos(DPoint center,double radius,double angle_1,
double angle_2)
{
const int BILLION = 1000000000;
DPoint new_point;
double rnd = double(randomNumber(1,BILLION)+1)/(BILLION+2);//rand number in (0,1)
double rnd_angle = angle_1 +(angle_2-angle_1)*rnd;
double dx = cos(rnd_angle) * radius;
double dy = sin(rnd_angle) * radius;
new_point.m_x = center.m_x + dx ;
new_point.m_y = center.m_y + dy;
return new_point;
}
inline DPoint Multilevel::get_waggled_inbetween_position(DPoint s, DPoint t, double lambda)
{
const double WAGGLEFACTOR = 0.05;
const int BILLION = 1000000000;
DPoint inbetween_point;
inbetween_point.m_x = s.m_x + lambda*(t.m_x - s.m_x);
inbetween_point.m_y = s.m_y + lambda*(t.m_y - s.m_y);
double radius = WAGGLEFACTOR * (t-s).norm();
double rnd = double(randomNumber(1,BILLION)+1)/(BILLION+2);//rand number in (0,1)
double rand_radius = radius * rnd;
return create_random_pos(inbetween_point,rand_radius,0,6.2831853);
}
inline DPoint Multilevel::get_barycenter_position(List& L)
{
DPoint sum (0,0);
DPoint barycenter;
forall_listiterators(DPoint, act_point_ptr,L)
sum = sum + (*act_point_ptr);
barycenter.m_x = sum.m_x/L.size();
barycenter.m_y = sum.m_y/L.size();
return barycenter;
}
inline DPoint Multilevel::calculate_position(DPoint P, DPoint Q, double dist_P, double dist_Q)
{
double dist_PQ = (P-Q).norm();
double lambda = (dist_P + (dist_PQ - dist_P - dist_Q)/2)/dist_PQ;
return get_waggled_inbetween_position(P,Q,lambda);
}
void Multilevel::delete_multilevel_representations(
Array &G_mult_ptr,
Array*> &A_mult_ptr,
Array*> &E_mult_ptr,
int max_level)
{
for(int i=1; i<= max_level; i++)
{
delete G_mult_ptr[i];
delete A_mult_ptr[i];
delete E_mult_ptr[i];
}
}
double Multilevel::angle(DPoint& P, DPoint& Q, DPoint& R)
{
double dx1 = Q.m_x - P.m_x;
double dy1 = Q.m_y - P.m_y;
double dx2 = R.m_x - P.m_x;
double dy2 = R.m_y - P.m_y;
double fi;//the angle
if ((dx1 == 0 && dy1 == 0) || (dx2 == 0 && dy2 == 0))
cout<<"Multilevel::angle()"<= 1.0 ) fi = 0;
if (cosfi <= -1.0 ) fi = Math::pi;
else
{
fi = acos(cosfi);
if (dx1*dy2 < dy1*dx2) fi = -fi;
if (fi < 0) fi += 2*Math::pi;
}
return fi;
}
}//namespace ogdf