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.
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.
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.
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.
TopologicalLayout applies graph topological ordering to the diagram (topological ordering of a graph is one where link's origin node is placed before link's destination node). The layout algorithm arranges nodes in a row or a column, depending on the value of the Orientation property, in such a way that there are no backward links when the graph is acyclic. If the graph contains cycles, the algorithms selects ordering with as few backward links as possible. Links that connect non-adjacent nodes are rendered as arcs, whose amplitude is proportional to the distance between respective connected nodes. Forward links are rendered at one side of the nodes and back links are rendered at the opposite side. All that makes it easy to discern graph features such as overall flow direction, cycles and nested cycles.
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.
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.
