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

#include <ogdf/planarlayout/PlanarDrawLayout.h>

Inheritance diagram for ogdf::PlanarDrawLayout:

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.

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

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`.

Private Member Functions
void	computeCoordinates (const Graph &G, ShellingOrder &order, NodeArray< int > &x, NodeArray< int > &y)

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

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

double	m_baseRatio
	The option for specifying the base ratio.

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

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

bool	m_sideOptimization
	The option for size optimization.

bool	m_sizeOptimization
	The option for allowing arbitrary slopes.

Additional Inherited Members
Protected Member Functions inherited from ogdf::PlanarGridLayoutModule
virtual void	doCall (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox) override
	Implements the GridLayoutModule::doCall().

bool	handleTrivial (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox)
	Handles the special cases of graphs with less than 3 nodes.

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

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

Option	Type	Default	Description
sizeOptimization	bool	true	If this option is set to true, the algorithm tries to reduce the size of the resulting grid layout.
sideOptimization	bool	false	If this option is set to true, slopes different from +1, 0, -1 are allowed on the contour for reducing the resulting grid size.
baseRatio	double	0.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:

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!

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 118 of file PlanarDrawLayout.h.

Constructor & Destructor Documentation

◆ PlanarDrawLayout()

ogdf::PlanarDrawLayout::PlanarDrawLayout ( )

Constructs an instance of the Planar-Draw layout algorithm.

◆ ~PlanarDrawLayout()

ogdf::PlanarDrawLayout::~PlanarDrawLayout ( )

inline

Definition at line 123 of file PlanarDrawLayout.h.

Member Function Documentation

◆ baseRatio() [1/2]

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, m_baseRatio * size of external face) many.

Definition at line 159 of file PlanarDrawLayout.h.

◆ baseRatio() [2/2]

void ogdf::PlanarDrawLayout::baseRatio ( double ratio )

inline

Sets the option baseRatio to ratio.

Definition at line 162 of file PlanarDrawLayout.h.

◆ computeCoordinates()

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

private

◆ doCall()

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

overrideprivatevirtual

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.

◆ setAugmenter()

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 175 of file PlanarDrawLayout.h.

◆ setEmbedder()

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

inline

Sets the module option for the graph embedding algorithm.

Definition at line 181 of file PlanarDrawLayout.h.

◆ setShellingOrder()

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

inline

Sets the shelling order module.

Definition at line 178 of file PlanarDrawLayout.h.

◆ sideOptimization() [1/2]

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 147 of file PlanarDrawLayout.h.

◆ sideOptimization() [2/2]

void ogdf::PlanarDrawLayout::sideOptimization ( bool opt )

inline

Sets the option sideOptimization to opt.

Definition at line 150 of file PlanarDrawLayout.h.

◆ sizeOptimization() [1/2]

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 136 of file PlanarDrawLayout.h.

◆ sizeOptimization() [2/2]

void ogdf::PlanarDrawLayout::sizeOptimization ( bool opt )

inline

Sets the option sizeOptimization to opt.

Definition at line 139 of file PlanarDrawLayout.h.

Member Data Documentation

◆ m_augmenter

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

private

The augmentation module.

Definition at line 191 of file PlanarDrawLayout.h.

◆ m_baseRatio

double ogdf::PlanarDrawLayout::m_baseRatio

private

The option for specifying the base ratio.

Definition at line 188 of file PlanarDrawLayout.h.

◆ m_computeOrder

std::unique_ptr<ShellingOrderModule> ogdf::PlanarDrawLayout::m_computeOrder

private

The shelling order module.

Definition at line 192 of file PlanarDrawLayout.h.

◆ m_embedder

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

private

The planar embedder module.

Definition at line 190 of file PlanarDrawLayout.h.

◆ m_sideOptimization

bool ogdf::PlanarDrawLayout::m_sideOptimization

private

The option for size optimization.

Definition at line 187 of file PlanarDrawLayout.h.

◆ m_sizeOptimization

bool ogdf::PlanarDrawLayout::m_sizeOptimization

private

The option for allowing arbitrary slopes.

Definition at line 186 of file PlanarDrawLayout.h.

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

include/ogdf/planarlayout/PlanarDrawLayout.h

OpenGraph DrawingFramework

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Precondition

Optional parameters

Module options

Running Time

Constructor & Destructor Documentation

◆ PlanarDrawLayout()

◆ ~PlanarDrawLayout()

Member Function Documentation

◆ baseRatio() [1/2]

◆ baseRatio() [2/2]

◆ computeCoordinates()

◆ doCall()

◆ setAugmenter()

◆ setEmbedder()

◆ setShellingOrder()

◆ sideOptimization() [1/2]

◆ sideOptimization() [2/2]

◆ sizeOptimization() [1/2]

◆ sizeOptimization() [2/2]

Member Data Documentation

◆ m_augmenter

◆ m_baseRatio

◆ m_computeOrder

◆ m_embedder

◆ m_sideOptimization

◆ m_sizeOptimization

Open
Graph Drawing
Framework