Open
Graph Drawing
Framework

 v.2007.11
 

ogdf::PlanarDrawLayout Class Reference

Implementation of the Planar-Draw layout algorithm. More...

#include <PlanarDrawLayout.h>

Inheritance diagram for ogdf::PlanarDrawLayout:

ogdf::PlanarGridLayoutModule ogdf::GridLayoutModule ogdf::LayoutModule

List of all members.

Public Member Functions

 PlanarDrawLayout ()
 Constructs an instance of the Planar-Draw layout algorithm.
 ~PlanarDrawLayout ()
Optional parameters
bool sizeOptimization () const
 Returns the current setting of option sizeOptimization.
void sizeOptimization (bool opt)
 Sets the option sizeOptimization to opt.
bool sideOptimization () const
 Returns the current setting of option sideOptimization.
void sideOptimization (bool opt)
 Sets the option sideOptimization to opt.
double baseRatio () const
 Returns the current setting of option baseRatio.
void baseRatio (double ratio)
 Sets the option baseRatio to ratio.
Module options
void setAugmenter (AugmentationModule *pAugmenter)
 Sets the augmentation module.
void setShellingOrder (ShellingOrderModule *pOrder)
 Sets the shelling order module.

Private Member Functions

void doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding)
 Implements the algorithm call.
void computeCoordinates (const Graph &G, ShellingOrder &order, NodeArray< int > &x, NodeArray< int > &y)

Private Attributes

bool m_sizeOptimization
 The option for allowing arbitrary slopes.
bool m_sideOptimization
 The option for size optimization.
double m_baseRatio
 The option for specifying the base ratio.
ModuleOption< AugmentationModulem_augmenter
 The augmentation module.
ModuleOption< ShellingOrderModulem_computeOrder
 The shelling order module.


Detailed Description

Implementation of the Planar-Draw layout algorithm.

The class PlanarDrawLayout implements a straight-line drawing algorithm for planar graphs. It draws a planar graph on a grid of size at most (n-2) * (n-2) without edge crossings.

The algorithm runs in several phases. In the first phase, the graph is augmented by adding edges to achieve a certain connectivity (e.g., biconnected or triconnected). Then, a shelling order of the the resulting graph is computed. Both phases are implemented by using module options, so you can replace them with different implementations. However, you have to make sure, that the connectivity achieved by the augmentation module is sufficient for the shelling order module (or the input graph already has the required connectivity).

The implementation used in PlanarDrawLayout is an improved version of the following publication:

M. Chrobak, G. Kant: Convex Grid Drawings of 3-connected Planar Graphs. International Journal of Computational Geometry and Applications 7(3), pp. 211-223, 1997.

Precondition

The input graph needs to be planar and simple (i.e., no self-loops and no multiple edges).

Optional parameters

OptionTypeDefaultDescription
sizeOptimizationbooltrue If this option is set to true, the algorithm tries to reduce the size of the resulting grid layout.
sideOptimizationboolfalse If this option is set to true, slopes different from +1, 0, -1 are allowed on the contour for reducing the resulting grid size.
baseRatiodouble0.33 This option specifies the maximal number of nodes placed on the base line. The algorithm tries to place as many nodes as possible on the base line, but takes at most max(2, baseRatio * size of external face) many.

Module options

Instances of type PlanarDrawLayout provide the following module options:

OptionTypeDefaultDescription
augmenterAugmentationModulePlanarAugmentation Augments the graph by adding edges to obtain a planar graph with a certain connectivity (e.g., biconnected or triconnected).
shellingOrderShellingOrderModuleBiconnectedShellingOrder The algorithm to compute a shelling order. The connectivity assured by the planar augmentation module has to be sufficient for the shelling order module!

Running Time

The computation of the layout takes time O(n), where n is the number of nodes of the input graph.

Definition at line 141 of file PlanarDrawLayout.h.


Constructor & Destructor Documentation

ogdf::PlanarDrawLayout::PlanarDrawLayout (  ) 

Constructs an instance of the Planar-Draw layout algorithm.

ogdf::PlanarDrawLayout::~PlanarDrawLayout (  )  [inline]

