Implementation of the Mixed-Model layout algorithm. More...
|Constructs an instance of the Mixed-Model layout algorithm. |
|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. |
|Public Member Functions inherited from ogdf::GridLayoutPlanRepModule|
|Initializes a plan-rep grid layout module. |
|void||callGrid (const Graph &G, GridLayout &gridLayout)|
|Calls the grid layout algorithm (call for GridLayout). |
|void||callGrid (PlanRep &PG, GridLayout &gridLayout)|
|Calls the grid layout algorithm (call for GridLayout of a PlanRep). |
|void||callGridFixEmbed (const Graph &G, GridLayout &gridLayout, adjEntry adjExternal=0)|
|Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout). |
|void||callGridFixEmbed (PlanRep &PG, GridLayout &gridLayout, adjEntry adjExternal=0)|
|Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout of a PlanRep). |
|Public Member Functions inherited from ogdf::PlanarGridLayoutModule|
|Initializes a planar grid layout module. |
|void||callFixEmbed (GraphAttributes &AG, adjEntry adjExternal=0)|
|Calls the grid layout algorithm with a fixed planar embedding (general call). |
|Public Member Functions inherited from ogdf::GridLayoutModule|
|Initializes a grid layout module. |
|void||call (GraphAttributes &AG)|
|Calls the grid layout algorithm (general call). |
|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|
|Initializes a layout module. |
|virtual void||call (GraphAttributes &GA, GraphConstraints &GC)|
|Computes a layout of graph GA wrt the constraints in GC (if applicable). |
|void||operator() (GraphAttributes &GA)|
|Computes a layout of graph GA. |
|void||doCall (PlanRep &PG, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding)|
|Implements the algorithm call. |
|ModuleOption< AugmentationModule >||m_augmenter|
|The augmentation module. |
|ModuleOption< ShellingOrderModule >||m_compOrder|
|The shelling order module. |
< MixedModelCrossingsBeautifierModule >
|The crossings beautifier module. |
|ModuleOption< EmbedderModule >||m_embedder|
|The planar embedder module. |
Implementation of the Mixed-Model layout algorithm.
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 multiple 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:
|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.
Constructs an instance of the Mixed-Model layout algorithm.
Implements the algorithm call.