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 51 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:

• include/ogdf/energybased/fmmm/Multilevel.h