|
|||
|
|
|
|||
|
|
Implementation of the Planar-Draw layout algorithm. More...
#include <ogdf/planarlayout/PlanarDrawLayout.h>
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. | |
Private Member Functions | |
| void | doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding) |
| Implements the algorithm call. | |
| void | computeCoordinates (const Graph &G, ShellingOrder &order, NodeArray< int > &x, NodeArray< int > &y) |
Private Attributes | |
| bool | m_sizeOptimization |
| The option for allowing arbitrary slopes. | |
| bool | m_sideOptimization |
| The option for size optimization. | |
| double | m_baseRatio |
| The option for specifying the base ratio. | |
| ModuleOption< AugmentationModule > | m_augmenter |
| The augmentation module. | |
| ModuleOption< ShellingOrderModule > | m_computeOrder |
| The shelling order module. | |
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.
The input graph needs to be planar and simple (i.e., no self-loops and no multiple edges).
| 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. |
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). |
| 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! |
The computation of the layout takes time O(n), where n is the number of nodes of the input graph.
Definition at line 143 of file PlanarDrawLayout.h.
| ogdf::PlanarDrawLayout::PlanarDrawLayout | ( | ) |
Constructs an instance of the Planar-Draw layout algorithm.
| ogdf::PlanarDrawLayout::~PlanarDrawLayout | ( | ) | [inline] |
Definition at line 149 of file PlanarDrawLayout.h.
| 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, baseRatio * size of external face) many.
Definition at line 186 of file PlanarDrawLayout.h.
| void ogdf::PlanarDrawLayout::baseRatio | ( | double | ratio | ) | [inline] |
Sets the option baseRatio to ratio.
Definition at line 189 of file PlanarDrawLayout.h.
| void ogdf::PlanarDrawLayout::computeCoordinates | ( | const Graph & | G, | |
| ShellingOrder & | order, | |||
| NodeArray< int > & | x, | |||
| NodeArray< int > & | y | |||
| ) | [private] |
| void ogdf::PlanarDrawLayout::doCall | ( | const Graph & | G, | |
| adjEntry | adjExternal, | |||
| GridLayout & | gridLayout, | |||
| IPoint & | boundingBox, | |||
| bool | fixEmbedding | |||
| ) | [private, virtual] |
Implements the algorithm call.
A derived algorithm must implement this method and return the computed grid layout in gridLayout.
| 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.
| 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 203 of file PlanarDrawLayout.h.
| void ogdf::PlanarDrawLayout::setShellingOrder | ( | ShellingOrderModule * | pOrder | ) | [inline] |
Sets the shelling order module.
Definition at line 208 of file PlanarDrawLayout.h.
| 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 174 of file PlanarDrawLayout.h.
| void ogdf::PlanarDrawLayout::sideOptimization | ( | bool | opt | ) | [inline] |
Sets the option sideOptimization to opt.
Definition at line 177 of file PlanarDrawLayout.h.
| void ogdf::PlanarDrawLayout::sizeOptimization | ( | bool | opt | ) | [inline] |
Sets the option sizeOptimization to opt.
Definition at line 166 of file PlanarDrawLayout.h.
| 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 163 of file PlanarDrawLayout.h.
The augmentation module.
Definition at line 219 of file PlanarDrawLayout.h.
double ogdf::PlanarDrawLayout::m_baseRatio [private] |
The option for specifying the base ratio.
Definition at line 217 of file PlanarDrawLayout.h.
The shelling order module.
Definition at line 220 of file PlanarDrawLayout.h.
bool ogdf::PlanarDrawLayout::m_sideOptimization [private] |
The option for size optimization.
Definition at line 216 of file PlanarDrawLayout.h.
bool ogdf::PlanarDrawLayout::m_sizeOptimization [private] |
The option for allowing arbitrary slopes.
Definition at line 215 of file PlanarDrawLayout.h.
