aiSee: Coordinate Calculation and Edge Bending

Coordinate calculation

Coordinate calculation follows after partitioning nodes into levels and ordering the nodes within the levels. Nodes can be aligned at the bottom or at the top of a level or centered at a level, with there being a minimum distance between levels (see graph attribute yspace). This influences the y coordinates. The x coordinate has to be calculated such that there is a minimum distance between nodes (xspace) and a minimum distance between the bend points of edges (xlspace). Furthermode, the layout should be balanced such that the edges are short and straight.

This is achieved by using a special method for downward laid-out trees or performing two general iteration phases. The first phase simulates a physical pendulum, the nodes being the balls and the edges the strings. The balls hanging on the strings swing to and fro, i.e. the nodes move within their level and influence the neighboring nodes until the layout is sparse enough and each node has sufficient space to be favorably positioned.

Next the nodes are centered with respect to their edges. This phase simulates a rubberband network: The edges pull on a node with a power proportional to their length, the result being that the node moves to a position such that the sum of the forces of its edges is zero. Then, the length of the edges is balanced.

An optional fine-tuning phase (see graph attribute straight_phase) tries to recognize long edges and draws them as vertical long line segments. This is useful for the orthogonal layout methods.

Unfortunately, both physical simulations needn't be convergent, meaning they may be iterated infinitely often without resulting in a stable layout. However, these cases are seldom. The number of iterations is restricted in order to prevent infinite execution, the t message character in the message window indicating that a timeout has occurred.

Edge bending

If a graph contains nodes of different sizes, an edge starting at a very small node may be drawn through a neighbored large node. This situation is avoided by bending edges at certain points. In addition, if an orthogonal layout method is selected, the edges are bent so that only orthogonal line segments exist (see graph attributes manhattan_edges and smanhattan_edges.