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.

virtual	~MixedModelLayout ()

Module options
void	setAugmenter (AugmentationModule *pAugmenter)
	Sets the augmentation module.

void	setShellingOrder (ShellingOrderModule *pOrder)
	Sets the shelling order module.

void	setCrossingsBeautifier (MixedModelCrossingsBeautifierModule *pBeautifier)
	Sets the crossings beautifier module.

void	setEmbedder (EmbedderModule *pEmbedder)
	Sets the module option for the graph embedding algorithm.

Public Member Functions inherited from ogdf::GridLayoutPlanRepModule
	GridLayoutPlanRepModule ()
	Initializes a plan-rep grid layout module.

virtual	~GridLayoutPlanRepModule ()

void	callGrid (const Graph &G, GridLayout &gridLayout)
	Calls the grid layout algorithm (call for GridLayout).

void	callGrid (PlanRep &PG, GridLayout &gridLayout)
	Calls the grid layout algorithm (call for GridLayout of a PlanRep).

void	callGridFixEmbed (const Graph &G, GridLayout &gridLayout, adjEntry adjExternal=nullptr)
	Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout).

void	callGridFixEmbed (PlanRep &PG, GridLayout &gridLayout, adjEntry adjExternal=nullptr)
	Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout of a PlanRep).

Public Member Functions inherited from ogdf::PlanarGridLayoutModule
	PlanarGridLayoutModule ()
	Initializes a planar grid layout module.

virtual	~PlanarGridLayoutModule ()

void	callFixEmbed (GraphAttributes &AG, adjEntry adjExternal=nullptr)
	Calls the grid layout algorithm with a fixed planar embedding (general call).

void	callGridFixEmbed (const Graph &G, GridLayout &gridLayout, adjEntry adjExternal=nullptr)
	Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout).

Public Member Functions inherited from ogdf::GridLayoutModule
	GridLayoutModule ()
	Initializes a grid layout module.

virtual	~GridLayoutModule ()

virtual void	call (GraphAttributes &GA) override final
	Calls the grid layout algorithm (general call).

void	callGrid (const Graph &G, GridLayout &gridLayout)
	Calls the grid layout algorithm (call for GridLayout).

const IPoint &	gridBoundingBox () const

double	separation () const
	Returns the current setting of the minimum distance between nodes.

void	separation (double sep)
	Sets the minimum distance between nodes.

Public Member Functions inherited from ogdf::LayoutModule
	LayoutModule ()
	Initializes a layout module.

virtual	~LayoutModule ()

void	operator() (GraphAttributes &GA)
	Computes a layout of graph `GA`.

Protected Member Functions
virtual void	doCall (PlanRep &PG, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding) override
	Implements the algorithm call.

Protected Member Functions inherited from ogdf::GridLayoutPlanRepModule
void	doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding) override
	Implements PlanarGridLayoutModule::doCall().

virtual void	doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding)=0
	Implements the algorithm call.

virtual void	doCall (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox) override
	Implements the GridLayoutModule::doCall().

Protected Member Functions inherited from ogdf::PlanarGridLayoutModule
bool	handleTrivial (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox)
	Handles the special cases of graphs with less than 3 nodes.

Private Attributes
std::unique_ptr< AugmentationModule >	m_augmenter
	The augmentation module.

std::unique_ptr< ShellingOrderModule >	m_compOrder
	The shelling order module.

std::unique_ptr< MixedModelCrossingsBeautifierModule >	m_crossingsBeautifier
	The crossings beautifier module.

std::unique_ptr< EmbedderModule >	m_embedder
	The planar embedder module.

Additional Inherited Members
Protected Attributes inherited from ogdf::GridLayoutModule
IPoint	m_gridBoundingBox
	The computed bounding box of the grid layout.

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:

Option	Type	Default	Description
augmenter	AugmentationModule	PlanarAugmentation	Augments the graph by adding edges to obtain a planar graph with a certain connectivity (e.g., biconnected or triconnected).
embedder	EmbedderModule	SimpleEmbedder	Planar embedding algorithm applied after planar augmentation.
shellingOrder	ShellingOrderModule	BiconnectedShellingOrder	The algorithm to compute a shelling order. The connectivity assured by the planar augmentation module has to be sufficient for the shelling order module!
crossingsBeautifier	MixedModelCrossingsBeautifierModule	MMDummyCrossingsBeautifier	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 113 of file MixedModelLayout.h.

Constructor & Destructor Documentation

◆ MixedModelLayout()

ogdf::MixedModelLayout::MixedModelLayout ( )

Constructs an instance of the Mixed-Model layout algorithm.

◆ ~MixedModelLayout()

virtual ogdf::MixedModelLayout::~MixedModelLayout ( )

inlinevirtual

Definition at line 118 of file MixedModelLayout.h.

Member Function Documentation

◆ doCall()

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

overrideprotectedvirtual

Implements the algorithm call.

Implements ogdf::GridLayoutPlanRepModule.

◆ setAugmenter()

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

◆ setCrossingsBeautifier()

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

inline

Sets the crossings beautifier module.

Definition at line 137 of file MixedModelLayout.h.

◆ setEmbedder()

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

inline

Sets the module option for the graph embedding algorithm.

Definition at line 142 of file MixedModelLayout.h.

◆ setShellingOrder()

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

inline

Sets the shelling order module.

Definition at line 134 of file MixedModelLayout.h.

Member Data Documentation

◆ m_augmenter

std::unique_ptr<AugmentationModule> ogdf::MixedModelLayout::m_augmenter

private

The augmentation module.

Definition at line 153 of file MixedModelLayout.h.

◆ m_compOrder

std::unique_ptr<ShellingOrderModule> ogdf::MixedModelLayout::m_compOrder

private

The shelling order module.

Definition at line 154 of file MixedModelLayout.h.

◆ m_crossingsBeautifier

std::unique_ptr<MixedModelCrossingsBeautifierModule> ogdf::MixedModelLayout::m_crossingsBeautifier

private

The crossings beautifier module.

Definition at line 155 of file MixedModelLayout.h.

◆ m_embedder

std::unique_ptr<EmbedderModule> ogdf::MixedModelLayout::m_embedder

private

The planar embedder module.

Definition at line 152 of file MixedModelLayout.h.

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

include/ogdf/planarlayout/MixedModelLayout.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Precondition

Module options

Running Time

Constructor & Destructor Documentation

◆ MixedModelLayout()

◆ ~MixedModelLayout()

Member Function Documentation

◆ doCall()

◆ setAugmenter()

◆ setCrossingsBeautifier()

◆ setEmbedder()

◆ setShellingOrder()

Member Data Documentation

◆ m_augmenter

◆ m_compOrder

◆ m_crossingsBeautifier

◆ m_embedder

Open
Graph Drawing
Framework