#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.

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.

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.

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.

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.

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.

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.

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).

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.

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.

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)

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.

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.

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).

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

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.

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.

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.

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.

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.

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:

include/ogdf/energybased/fmmm/Multilevel.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Detailed Description

Member Function Documentation

◆ calculate_mass_of_collapsed_nodes()

◆ calculate_position()

◆ collaps_solar_systems()

◆ create_all_placement_sectors()

◆ create_edges_edgedistances_and_lambda_Lists()

◆ create_moon_nodes_and_pm_nodes()

◆ create_multilevel_representations()

◆ create_random_pos()

◆ create_suns_and_planets()

◆ delete_multilevel_representations()

◆ delete_parallel_edges_and_update_edgelength()

◆ edgenumbersum_of_all_levels_is_linear()

◆ find_initial_placement_for_level()

◆ get_barycenter_position()

◆ get_waggled_inbetween_position()

◆ init_multilevel_values()

◆ partition_galaxy_into_solar_systems()

◆ set_initial_positions_of_planet_and_moon_nodes()

◆ set_initial_positions_of_pm_nodes()

◆ set_initial_positions_of_sun_nodes()

Open
Graph Drawing
Framework