Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::energybased::fmmm::Multilevel Class Reference

#include <ogdf/energybased/fmmm/Multilevel.h>

Public Member Functions

void create_multilevel_representations (Graph &G, NodeArray< NodeAttributes > &A, EdgeArray< EdgeAttributes > &E, int rand_seed, FMMMOptions::GalaxyChoice galaxy_choice, int min_Graph_size, int rand_tries, Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, int &max_level)
 The multilevel representations *G_mult_ptr/*A_mult_ptr/*E_mult_ptr for G/A/E are created. The maximum multilevel is calculated, too. More...
 
void delete_multilevel_representations (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, int max_level)
 Free dynamically allocated memory. More...
 
void find_initial_placement_for_level (int level, FMMMOptions::InitialPlacementMult init_placement_way, Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr)
 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. More...
 

Private Member Functions

void calculate_mass_of_collapsed_nodes (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_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. More...
 
DPoint calculate_position (DPoint P, DPoint Q, double dist_P, double dist_Q)
 Creates a waggled position on the line PQ, depending on dist_P and dist_Q needed in case init_placement_way() == 1. More...
 
void collaps_solar_systems (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &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. More...
 
void create_all_placement_sectors (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, int level)
 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. More...
 
void create_edges_edgedistances_and_lambda_Lists (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, EdgeArray< double > &new_edgelength, 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). More...
 
void create_moon_nodes_and_pm_nodes (const Graph &G_mult, NodeArray< NodeAttributes > &A_mult, EdgeArray< EdgeAttributes > &E_mult)
 Partitions the nodes of G_mult 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. More...
 
DPoint create_random_pos (DPoint center, double radius, double angle_1, double angle_2)
 Returns a random point with radius radius between angle_1 and angle_2. More...
 
void create_suns_and_planets (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, int rand_seed, FMMMOptions::GalaxyChoice 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) More...
 
void delete_parallel_edges_and_update_edgelength (Array< Graph * > &G_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, EdgeArray< double > &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. More...
 
bool edgenumbersum_of_all_levels_is_linear (Array< Graph * > &G_mult_ptr, int act_level, int &bad_edgenr_counter)
 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. More...
 
DPoint get_barycenter_position (List< DPoint > &L)
 Returns the barycenter position of all points in L (the mass of all point is regarded as equal). More...
 
DPoint get_waggled_inbetween_position (DPoint s, DPoint t, double lambda)
 Returns roughtly the position s +lambda*(t-s) + some random waggling. More...
 
void init_multilevel_values (const Graph &G_mult, NodeArray< NodeAttributes > &A_mult, EdgeArray< EdgeAttributes > &E_mult)
 Sets the default multilevel values for all nodes and edges in G_mult. More...
 
void partition_galaxy_into_solar_systems (Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, int rand_seed, FMMMOptions::GalaxyChoice galaxy_choice, int random_tries, int act_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. More...
 
void set_initial_positions_of_planet_and_moon_nodes (int level, FMMMOptions::InitialPlacementMult init_placement_way, Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, List< node > &pm_nodes)
 The initial positions of the planet/moon_nodes at level level are calculated here and a list of all pm_nodes is returned. More...
 
void set_initial_positions_of_pm_nodes (int level, FMMMOptions::InitialPlacementMult init_placement_way, Array< NodeArray< NodeAttributes > * > &A_mult_ptr, Array< EdgeArray< EdgeAttributes > * > &E_mult_ptr, List< node > &pm_nodes)
 The initial positions of the pm nodes are calculated by the position of the dedicated sun and moon_nodes. More...
 
void set_initial_positions_of_sun_nodes (int level, Array< Graph * > &G_mult_ptr, Array< NodeArray< NodeAttributes > * > &A_mult_ptr)
 The initial positions of all sun_nodes at level level are set. More...
 

Detailed Description

Definition at line 47 of file Multilevel.h.

Member Function Documentation

◆ calculate_mass_of_collapsed_nodes()

void ogdf::energybased::fmmm::Multilevel::calculate_mass_of_collapsed_nodes ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
int  act_level 
)
private

The mass of all nodes at level act_level+1 is set to the mass of its dedicated solar_system at level act_level.

◆ calculate_position()

DPoint ogdf::energybased::fmmm::Multilevel::calculate_position ( DPoint  P,
DPoint  Q,
double  dist_P,
double  dist_Q 
)
private

Creates a waggled position on the line PQ, depending on dist_P and dist_Q needed in case init_placement_way() == 1.

◆ collaps_solar_systems()

void ogdf::energybased::fmmm::Multilevel::collaps_solar_systems ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
int  act_level 
)
private

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.

◆ create_all_placement_sectors()

void ogdf::energybased::fmmm::Multilevel::create_all_placement_sectors ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
int  level 
)
private

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.

◆ create_edges_edgedistances_and_lambda_Lists()

void ogdf::energybased::fmmm::Multilevel::create_edges_edgedistances_and_lambda_Lists ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
EdgeArray< double > &  new_edgelength,
int  act_level 
)
private

The edges , new_edgelength and the lambda lists at level act_level+1 are created (the graph may contain parallel edges afterwards).

◆ create_moon_nodes_and_pm_nodes()

void ogdf::energybased::fmmm::Multilevel::create_moon_nodes_and_pm_nodes ( const Graph G_mult,
NodeArray< NodeAttributes > &  A_mult,
EdgeArray< EdgeAttributes > &  E_mult 
)
private

Partitions the nodes of G_mult 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.

◆ create_multilevel_representations()

void ogdf::energybased::fmmm::Multilevel::create_multilevel_representations ( Graph G,
NodeArray< NodeAttributes > &  A,
EdgeArray< EdgeAttributes > &  E,
int  rand_seed,
FMMMOptions::GalaxyChoice  galaxy_choice,
int  min_Graph_size,
int  rand_tries,
Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
int &  max_level 
)

The multilevel representations *G_mult_ptr/*A_mult_ptr/*E_mult_ptr for G/A/E are created. The maximum multilevel is calculated, too.

◆ create_random_pos()

DPoint ogdf::energybased::fmmm::Multilevel::create_random_pos ( DPoint  center,
double  radius,
double  angle_1,
double  angle_2 
)
private

Returns a random point with radius radius between angle_1 and angle_2.

◆ create_suns_and_planets()

void ogdf::energybased::fmmm::Multilevel::create_suns_and_planets ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
int  rand_seed,
FMMMOptions::GalaxyChoice  galaxy_choice,
int  random_tries,
int  act_level 
)
private

The sun and planet nodes are created by choosing the sun nodes randomly with uniform or weighted probability (depending on galaxy_choice)

◆ delete_multilevel_representations()

void ogdf::energybased::fmmm::Multilevel::delete_multilevel_representations ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
int  max_level 
)

Free dynamically allocated memory.

◆ delete_parallel_edges_and_update_edgelength()

void ogdf::energybased::fmmm::Multilevel::delete_parallel_edges_and_update_edgelength ( Array< Graph * > &  G_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
EdgeArray< double > &  new_edgelength,
int  act_level 
)
private

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.

◆ edgenumbersum_of_all_levels_is_linear()

bool ogdf::energybased::fmmm::Multilevel::edgenumbersum_of_all_levels_is_linear ( Array< Graph * > &  G_mult_ptr,
int  act_level,
int &  bad_edgenr_counter 
)
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.

◆ find_initial_placement_for_level()

void ogdf::energybased::fmmm::Multilevel::find_initial_placement_for_level ( int  level,
FMMMOptions::InitialPlacementMult  init_placement_way,
Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr 
)

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.

◆ get_barycenter_position()

DPoint ogdf::energybased::fmmm::Multilevel::get_barycenter_position ( List< DPoint > &  L)
private

Returns the barycenter position of all points in L (the mass of all point is regarded as equal).

◆ get_waggled_inbetween_position()

DPoint ogdf::energybased::fmmm::Multilevel::get_waggled_inbetween_position ( DPoint  s,
DPoint  t,
double  lambda 
)
private

Returns roughtly the position s +lambda*(t-s) + some random waggling.

◆ init_multilevel_values()

void ogdf::energybased::fmmm::Multilevel::init_multilevel_values ( const Graph G_mult,
NodeArray< NodeAttributes > &  A_mult,
EdgeArray< EdgeAttributes > &  E_mult 
)
private

Sets the default multilevel values for all nodes and edges in G_mult.

◆ partition_galaxy_into_solar_systems()

void ogdf::energybased::fmmm::Multilevel::partition_galaxy_into_solar_systems ( Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
int  rand_seed,
FMMMOptions::GalaxyChoice  galaxy_choice,
int  random_tries,
int  act_level 
)
private

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.

◆ set_initial_positions_of_planet_and_moon_nodes()

void ogdf::energybased::fmmm::Multilevel::set_initial_positions_of_planet_and_moon_nodes ( int  level,
FMMMOptions::InitialPlacementMult  init_placement_way,
Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
List< node > &  pm_nodes 
)
private

The initial positions of the planet/moon_nodes at level level are calculated here and a list of all pm_nodes is returned.

◆ set_initial_positions_of_pm_nodes()

void ogdf::energybased::fmmm::Multilevel::set_initial_positions_of_pm_nodes ( int  level,
FMMMOptions::InitialPlacementMult  init_placement_way,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr,
Array< EdgeArray< EdgeAttributes > * > &  E_mult_ptr,
List< node > &  pm_nodes 
)
private

The initial positions of the pm nodes are calculated by the position of the dedicated sun and moon_nodes.

◆ set_initial_positions_of_sun_nodes()

void ogdf::energybased::fmmm::Multilevel::set_initial_positions_of_sun_nodes ( int  level,
Array< Graph * > &  G_mult_ptr,
Array< NodeArray< NodeAttributes > * > &  A_mult_ptr 
)
private

The initial positions of all sun_nodes at level level are set.


The documentation for this class was generated from the following file: