Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::PlanarStraightLayout Class Reference

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

#include <ogdf/planarlayout/PlanarStraightLayout.h>

+ Inheritance diagram for ogdf::PlanarStraightLayout:

Public Member Functions

 PlanarStraightLayout ()
 Constructs an instance of the Planar-Straight layout algorithm. More...
 
 ~PlanarStraightLayout ()
 
Optional parameters
bool sizeOptimization () const
 Returns the current setting of option sizeOptimization. More...
 
void sizeOptimization (bool opt)
 Sets the option sizeOptimization to opt. More...
 
double baseRatio () const
 Returns the current setting of option baseRatio. More...
 
void baseRatio (double ratio)
 Sets the option baseRatio to ratio. More...
 
Module options
void setAugmenter (AugmentationModule *pAugmenter)
 Sets the augmentation module. More...
 
void setShellingOrder (ShellingOrderModule *pOrder)
 Sets the shelling order module. More...
 
void setEmbedder (EmbedderModule *pEmbedder)
 Sets the module option for the graph embedding algorithm. More...
 
- Public Member Functions inherited from ogdf::PlanarGridLayoutModule
 PlanarGridLayoutModule ()
 Initializes a planar grid layout module. More...
 
virtual ~PlanarGridLayoutModule ()
 
void callFixEmbed (GraphAttributes &AG, adjEntry adjExternal=0)
 Calls the grid layout algorithm with a fixed planar embedding (general call). More...
 
void callGridFixEmbed (const Graph &G, GridLayout &gridLayout, adjEntry adjExternal=0)
 Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout). More...
 
- Public Member Functions inherited from ogdf::GridLayoutModule
 GridLayoutModule ()
 Initializes a grid layout module. More...
 
virtual ~GridLayoutModule ()
 
void call (GraphAttributes &AG)
 Calls the grid layout algorithm (general call). More...
 
void callGrid (const Graph &G, GridLayout &gridLayout)
 Calls the grid layout algorithm (call for GridLayout). More...
 
const IPointgridBoundingBox () const
 
double separation () const
 Returns the current setting of the minimum distance between nodes. More...
 
void separation (double sep)
 Sets the minimum distance between nodes. More...
 
- Public Member Functions inherited from ogdf::LayoutModule
 LayoutModule ()
 Initializes a layout module. More...
 
virtual ~LayoutModule ()
 
virtual void call (GraphAttributes &GA, GraphConstraints &GC)
 Computes a layout of graph GA wrt the constraints in GC (if applicable). More...
 
void operator() (GraphAttributes &GA)
 Computes a layout of graph GA. More...
 

Private Member Functions

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

Private Attributes

ModuleOption< AugmentationModulem_augmenter
 The augmentation module. More...
 
double m_baseRatio
 The option for specifying the base ratio. More...
 
ModuleOption< ShellingOrderModulem_computeOrder
 The shelling order module. More...
 
ModuleOption< EmbedderModulem_embedder
 The planar embedder module. More...
 
bool m_sizeOptimization
 The option for size optimization. More...
 

Additional Inherited Members

- Protected Member Functions inherited from ogdf::PlanarGridLayoutModule
virtual void doCall (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox)
 Implements the GridLayoutModule::doCall(). More...
 
- Protected Attributes inherited from ogdf::GridLayoutModule
IPoint m_gridBoundingBox
 The computed bounding box of the grid layout. More...
 

Detailed Description

Implementation of the Planar-Straight layout algorithm.

The class PlanarStraightLayout implements a straight-line drawing algorithm for planar graphs. It draws a planar graph on a grid of size at most (2n-4) * (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 PlanarStraightLayout is an improved version of an algorithm presented in:

Goos Kant: Drawing Planar Graphs Using the Canonical Ordering. Algorithmica 16(1), pp. 4-32, 1996.

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.
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).
embedderEmbedderModuleSimpleEmbedder Planar embedding algorithm applied after planar augmentation.
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 133 of file PlanarStraightLayout.h.

Constructor & Destructor Documentation

ogdf::PlanarStraightLayout::PlanarStraightLayout ( )

Constructs an instance of the Planar-Straight layout algorithm.

ogdf::PlanarStraightLayout::~PlanarStraightLayout ( )
inline

Definition at line 139 of file PlanarStraightLayout.h.

Member Function Documentation

double ogdf::PlanarStraightLayout::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 165 of file PlanarStraightLayout.h.

void ogdf::PlanarStraightLayout::baseRatio ( double  ratio)
inline

Sets the option baseRatio to ratio.

Definition at line 168 of file PlanarStraightLayout.h.

void ogdf::PlanarStraightLayout::computeCoordinates ( const Graph G,
ShellingOrder lmc,
NodeArray< int > &  x,
NodeArray< int > &  y 
)
private
void ogdf::PlanarStraightLayout::doCall ( const Graph G,
adjEntry  adjExternal,
GridLayout gridLayout,
IPoint boundingBox,
bool  fixEmbedding 
)
privatevirtual

Implements the algorithm call.

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

Parameters
Gis the input graph.
adjExternalis an adjacency entry on the external face, or 0 if no external face is specified.
gridLayoutis assigned the computed grid layout.
boundingBoxreturns 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.
fixEmbeddingdetermines 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::PlanarStraightLayout::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 182 of file PlanarStraightLayout.h.

void ogdf::PlanarStraightLayout::setEmbedder ( EmbedderModule pEmbedder)
inline

Sets the module option for the graph embedding algorithm.

Definition at line 192 of file PlanarStraightLayout.h.

void ogdf::PlanarStraightLayout::setShellingOrder ( ShellingOrderModule pOrder)
inline

Sets the shelling order module.

Definition at line 187 of file PlanarStraightLayout.h.

bool ogdf::PlanarStraightLayout::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 153 of file PlanarStraightLayout.h.

void ogdf::PlanarStraightLayout::sizeOptimization ( bool  opt)
inline

Sets the option sizeOptimization to opt.

Definition at line 156 of file PlanarStraightLayout.h.

Member Data Documentation

ModuleOption<AugmentationModule> ogdf::PlanarStraightLayout::m_augmenter
private

The augmentation module.

Definition at line 203 of file PlanarStraightLayout.h.

double ogdf::PlanarStraightLayout::m_baseRatio
private

The option for specifying the base ratio.

Definition at line 200 of file PlanarStraightLayout.h.

ModuleOption<ShellingOrderModule> ogdf::PlanarStraightLayout::m_computeOrder
private

The shelling order module.

Definition at line 204 of file PlanarStraightLayout.h.

ModuleOption<EmbedderModule> ogdf::PlanarStraightLayout::m_embedder
private

The planar embedder module.

Definition at line 202 of file PlanarStraightLayout.h.

bool ogdf::PlanarStraightLayout::m_sizeOptimization
private

The option for size optimization.

Definition at line 199 of file PlanarStraightLayout.h.


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