|
|||
|
|
|
|||
|
|
#include <MixedModelLayout.h>
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. | |
Protected Member Functions | |
| void | doCall (PlanRep &PG, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding) |
| Implements the algorithm call. | |
Private Attributes | |
| ModuleOption< EmbedderModule > | m_embedder |
| The planar embedder module. | |
| ModuleOption< AugmentationModule > | m_augmenter |
| The augmentation module. | |
| ModuleOption< ShellingOrderModule > | m_compOrder |
| The shelling order module. | |
| ModuleOption < MixedModelCrossingsBeautifierModule > | m_crossingsBeautifier |
| The crossings beautifier module. | |
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 mulitple 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.
The input graph needs to be planar and simple (i.e., no self-loops and no multiple edges).
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. |
The computation of the layout takes time O(n), where n is the number of nodes of the input graph.
Definition at line 139 of file MixedModelLayout.h.
| ogdf::MixedModelLayout::MixedModelLayout | ( | ) |
Constructs an instance of the Mixed-Model layout algorithm.
| virtual ogdf::MixedModelLayout::~MixedModelLayout | ( | ) | [inline, virtual] |
Definition at line 145 of file MixedModelLayout.h.
| 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 158 of file MixedModelLayout.h.
| void ogdf::MixedModelLayout::setShellingOrder | ( | ShellingOrderModule * | pOrder | ) | [inline] |
| void ogdf::MixedModelLayout::setCrossingsBeautifier | ( | MixedModelCrossingsBeautifierModule * | pBeautifier | ) | [inline] |
| void ogdf::MixedModelLayout::setEmbedder | ( | EmbedderModule * | pEmbedder | ) | [inline] |
Sets the module option for the graph embedding algorithm.
Definition at line 173 of file MixedModelLayout.h.
| void ogdf::MixedModelLayout::doCall | ( | PlanRep & | PG, | |
| adjEntry | adjExternal, | |||
| GridLayout & | gridLayout, | |||
| IPoint & | boundingBox, | |||
| bool | fixEmbedding | |||
| ) | [protected, virtual] |
