Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf. More...
#include <ogdf/layered/FastSimpleHierarchyLayout.h>
Public Member Functions | |
FastSimpleHierarchyLayout () | |
Creates an instance of fast simple hierarchy layout. More... | |
FastSimpleHierarchyLayout (const FastSimpleHierarchyLayout &) | |
Copy constructor. More... | |
virtual | ~FastSimpleHierarchyLayout () |
bool | balanced () const |
Returns the option balanced. More... | |
void | balanced (bool b) |
Sets the option balanced to b . More... | |
bool | downward () const |
Returns the option downward. More... | |
void | downward (bool d) |
Sets the option downward to d . More... | |
double | layerDistance () const |
Returns the option layer distance. More... | |
void | layerDistance (double dist) |
Sets the option layer distance to dist . More... | |
bool | leftToRight () const |
Returns the option left-to-right. More... | |
void | leftToRight (bool b) |
Sets the option left-to-right to b . More... | |
double | nodeDistance () const |
Returns the option node distance. More... | |
void | nodeDistance (double dist) |
Sets the option node distance to dist . More... | |
FastSimpleHierarchyLayout & | operator= (const FastSimpleHierarchyLayout &) |
Assignment operator. More... | |
Public Member Functions inherited from ogdf::HierarchyLayoutModule | |
HierarchyLayoutModule () | |
Initializes a hierarchy layout module. More... | |
virtual | ~HierarchyLayoutModule () |
void | call (const HierarchyLevelsBase &levels, GraphAttributes &GA) |
Computes a hierarchy layout of levels in GA . More... | |
Protected Member Functions | |
virtual void | doCall (const HierarchyLevelsBase &levels, GraphAttributes &AGC) override |
Implements the actual algorithm call. More... | |
Private Member Functions | |
void | computeBlockWidths (const GraphCopy &GC, const GraphAttributes &GCA, NodeArray< node > &root, NodeArray< double > &blockWidth) |
Computes the width of each block, i.e., the maximal width of a node in the block, and stores it in blockWidth for the root of the block. More... | |
void | horizontalCompactation (const NodeArray< node > &align, const HierarchyLevelsBase &levels, const NodeArray< node > &root, const NodeArray< double > &blockWidth, NodeArray< double > &x, const bool leftToRight, bool downward) |
Calculate the coordinates for each node. More... | |
void | markType1Conflicts (const HierarchyLevelsBase &levels, bool downward, NodeArray< NodeArray< bool >> &type1Conflicts) |
Preprocessing step to find all type1 conflicts. More... | |
void | placeBlock (node v, NodeArray< node > &sink, NodeArray< double > &shift, NodeArray< double > &x, const NodeArray< node > &align, const HierarchyLevelsBase &levels, const NodeArray< double > &blockWidth, const NodeArray< node > &root, const bool leftToRight) |
Calculate the coordinate for root nodes (placing) More... | |
node | pred (const node v, const HierarchyLevelsBase &levels, const bool leftToRight) |
Predecessor of v on the same level,. More... | |
void | verticalAlignment (const HierarchyLevelsBase &levels, NodeArray< node > &root, NodeArray< node > &align, const NodeArray< NodeArray< bool >> &type1Conflicts, const bool downward, const bool leftToRight) |
Align each node to a node on the next higher level. More... | |
node | virtualTwinNode (const HierarchyLevelsBase &levels, const node v, const HierarchyLevelsBase::TraversingDir dir) const |
The twin of an inner Segment. More... | |
Private Attributes | |
bool | m_balanced |
stores the option balanced. More... | |
bool | m_downward |
stores the option downward. More... | |
bool | m_leftToRight |
stores the option left-to-right. More... | |
double | m_minXSep |
stores the option node distance. More... | |
double | m_ySep |
stores the option layer distance. More... | |
Additional Inherited Members | |
Static Public Member Functions inherited from ogdf::HierarchyLayoutModule | |
static void | dynLayerDistance (GraphAttributes &AGC, HierarchyLevelsBase &levels) |
Static Protected Member Functions inherited from ogdf::HierarchyLayoutModule | |
static double | getHeight (const GraphAttributes &GA, const HierarchyLevelsBase &levels, node v) |
Returns the GA height of node v or 0 if it is a dummy node in the hierarchy of levels . More... | |
static double | getWidth (const GraphAttributes &GA, const HierarchyLevelsBase &levels, node v) |
Returns the GA width of node v or 0 if it is a dummy node in the hierarchy of levels . More... | |
Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf.
This class implements a hierarchy layout algorithm, i.e., it layouts hierarchies with a given order of nodes on each layer. It is used as a third phase of the Sugiyama algorithm.
The Algorithm runs in three phases.
The Alignment and Horzontal Compactation phase are calculated downward, upward, left-to-right and right-to-left. The four resulting layouts are combined in a balancing step.
The implementation is based on:
Ulrik Brandes, Boris Köpf: Fast and Simple Horizontal Coordinate Assignment. LNCS 2002, Volume 2265/2002, pp. 33-36
Option | Type | Default | Description |
---|---|---|---|
node distance | int | 150 | the minimal horizontal distance between two nodes on the same layer |
layer distance | int | 75 | the minimal vertical distance between two nodes on adjacent layers |
balanced | bool | true | determines whether balancing is used |
left-to-right | bool | true | determines whether block alignment is computed by a left-to-right (true) or right-to-left traversal |
downward | bool | true | determines whether block alignment is computed by a downward (true) or upward traversal |
Definition at line 86 of file FastSimpleHierarchyLayout.h.
ogdf::FastSimpleHierarchyLayout::FastSimpleHierarchyLayout | ( | ) |
Creates an instance of fast simple hierarchy layout.
Sets the options to default values, i.e., use balanced layout with left-to-right node direction on each layer, node distance as given by LayoutStandards, and layer distance as 1.5 times node distance.
ogdf::FastSimpleHierarchyLayout::FastSimpleHierarchyLayout | ( | const FastSimpleHierarchyLayout & | ) |
Copy constructor.
|
inlinevirtual |
Definition at line 111 of file FastSimpleHierarchyLayout.h.
|
inline |
Returns the option balanced.
Definition at line 141 of file FastSimpleHierarchyLayout.h.
|
inline |
Sets the option balanced to b
.
Definition at line 144 of file FastSimpleHierarchyLayout.h.
|
private |
Computes the width of each block, i.e., the maximal width of a node in the block, and stores it in blockWidth for the root of the block.
GC | The input graph copy |
GCA | The input graph copies (gives in particular the widths of nodes) |
root | The root for each node (calculated by this method) |
blockWidth | Is assigned the width of each block (stored for the root) |
|
overrideprotectedvirtual |
Implements the actual algorithm call.
Must be implemented by derived classes.
levels | is the input hierarchy. |
AGC | has to be assigned the hierarchy layout. |
Implements ogdf::HierarchyLayoutModule.
|
inline |
Returns the option downward.
Definition at line 129 of file FastSimpleHierarchyLayout.h.
|
inline |
Sets the option downward to d
.
Definition at line 132 of file FastSimpleHierarchyLayout.h.
|
private |
Calculate the coordinates for each node.
align | The alignment to the next level node (align(v)=u <=> u is aligned to v) |
levels | The Hierarchy |
root | The root for each node |
blockWidth | The width of each block |
x | The x-coordinates for each node (calculated by this method) |
leftToRight | The node direction on each level |
downward | The level direction |
|
inline |
Returns the option layer distance.
Definition at line 123 of file FastSimpleHierarchyLayout.h.
|
inline |
Sets the option layer distance to dist
.
Definition at line 126 of file FastSimpleHierarchyLayout.h.
|
inline |
Returns the option left-to-right.
Definition at line 135 of file FastSimpleHierarchyLayout.h.
|
inline |
Sets the option left-to-right to b
.
Definition at line 138 of file FastSimpleHierarchyLayout.h.
|
private |
Preprocessing step to find all type1 conflicts.
A type1 conflict is a crossing of a inner segment with a non-inner segment.
This is for preferring straight inner segments.
levels | The Hierarchy |
downward | The level direction |
type1Conflicts | is assigned the conflicts, (type1Conflicts[v])[u]=true means (u,v) is marked, u is the upper node |
|
inline |
Returns the option node distance.
Definition at line 117 of file FastSimpleHierarchyLayout.h.
|
inline |
Sets the option node distance to dist
.
Definition at line 120 of file FastSimpleHierarchyLayout.h.
FastSimpleHierarchyLayout& ogdf::FastSimpleHierarchyLayout::operator= | ( | const FastSimpleHierarchyLayout & | ) |
Assignment operator.
|
private |
Calculate the coordinate for root nodes (placing)
v | The root node to place |
sink | The Sink for each node. A sink identifies each block class (calculated by this method) |
shift | The shift for each class (calculated by this method) |
x | The class relative x-coordinate for each node (calculated by this method) |
align | The alignment to the next level node (align(v)=u <=> u is aligned to v) |
levels | The Hierarchy |
blockWidth | The width of each block |
root | The root for each node |
leftToRight | The node direction on each level |
|
private |
Predecessor of v on the same level,.
v | The node for which the predecessor should be calculated. |
levels | The Hierarchy |
leftToRight | If true the left predecessor is choosen. Otherwise the right predecessor. |
|
private |
Align each node to a node on the next higher level.
The result is a blockgraph where each node is in a block whith a nother node when they have the same root.
levels | The Hierarchy |
root | The root for each node (calculated by this method) |
align | The alignment to the next level node (align(v)=u <=> u is aligned to v) (calculated by this method) |
type1Conflicts | Type1 conflicts to prefer straight inner segments |
downward | The level direction |
leftToRight | The node direction on each level |
|
private |
The twin of an inner Segment.
|
private |
stores the option balanced.
Definition at line 90 of file FastSimpleHierarchyLayout.h.
|
private |
stores the option downward.
Definition at line 91 of file FastSimpleHierarchyLayout.h.
|
private |
stores the option left-to-right.
Definition at line 92 of file FastSimpleHierarchyLayout.h.
|
private |
stores the option node distance.
Definition at line 88 of file FastSimpleHierarchyLayout.h.
|
private |
stores the option layer distance.
Definition at line 89 of file FastSimpleHierarchyLayout.h.