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;