Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::FPPLayout Class Reference

The class FPPLayout represents the layout algorithm by de Fraysseix, Pach, Pollack [DPP90]. More...

#include <ogdf/planarlayout/FPPLayout.h>

+ Inheritance diagram for ogdf::FPPLayout:

Public Member Functions

 FPPLayout ()
 
- 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 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 ()
 
void operator() (GraphAttributes &GA)
 Computes a layout of graph GA. More...
 

Private Member Functions

void computeCoordinates (const GraphCopy &G, IPoint &boundingBox, GridLayout &gridLayout, NodeArray< int > &num, NodeArray< adjEntry > &e_wp, NodeArray< adjEntry > &e_wq)
 
void computeOrder (const GraphCopy &G, NodeArray< int > &num, NodeArray< adjEntry > &e_wp, NodeArray< adjEntry > &e_wq, adjEntry e_12, adjEntry e_2n, adjEntry e_n1)
 
virtual void doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding) override
 Implements the algorithm call. More...
 

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(). More...
 
bool handleTrivial (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox)
 Handles the special cases of graphs with less than 3 nodes. More...
 
- Protected Attributes inherited from ogdf::GridLayoutModule
IPoint m_gridBoundingBox
 The computed bounding box of the grid layout. More...
 

Detailed Description

The class FPPLayout represents the layout algorithm by de Fraysseix, Pach, Pollack [DPP90].

This algorithm draws a planar graph G straight-line without crossings. G must not contain self-loops or multiple edges. The grid layout size is (2n-4) * (n-2) for a graph with n nodes (n ≥ 3). 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 so-called shelling order (also called canonical ordering) for triangulated planar graphs is computed. In the third phase the vertices are placed incrementally according to the shelling order.

Definition at line 53 of file FPPLayout.h.

Constructor & Destructor Documentation

◆ FPPLayout()

ogdf::FPPLayout::FPPLayout ( )

Member Function Documentation

◆ computeCoordinates()

void ogdf::FPPLayout::computeCoordinates ( const GraphCopy G,
IPoint boundingBox,
GridLayout gridLayout,
NodeArray< int > &  num,
NodeArray< adjEntry > &  e_wp,
NodeArray< adjEntry > &  e_wq 
)
private

◆ computeOrder()

void ogdf::FPPLayout::computeOrder ( const GraphCopy G,
NodeArray< int > &  num,
NodeArray< adjEntry > &  e_wp,
NodeArray< adjEntry > &  e_wq,
adjEntry  e_12,
adjEntry  e_2n,
adjEntry  e_n1 
)
private

◆ doCall()

virtual void ogdf::FPPLayout::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
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.


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