Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::MixedModelLayout Class Reference

Implementation of the Mixed-Model layout algorithm. More...

#include <ogdf/planarlayout/MixedModelLayout.h>

+ Inheritance diagram for ogdf::MixedModelLayout:

Public Member Functions

 MixedModelLayout ()
 Constructs an instance of the Mixed-Model layout algorithm. More...
 
virtual ~MixedModelLayout ()
 
Module options
void setAugmenter (AugmentationModule *pAugmenter)
 Sets the augmentation module. More...
 
void setShellingOrder (ShellingOrderModule *pOrder)
 Sets the shelling order module. More...
 
void setCrossingsBeautifier (MixedModelCrossingsBeautifierModule *pBeautifier)
 Sets the crossings beautifier module. More...
 
void setEmbedder (EmbedderModule *pEmbedder)
 Sets the module option for the graph embedding algorithm. More...
 
- Public Member Functions inherited from ogdf::GridLayoutPlanRepModule
 GridLayoutPlanRepModule ()
 Initializes a plan-rep grid layout module. More...
 
virtual ~GridLayoutPlanRepModule ()
 
void callGrid (const Graph &G, GridLayout &gridLayout)
 Calls the grid layout algorithm (call for GridLayout). More...
 
void callGrid (PlanRep &PG, GridLayout &gridLayout)
 Calls the grid layout algorithm (call for GridLayout of a PlanRep). 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...
 
void callGridFixEmbed (PlanRep &PG, GridLayout &gridLayout, adjEntry adjExternal=0)
 Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout of a PlanRep). 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...
 

Protected Member Functions

void doCall (PlanRep &PG, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding)
 Implements the algorithm call. More...
 
- Protected Member Functions inherited from ogdf::GridLayoutPlanRepModule
void doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding)
 Implements PlanarGridLayoutModule::doCall(). More...
 
void doCall (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox)
 Implements the GridLayoutModule::doCall(). More...
 

Private Attributes

ModuleOption< AugmentationModulem_augmenter
 The augmentation module. More...
 
ModuleOption< ShellingOrderModulem_compOrder
 The shelling order module. More...
 
ModuleOption< MixedModelCrossingsBeautifierModulem_crossingsBeautifier
 The crossings beautifier module. More...
 
ModuleOption< EmbedderModulem_embedder
 The planar embedder module. More...
 

Additional Inherited Members

- Protected Attributes inherited from ogdf::GridLayoutModule
IPoint m_gridBoundingBox
 The computed bounding box of the grid layout. More...
 

Detailed Description

Implementation of the Mixed-Model layout algorithm.

The class MixedModelLayout represents the Mixed-Model layout algorithm by Gutwenger and Mutzel, which is based upon ideas by Kant. In particular, Kant's algorithm has been changed concerning the placement phase and the vertex boxes, and it has been generalized to work for connected planar graphs.

This algorithm draws a d-planar graph G on a grid such that every edge has at most three bends and the minimum angle between two edges is at least 2/d radians. G must not contain self-loops or multiple edges. The grid size is at most (2n-6) * (3/2n-7/2), the number of bends is at most 5n-15, and every edge has length O(n), where G has n nodes.

The algorithm runs in several phases. In the preprocessing phase, vertices with degree one are temporarily deleted and the graph is being augmented to a biconnected planar graph using a planar biconnectivity augmentation module. Then, a shelling order for biconnected plane graphs is computed. In the next step, boxes around each vertex are defined in such a way that the incident edges appear regularly along the box. Finally, the coordinates of the vertex boxes are computed taking the degree-one vertices into account.

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

C. Gutwenger, P. Mutzel: Planar Polyline Drawings with Good Angular Resolution. 6th International Symposium on Graph Drawing 1998, Montreal (GD '98), LNCS 1547, pp. 167-182, 1998.

Precondition

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

Module options

Instances of type MixedModelLayout 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!
crossingsBeautifierMixedModelCrossingsBeautifierModuleMMDummyCrossingsBeautifier The crossing beautifier is applied as preprocessing to dummy nodes in the graph that actually represent crossings. Such nodes arise when using the mixed-model layout algorithm in the planarization approach (see PlanarizationGridLayout). By default, crossings might look weird, since they are not drawn as two crossing horizontal and vertical lines; the other available crossings beautifier correct this.

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 132 of file MixedModelLayout.h.

Constructor & Destructor Documentation

ogdf::MixedModelLayout::MixedModelLayout ( )

Constructs an instance of the Mixed-Model layout algorithm.

virtual ogdf::MixedModelLayout::~MixedModelLayout ( )
inlinevirtual

Definition at line 138 of file MixedModelLayout.h.

Member Function Documentation

void ogdf::MixedModelLayout::doCall ( PlanRep PG,
adjEntry  adjExternal,
GridLayout gridLayout,
IPoint boundingBox,
bool  fixEmbedding 
)
protectedvirtual

Implements the algorithm call.

Implements ogdf::GridLayoutPlanRepModule.

void ogdf::MixedModelLayout::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 151 of file MixedModelLayout.h.

void ogdf::MixedModelLayout::setCrossingsBeautifier ( MixedModelCrossingsBeautifierModule pBeautifier)
inline

Sets the crossings beautifier module.

Definition at line 161 of file MixedModelLayout.h.

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

Sets the module option for the graph embedding algorithm.

Definition at line 166 of file MixedModelLayout.h.

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

Sets the shelling order module.

Definition at line 156 of file MixedModelLayout.h.

Member Data Documentation

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

The augmentation module.

Definition at line 183 of file MixedModelLayout.h.

ModuleOption<ShellingOrderModule> ogdf::MixedModelLayout::m_compOrder
private

The shelling order module.

Definition at line 184 of file MixedModelLayout.h.

ModuleOption<MixedModelCrossingsBeautifierModule> ogdf::MixedModelLayout::m_crossingsBeautifier
private

The crossings beautifier module.

Definition at line 185 of file MixedModelLayout.h.

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

The planar embedder module.

Definition at line 182 of file MixedModelLayout.h.


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