Search

Topology based layout algorithms

The following algorithms are based on the topological features of the graph being arranged, such as the size and adjacency of faces (a face is a region bounded by links) and the overall direction of links. The algorithms differ in the shape they apply to graph faces and the manner in which faces are embedded in the plane.

One-way Graph Layout

The OneWayLayout class ensures that links enter into nodes from the same general direction and exit them from the opposite side. If the graph contains cycles, some links bend around the nodes to keep the enter/exit direction consistent. The algorithm aims to minimize the number of such links.

Topological Graph Layout

If the underlying graph if acyclic, TopologicalLayout arranges the nodes linearly in such a way that each node comes before all destination nodes of its outgoing links. The links are drawn as curves above the chain of nodes, with their height proportional to the distance between the nodes. If the graph is not acyclic, the layout algorithm finds an ordering with a minimal number of back links, and draws the back links below the chain of nodes.

Orthogonal Graph Layout

The OrthogonalLayout class implements an orthogonal graph layout algorithm. Each link is drawn as a chain of alternating horizontal and vertical segments. Nodes are placed in a way that facilitates few links bends and crossings. This algorithm was designed for planar graphs where the nodes have at most four incident links, and produces best results with such graphs as input. It can arrange any arbitrary graph as well, by adding some dummy nodes and links to planarize the graph and reduce its vertex degree, and removing them after the layout. However this might lead to using larger area than necessary, due to the space occupied by dummy elements.

Orthogonal Router

OrthogonalRouter is a secondary layout algorithm that can be used to arrange links after an initial node arrangement has already been applied. The orthogonal layout is useful when there are much more links than nodes in a graph. The algorithm strives to achieve the following criteria, while preserving as much of the initial node configuration as possible.

• links must not overlap;
• only vertical and horizontal routing lines are used;
• graph routing is performed with respect to the specified main layout direction;
• links crossings are minimized;
• bends are minimized;

Cascade Graph Layout

CascadeLayout places nodes on a virtual grid and arranges links orthogonally, such that if the source graph is planar all links are guaranteed to have no more than two bends and will not intersect. By default the layout method arranges nodes in rows and link segments in columns; this can be changed by setting the Orientation property.

Triangular Graph Layout

TriangularLayout places nodes on a virtual grid, such that if the source graph is planar, all links are guaranteed to have a single segment and not intersect. If the graph is not planar, its intersecting links can be optionally segmented and bended in order to improve readability. The layout method places the nodes from the external face on a triangle and recursively adds the rest of the nodes as vertices of internal triangles. As a result, it is very effective for near maximal-planar (a.k.a. triangular) graphs.