The planarization layout algorithm. More...

#include <ogdf/planarity/PlanarizationLayout.h>

Inheritance diagram for ogdf::PlanarizationLayout:

Public Member Functions
	PlanarizationLayout ()
	Creates an instance of planarization layout and sets options to default values.
virtual	~PlanarizationLayout ()
Algorithm call

void	call (GraphAttributes &GA)
	Calls planarization layout for graph attributes GA and computes a layout.
virtual void	call (UMLGraph &umlGraph)
	Calls planarization layout for UML-graph umlGraph and computes a mixed-upward layout.
void	simpleCall (UMLGraph &umlGraph)
	Simple call function that does not care about cliques etc.
virtual void	callSimDraw (UMLGraph &umlGraph)
	Call for simultaneous drawing with graph umlGraph.
virtual void	callFixEmbed (UMLGraph &umlGraph)
	Calls planarization layout with fixed embedding given by umlGraph.
virtual void	callIncremental (UMLGraph &umlgraph, NodeArray< bool > &fixedNodes, const EdgeArray< bool > &fixedEdges)
Optional parameters

double	pageRatio () const
	Returns the current setting of option pageRatio.
void	pageRatio (double ratio)
	Sets the option pageRatio to ratio.
bool	preprocessCliques () const
	Returns the current setting of option preprocessCliques.
void	preprocessCliques (bool b)
	Sets the option preProcessCliques to b.
int	minCliqueSize () const
	Returns the current setting of option minCliqueSize.
void	minCliqueSize (int i)
	Set the option minCliqueSize to i.
void	setLayouterOptions (int ops)
void	alignSons (bool b)
Module options

void	setSubgraph (PlanarSubgraphModule *pSubgraph)
	Sets the module option for the computation of the planar subgraph.
void	setInserter (EdgeInsertionModule *pInserter)
	Sets the module option for edge insertion.
void	setEmbedder (EmbedderModule *pEmbedder)
	Sets the module option for the graph embedding algorithm.
void	setPlanarLayouter (LayoutPlanRepModule *pPlanarLayouter)
	Sets the module option for the planar layout algorithm.
void	setPacker (CCLayoutPackModule *pPacker)
	Sets the module option for the arrangement of connected components.
Further information

int	numberOfCrossings () const
	Returns the number of crossings in computed layout.
void	assureDrawability (UMLGraph &umlGraph)
	Throws a PreconditionViolatedException if umlGraph violates a precondition of planarization layout.
Protected Member Functions
void	doSimpleCall (GraphAttributes pGA, UMLGraph pUmlGraph)
void	sortIncrementalNodes (List< node > &addNodes, const NodeArray< bool > &fixedNodes)
void	getFixationDistance (node startNode, HashArray< int, int > &distance, const NodeArray< bool > &fixedNodes)
void	reembed (PlanRepUML &PG, int ccNumber, bool l_align=false, bool l_gensExist=false)
virtual void	preProcess (UMLGraph &UG)
virtual void	postProcess (UMLGraph &UG)
void	fillAdjNodes (List< node > &adjNodes, PlanRepUML &PG, node centerNode, NodeArray< bool > &isClique, Layout &drawing)
void	arrangeCCs (PlanRep &PG, GraphAttributes &GA, Array< DPoint > &boundingBox)
Private Member Functions
face	findBestExternalFace (const PlanRep &PG, const CombinatorialEmbedding &E)
Private Attributes
ModuleOption < PlanarSubgraphModule >	m_subgraph
	The module for computing a planar subgraph.
ModuleOption< EdgeInsertionModule >	m_inserter
	The module for edge re-insertion.
ModuleOption< EmbedderModule >	m_embedder
	The module for planar embedding.
ModuleOption< LayoutPlanRepModule >	m_planarLayouter
	The module for computing a planar layout.
ModuleOption< CCLayoutPackModule >	m_packer
	The module for arranging connected components.
double	m_pageRatio
	The desired page ratio.
int	m_nCrossings
	The number of crossings in the computed layout.
bool	m_arrangeLabels
	Option for re-arranging labels.
bool	m_processCliques
	Option for preprocessing cliques (not UML layout).
int	m_cliqueSize
	The minimum size of cliques to search for.
List< edge >	m_fakedGens
bool	m_fakeTree

Detailed Description

The planarization layout algorithm.

The class PlanarizationLayout represents a customizable implementation of the planarization approach for drawing graphs. The class provides three different algorithm calls:

Calling the algorithm for a usual graph (call with GraphAttributes).
Calling the algorithm for a mixed-upward graph (e.g., a UML class diagram; call with UMLGraph); a simplified version is provided by simpleCall().
Calling the algorithm for simultaneous drawing.

If the planarization layout algorithm shall be used for simultaneous drawing, you need to define the different subgraphs by setting the subgraphs option.

The implementation used in PlanarizationLayout is based on the following publication:

C. Gutwenger, P. Mutzel: An Experimental Study of Crossing Minimization Heuristics. 11th International Symposium on Graph Drawing 2003, Perugia (GD '03), LNCS 2912, pp. 13-24, 2004.

Optional parameters

Option	Type	Default	Description
pageRatio	double	1.0	Specifies the desired ration of width / height of the computed layout. It is currently only used when packing connected components.
preprocessCliques	bool	false	If set to true, a preprocessing for cliques (complete subgraphs) is performed and cliques will be laid out in a special form (straight-line, not orthogonal). The preprocessing may reduce running time and improve layout quality if the input graphs contains dense subgraphs.
minCliqueSize	int	10	If preprocessing of cliques is enabled, this option determines the minimal size of cliques to search for.

Module options

The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:

Option	Type	Default	Description
subgraph	PlanarSubgraphModule	FastPlanarSubgraph	The module for the computation of the planar subgraph.
inserter	EdgeInsertionModule	FixedEmbeddingInserter	The module used for edge insertion which is applied in the second step of the planarization method. The edges not contained in the planar subgraph are re-inserted one-by-one, each with as few crossings as possible.
embedder	EmbedderModule	SimpleEmbedder	The graph embedding algorithm applied after the crossing minimization step.
planarLayouter	LayoutPlanRepModule	OrthoLayout	The planar layout algorithm used to compute a planar layout of the planarized representation resulting from the crossing minimization step.
packer	CCLayoutPackModule	TileToRowsCCPacker	The packer module used for arranging connected components.

Definition at line 141 of file PlanarizationLayout.h.

Constructor & Destructor Documentation

ogdf::PlanarizationLayout::PlanarizationLayout ( )

Creates an instance of planarization layout and sets options to default values.

virtual ogdf::PlanarizationLayout::~PlanarizationLayout ( ) [inline, virtual]

Definition at line 69 of file PlanarizationLayout.h.

Member Function Documentation

void ogdf::PlanarizationLayout::alignSons ( bool b ) [inline]

Definition at line 176 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::arrangeCCs	(	PlanRep &	PG,
		GraphAttributes &	GA,
		Array< DPoint > &	boundingBox
	)			`[protected]`

void ogdf::PlanarizationLayout::assureDrawability ( UMLGraph & umlGraph )

Throws a PreconditionViolatedException if umlGraph violates a precondition of planarization layout.

virtual void ogdf::PlanarizationLayout::call ( UMLGraph & umlGraph ) [virtual]

Calls planarization layout for UML-graph umlGraph and computes a mixed-upward layout.

Precondition:: The graph has no self-loops.

Parameters:

umlGraph

is the input graph and will also be assigned the layout information.

Implements ogdf::UMLLayoutModule.

void ogdf::PlanarizationLayout::call ( GraphAttributes & GA ) [inline, virtual]

Calls planarization layout for graph attributes GA and computes a layout.

Precondition:: The graph has no self-loops.

Parameters:

GA

is the input graph and will also be assigned the layout information.

Implements ogdf::LayoutModule.

Definition at line 81 of file PlanarizationLayout.h.

virtual void ogdf::PlanarizationLayout::callFixEmbed ( UMLGraph & umlGraph ) [virtual]

Calls planarization layout with fixed embedding given by umlGraph.

Precondition:: The graph has no self-loops.

Parameters:

umlGraph

is the input graph and will also be assigned the layout information. The fixed embedding is obtained from the layout information (node coordinates, bend points) in umlGraph.

virtual void ogdf::PlanarizationLayout::callIncremental	(	UMLGraph &	umlgraph,
		NodeArray< bool > &	fixedNodes,
		const EdgeArray< bool > &	fixedEdges
	)			`[virtual]`

virtual void ogdf::PlanarizationLayout::callSimDraw ( UMLGraph & umlGraph ) [virtual]

Call for simultaneous drawing with graph umlGraph.

void ogdf::PlanarizationLayout::doSimpleCall	(	GraphAttributes *	pGA,
		UMLGraph *	pUmlGraph
	)			`[protected]`

void ogdf::PlanarizationLayout::fillAdjNodes	(	List< node > &	adjNodes,
		PlanRepUML &	PG,
		node	centerNode,
		NodeArray< bool > &	isClique,
		Layout &	drawing
	)			`[protected]`

face ogdf::PlanarizationLayout::findBestExternalFace	(	const PlanRep &	PG,
		const CombinatorialEmbedding &	E
	)			`[private]`

void ogdf::PlanarizationLayout::getFixationDistance	(	node	startNode,
		HashArray< int, int > &	distance,
		const NodeArray< bool > &	fixedNodes
	)			`[protected]`

int ogdf::PlanarizationLayout::minCliqueSize ( ) const [inline]

Returns the current setting of option minCliqueSize.

If preprocessing of cliques is enabled, this option determines the minimal size of cliques to search for.

Definition at line 162 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::minCliqueSize ( int i ) [inline]

Set the option minCliqueSize to i.

Definition at line 167 of file PlanarizationLayout.h.

int ogdf::PlanarizationLayout::numberOfCrossings ( ) const [inline]

Returns the number of crossings in computed layout.

Definition at line 254 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::pageRatio ( double ratio ) [inline]

Sets the option pageRatio to ratio.

Definition at line 134 of file PlanarizationLayout.h.

double ogdf::PlanarizationLayout::pageRatio ( ) const [inline]

Returns the current setting of option pageRatio.

This option specifies the desired ration width / height of the computed layout. It is currently only used for packing connected components.

Definition at line 129 of file PlanarizationLayout.h.

virtual void ogdf::PlanarizationLayout::postProcess ( UMLGraph & UG ) [protected, virtual]

virtual void ogdf::PlanarizationLayout::preProcess ( UMLGraph & UG ) [protected, virtual]

bool ogdf::PlanarizationLayout::preprocessCliques ( ) const [inline]

Returns the current setting of option preprocessCliques.

If this option is enabled (set to true), a preprocessing for cliques (complete subgraphs) is performed and cliques will be laid out in a special form (straight-line, not orthogonal). The preprocessing may reduce running time and improve layout quality if the input graphs contains dense subgraphs.

Definition at line 147 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::preprocessCliques ( bool b ) [inline]

Sets the option preProcessCliques to b.

Definition at line 152 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::reembed	(	PlanRepUML &	PG,
		int	ccNumber,
		bool	l_align = `false`,
		bool	l_gensExist = `false`
	)			`[protected]`

void ogdf::PlanarizationLayout::setEmbedder ( EmbedderModule * pEmbedder ) [inline]

Sets the module option for the graph embedding algorithm.

The result of the crossing minimization step is a planar graph, in which crossings are replaced by dummy nodes. The embedding module then computes a planar embedding of this planar graph.

Definition at line 219 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::setInserter ( EdgeInsertionModule * pInserter ) [inline]

Sets the module option for edge insertion.

The edge insertion module is applied in the second step of the planarization method. The edges not contained in the planar subgraph are re-inserted one-by-one, each with as few crossings as possible. The edge insertion module implements the whole second step, i.e., it inserts all edges.

Definition at line 208 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::setLayouterOptions ( int ops ) [inline]

Definition at line 172 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::setPacker ( CCLayoutPackModule * pPacker ) [inline]

Sets the module option for the arrangement of connected components.

The planarization layout algorithm draws each connected component of the input graph seperately, and then arranges the resulting drawings using a packing algorithm.

Definition at line 244 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::setPlanarLayouter ( LayoutPlanRepModule * pPlanarLayouter ) [inline]

Sets the module option for the planar layout algorithm.

The planar layout algorithm is used to compute a planar layout of the planarized representation resulting from the crossing minimization step. Planarized representation means that edge crossings are replaced by dummy nodes of degree four, so the actual layout algorithm obtains a planar graph as input. By default, the planar layout algorithm produces an orthogonal drawing.

Definition at line 233 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::setSubgraph ( PlanarSubgraphModule * pSubgraph ) [inline]

Sets the module option for the computation of the planar subgraph.

The computation of a planar subgraph is the first step in the crossing minimization procedure of the planarization approach.

Definition at line 196 of file PlanarizationLayout.h.

void ogdf::PlanarizationLayout::simpleCall ( UMLGraph & umlGraph ) [inline]

Simple call function that does not care about cliques etc.

Definition at line 93 of file PlanarizationLayout.h.