Definition at line 147 of file PlanarDrawLayout.h.


Member Function Documentation

bool ogdf::PlanarDrawLayout::sizeOptimization (  )  const [inline]

Returns the current setting of option sizeOptimization.

If this option is set to true, the algorithm tries to reduce the size of the resulting grid layout.

Definition at line 161 of file PlanarDrawLayout.h.

void ogdf::PlanarDrawLayout::sizeOptimization ( bool  opt  )  [inline]

Sets the option sizeOptimization to opt.

Definition at line 164 of file PlanarDrawLayout.h.

bool ogdf::PlanarDrawLayout::sideOptimization (  )  const [inline]

Returns the current setting of option sideOptimization.

If this option is set to true, slopes different from +1, 0, -1 are allowed on the contour for reducing the resulting grid size.

Definition at line 172 of file PlanarDrawLayout.h.

void ogdf::PlanarDrawLayout::sideOptimization ( bool  opt  )  [inline]

Sets the option sideOptimization to opt.

Definition at line 175 of file PlanarDrawLayout.h.

double ogdf::PlanarDrawLayout::baseRatio (  )  const [inline]

Returns the current setting of option baseRatio.

This option specifies the maximal number of nodes placed on the base line. The algorithm tries to place as many nodes as possible on the base line, but takes at most max(2, baseRatio * size of external face) many.

Definition at line 184 of file PlanarDrawLayout.h.

void ogdf::PlanarDrawLayout::baseRatio ( double  ratio  )  [inline]

Sets the option baseRatio to ratio.

Definition at line 187 of file PlanarDrawLayout.h.

void ogdf::PlanarDrawLayout::setAugmenter ( AugmentationModule pAugmenter  )  [inline]

Sets the augmentation module.

The augmentation module needs to make sure that the graph gets the connectivity required for calling the shelling order module.

Definition at line 201 of file PlanarDrawLayout.h.

void ogdf::PlanarDrawLayout::setShellingOrder ( ShellingOrderModule pOrder  )  [inline]

Sets the shelling order module.

Definition at line 206 of file PlanarDrawLayout.h.

void ogdf::PlanarDrawLayout::doCall ( const Graph G,
adjEntry  adjExternal,
GridLayout gridLayout,
IPoint boundingBox,
bool  fixEmbedding 
) [private, virtual]

Implements the algorithm call.

A derived algorithm must implement this method and return the computed grid layout in gridLayout.

Parameters:
G is the input graph.
adjExternal is an adjacency entry on the external face, or 0 if no external face is specified.
gridLayout is assigned the computed grid layout.
boundingBox returns the bounding box of the grid layout. The lower left corner of the bounding box is always (0,0), thus this IPoint defines the upper right corner as well as the width and height of the grid layout.
fixEmbedding determines if the input graph is embedded and that embedding has to be preserved (true), or if an embedding needs to be computed (false).

Implements ogdf::PlanarGridLayoutModule.

void ogdf::PlanarDrawLayout::computeCoordinates ( const Graph G,
ShellingOrder order,
NodeArray< int > &  x,
NodeArray< int > &  y 
) [private]


Member Data Documentation

bool ogdf::PlanarDrawLayout::m_sizeOptimization [private]

The option for allowing arbitrary slopes.

Definition at line 213 of file PlanarDrawLayout.h.

bool ogdf::PlanarDrawLayout::m_sideOptimization [private]

The option for size optimization.

Definition at line 214 of file PlanarDrawLayout.h.

double ogdf::PlanarDrawLayout::m_baseRatio [private]

The option for specifying the base ratio.

Definition at line 215 of file PlanarDrawLayout.h.

ModuleOption<AugmentationModule> ogdf::PlanarDrawLayout::m_augmenter [private]

The augmentation module.

Definition at line 217 of file PlanarDrawLayout.h.

ModuleOption<ShellingOrderModule> ogdf::PlanarDrawLayout::m_computeOrder [private]

The shelling order module.

Definition at line 218 of file PlanarDrawLayout.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:14 2007 by doxygen 1.5.4.