Open
Graph Drawing
Framework

 v.2007.11
 

ogdf::PlanarizationLayout Class Reference

The planarization layout algorithm. More...

#include <PlanarizationLayout.h>

Inheritance diagram for ogdf::PlanarizationLayout:

ogdf::UMLLayoutModule ogdf::LayoutModule

List of all members.

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< EdgeInsertionModulem_inserter
 The module for edge re-insertion.
ModuleOption< EmbedderModulem_embedder
 The module for planar embedding.
ModuleOption< LayoutPlanRepModulem_planarLayouter
 The module for computing a planar layout.
ModuleOption< CCLayoutPackModulem_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< edgem_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:

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

OptionTypeDefaultDescription
pageRatiodouble1.0 Specifies the desired ration of width / height of the computed layout. It is currently only used when packing connected components.
preprocessCliquesboolfalse 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.
minCliqueSizeint10If 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:

OptionTypeDefaultDescription
subgraphPlanarSubgraphModuleMaximalPlanarSubgraphSimple The module for the computation of the planar subgraph.
inserterEdgeInsertionModuleFixedEmbeddingInserter 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.
embedderEmbedderModuleSimpleEmbedder The graph embedding algorithm applied after the crossing minimization step.
planarLayouterLayoutPlanRepModuleOrthoLayout The planar layout algorithm used to compute a planar layout of the planarized representation resulting from the crossing minimization step.
packerCCLayoutPackModuleTileToRowsCCPacker The packer module used for arranging connected components.

Definition at line 149 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 156 of file PlanarizationLayout.h.


Member Function Documentation

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 168 of file PlanarizationLayout.h.

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::simpleCall ( UMLGraph umlGraph  )  [inline]

Simple call function that does not care about cliques etc.

Definition at line 180 of file PlanarizationLayout.h.

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

Call for simultaneous drawing with graph umlGraph.

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]

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 216 of file PlanarizationLayout.h.

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

Sets the option pageRatio to ratio.

Definition at line 221 of file PlanarizationLayout.h.

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 234 of file PlanarizationLayout.h.

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

Sets the option preProcessCliques to b.

Definition at line 239 of file PlanarizationLayout.h.

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 249 of file PlanarizationLayout.h.

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

Set the option minCliqueSize to i.

Definition at line 254 of file PlanarizationLayout.h.

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

Definition at line 259 of file PlanarizationLayout.h.

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

Definition at line 263 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 283 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 295 of file PlanarizationLayout.h.

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 306 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 320 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 331 of file PlanarizationLayout.h.

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

Returns the number of crossings in computed layout.

Definition at line 341 of file PlanarizationLayout.h.

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

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

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

void ogdf::PlanarizationLayout::sortIncrementalNodes ( List< node > &  addNodes,
const NodeArray< bool > &  fixedNodes 
) [protected]

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

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

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

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

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

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

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


Member Data Documentation

ModuleOption<PlanarSubgraphModule> ogdf::PlanarizationLayout::m_subgraph [private]

The module for computing a planar subgraph.

Definition at line 372 of file PlanarizationLayout.h.

ModuleOption<EdgeInsertionModule> ogdf::PlanarizationLayout::m_inserter [private]

The module for edge re-insertion.

Definition at line 375 of file PlanarizationLayout.h.

ModuleOption<EmbedderModule> ogdf::PlanarizationLayout::m_embedder [private]

The module for planar embedding.

Definition at line 378 of file PlanarizationLayout.h.

ModuleOption<LayoutPlanRepModule> ogdf::PlanarizationLayout::m_planarLayouter [private]

The module for computing a planar layout.

Definition at line 381 of file PlanarizationLayout.h.

ModuleOption<CCLayoutPackModule> ogdf::PlanarizationLayout::m_packer [private]

The module for arranging connected components.

Definition at line 384 of file PlanarizationLayout.h.

double ogdf::PlanarizationLayout::m_pageRatio [private]

The desired page ratio.

Definition at line 386 of file PlanarizationLayout.h.

int ogdf::PlanarizationLayout::m_nCrossings [private]

The number of crossings in the computed layout.

Definition at line 387 of file PlanarizationLayout.h.

bool ogdf::PlanarizationLayout::m_arrangeLabels [private]

Option for re-arranging labels.

Definition at line 388 of file PlanarizationLayout.h.

bool ogdf::PlanarizationLayout::m_processCliques [private]

Option for preprocessing cliques (not UML layout).

Definition at line 389 of file PlanarizationLayout.h.

int ogdf::PlanarizationLayout::m_cliqueSize [private]

The minimum size of cliques to search for.

Definition at line 390 of file PlanarizationLayout.h.

List<edge> ogdf::PlanarizationLayout::m_fakedGens [private]

Definition at line 393 of file PlanarizationLayout.h.

bool ogdf::PlanarizationLayout::m_fakeTree [private]

Definition at line 394 of file PlanarizationLayout.h.


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

© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:13 2007 by doxygen 1.5.4.