|
|||
|
|
|
|||
|
|
The class SchnyderLayout represents the layout algorithm by Schnyder [Sch90]. More...
#include <ogdf/planarlayout/SchnyderLayout.h>
Inheritance diagram for ogdf::SchnyderLayout:Public Types | |
| enum class | CombinatorialObjects { VerticesMinusDepth , 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. | |
| void | setCombinatorialObjects (CombinatorialObjects combinatorialObjects) |
| Sets the type of combinatorial objects whose number corresponds to the node coordinates. | |
| Public Member Functions inherited from ogdf::PlanarGridLayoutModule | |
| PlanarGridLayoutModule () | |
| Initializes a planar grid layout module. | |
| virtual | ~PlanarGridLayoutModule () |
| void | callFixEmbed (GraphAttributes &AG, adjEntry adjExternal=nullptr) |
| Calls the grid layout algorithm with a fixed planar embedding (general call). | |
| void | callGridFixEmbed (const Graph &G, GridLayout &gridLayout, adjEntry adjExternal=nullptr) |
| Calls the grid layout algorithm with a fixed planar embedding (call for GridLayout). | |
| Public Member Functions inherited from ogdf::GridLayoutModule | |
| GridLayoutModule () | |
| Initializes a grid layout module. | |
| virtual | ~GridLayoutModule () |
| virtual void | call (GraphAttributes &GA) override final |
| Calls the grid layout algorithm (general call). | |
| void | callGrid (const Graph &G, GridLayout &gridLayout) |
| Calls the grid layout algorithm (call for GridLayout). | |
| 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 | |
| LayoutModule () | |
| Initializes a layout module. | |
| virtual | ~LayoutModule () |
| void | operator() (GraphAttributes &GA) |
Computes a layout of graph GA. | |
Protected Member Functions | |
| virtual void | doCall (const Graph &G, adjEntry adjExternal, GridLayout &gridLayout, IPoint &boundingBox, bool fixEmbedding) override |
| Implements the algorithm call. | |
| Protected Member Functions inherited from ogdf::PlanarGridLayoutModule | |
| virtual void | doCall (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox) override |
| Implements the GridLayoutModule::doCall(). | |
| bool | handleTrivial (const Graph &G, GridLayout &gridLayout, IPoint &boundingBox) |
| Handles the special cases of graphs with less than 3 nodes. | |
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. | |
Additional Inherited Members | |
| Protected Attributes inherited from ogdf::GridLayoutModule | |
| IPoint | m_gridBoundingBox |
| The computed bounding box of the grid layout. | |
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 60 of file SchnyderLayout.h.
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.
Definition at line 69 of file SchnyderLayout.h.
| ogdf::SchnyderLayout::SchnyderLayout | ( | ) |
|
overrideprotectedvirtual |
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.
|
inline |
Returns the type of combinatorial objects whose number corresponds to the node coordinates.
Definition at line 80 of file SchnyderLayout.h.
|
private |
|
private |
|
private |
|
inline |
Sets the type of combinatorial objects whose number corresponds to the node coordinates.
Definition at line 83 of file SchnyderLayout.h.
|
private |
|
private |
Determines how the barycentric coordinates of each node are computed.
Definition at line 105 of file SchnyderLayout.h.
