The class SchnyderLayout represents the layout algorithm by Schnyder [Sch90]. More...

#include <ogdf/planarlayout/SchnyderLayout.h>

Inheritance diagram for ogdf::SchnyderLayout:

Public Types
enum	CombinatorialObjects { CombinatorialObjects::VerticesMinusDepth, CombinatorialObjects::Faces }
	Each node in a Schnyder wood splits the graph into three regions. More...

Public Member Functions
	SchnyderLayout ()

CombinatorialObjects	getCombinatorialObjects ()
	Returns the type of combinatorial objects whose number corresponds to the node coordinates. More...

void	setCombinatorialObjects (CombinatorialObjects combinatorialObjects)
	Sets the type of combinatorial objects whose number corresponds to the node coordinates. More...

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

virtual	~PlanarGridLayoutModule ()

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

void	callGridFixEmbed (const Graph &G, GridLayout &gridLayout, adjEntry adjExternal=nullptr)
	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 ()

virtual void	call (GraphAttributes &GA) override final
	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 IPoint &	gridBoundingBox () 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 ()

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

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

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

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

Private Member Functions
void	contract (Graph &G, node a, node b, node c, List< node > &L)

void	prefixSum (EdgeArray< int > &rValues, int i, node r, const NodeArray< int > &val, NodeArray< int > &sum)

void	realizer (GraphCopy &G, const List< node > &L, node a, node b, node c, EdgeArray< int > &rValues, GraphCopy &T)

void	schnyderEmbedding (GraphCopy &GC, GridLayout &gridLayout, adjEntry adjExternal)

void	subtreeSizes (EdgeArray< int > &rValues, int i, node r, NodeArray< int > &size)

Private Attributes
CombinatorialObjects	m_combinatorialObjects
	Determines how the barycentric coordinates of each node are computed. More...

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

Detailed Description

The class SchnyderLayout represents the layout algorithm by Schnyder [Sch90].

This algorithm draws a planar graph G straight-line without crossings. G (with |V| ≥ 3) must not contain self-loops or multiple edges. The algorithm runs in three phases. In the first phase, the graph is augmented by adding new artificial edges to get a triangulated plane graph. Then, a partition of the set of interior edges in three trees (also called Schnyder trees) with special orientation properties is derived. In the third step, the actual coordinates are computed. See:

[Sch90] Schnyder, Walter. "Embedding planar graphs on the grid." Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1990.

[Sch89] Schnyder, Walter. "Planar graphs and poset dimension." Order 5.4 (1989): 323-343.

Definition at line 65 of file SchnyderLayout.h.

Member Enumeration Documentation

◆ CombinatorialObjects

enum ogdf::SchnyderLayout::CombinatorialObjects

strong

Each node in a Schnyder wood splits the graph into three regions.

The barycentric coordinates of the nodes are given by the count of combinatorial objects in these regions.

Enumerator

VerticesMinusDepth

Count the number of vertices in each region i and subtract the depth of the (i-1)-path of the node.

This approach is outlined in [Sch90]. The grid layout size is (n - 2) × (n - 2).

Faces

Count the number of faces in each region i.

This approach is outlined in [Sch89]. The grid layout size is (2n - 5) × (2n - 5).

Definition at line 74 of file SchnyderLayout.h.

Constructor & Destructor Documentation

◆ SchnyderLayout()

ogdf::SchnyderLayout::SchnyderLayout ( )

Member Function Documentation

◆ contract()

void ogdf::SchnyderLayout::contract	(	Graph &	G,
		node	a,
		node	b,
		node	c,
		List< node > &	L
	)

private

◆ doCall()

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

overrideprotectedvirtual

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.

◆ getCombinatorialObjects()

CombinatorialObjects ogdf::SchnyderLayout::getCombinatorialObjects ( )

inline

Returns the type of combinatorial objects whose number corresponds to the node coordinates.

Definition at line 85 of file SchnyderLayout.h.

◆ prefixSum()

void ogdf::SchnyderLayout::prefixSum	(	EdgeArray< int > &	rValues,
		int	i,
		node	r,
		const NodeArray< int > &	val,
		NodeArray< int > &	sum
	)

private

◆ realizer()

void ogdf::SchnyderLayout::realizer	(	GraphCopy &	G,
		const List< node > &	L,
		node	a,
		node	b,
		node	c,
		EdgeArray< int > &	rValues,
		GraphCopy &	T
	)

private

◆ schnyderEmbedding()

void ogdf::SchnyderLayout::schnyderEmbedding	(	GraphCopy &	GC,
		GridLayout &	gridLayout,
		adjEntry	adjExternal
	)

private

◆ setCombinatorialObjects()

void ogdf::SchnyderLayout::setCombinatorialObjects ( CombinatorialObjects combinatorialObjects )

inline

Sets the type of combinatorial objects whose number corresponds to the node coordinates.

Definition at line 88 of file SchnyderLayout.h.

◆ subtreeSizes()

void ogdf::SchnyderLayout::subtreeSizes	(	EdgeArray< int > &	rValues,
		int	i,
		node	r,
		NodeArray< int > &	size
	)

private

Member Data Documentation

◆ m_combinatorialObjects

CombinatorialObjects ogdf::SchnyderLayout::m_combinatorialObjects

private

Determines how the barycentric coordinates of each node are computed.

Definition at line 110 of file SchnyderLayout.h.

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

include/ogdf/planarlayout/SchnyderLayout.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ CombinatorialObjects

Constructor & Destructor Documentation

◆ SchnyderLayout()

Member Function Documentation

◆ contract()

◆ doCall()

◆ getCombinatorialObjects()

◆ prefixSum()

◆ realizer()

◆ schnyderEmbedding()

◆ setCombinatorialObjects()

◆ subtreeSizes()

Member Data Documentation

◆ m_combinatorialObjects

Open
Graph Drawing
Framework