(the following is the original commit message)
Now that the problematic edges are dealt with, all the normal edges
need to also get routed, but first, it's a good idea to order them.
As such, the DAG is consumed to produce the list of all the edges in
the optimal order for them to get routed.
(the following is the original commit message)
Now that every single node has gotten its exact position, the only
thing left to do is to route all the edges between them. First of
all, the special edges (like corners) need to be handled.
(the following is the original commit message)
Now that the nodes are placed into the grid (at least horizontally),
it's possible to focus on the edges. Since, the information about
the number of edges going from/to each of the layers is known, it's
possible to determine the number of horizontal space needed to placed
those.
In this part of the layouter, the focus is on three different laning
points:
- horizontal lanes between layers.
- entry lanes for each of the nodes.
- exit lanes for each of the nodes.
Indexation is done independently for each of the lane types.
(the following is the original commit message)
Since from this point on, no breaking changes will be done to the graph
It's possible to finalize the layout. Meaning that from this point
onwards the logical positions of the nodes remain unchanged.
Having this guarantee we can proceed to calculating their real
positions, starting from the horizontal coordinates.
(the following is the original commit message)
Now that the layer permutation is finalized, it's possible to select
a couple of node-groups that only depend on a single predecessor and
consider them a single linear segment. This allows to "draw" straight
vertical lines accross the layout for nodes that could benefit from
that.
Such linear segments are also paramount for good looking long edges
(both forwards and backwards facing).
\note: this part of the layouter could still use more work.
If you're looking to rework it, this is the spot.
(the following is the original commit message)
To ensure the optimal layout is choosen, it's important to try out
and compare a few different permutations.
First of all, layers are optimized. Those layers, that only contain
irrelevant artificial nodes are removed and all the others are shifted
in order to maintain simple layer indexing.
Then, using a simple hill climbing the permutation with the lowest
number of edge crossings is selected. After which a technique based
on computing barycenters for nodes and layers is used as a fallback
to ensure even the least optimal layout is still usable.
On top of all that, simple clustering based on the classification
obtained while preparing the graph is used to keep original nodes
somewhat separate from the artificial ones.
(the following is the original commit message)
Preparation includes:
- ensuring there are no loops.
- ensuring there are no edges spanning more than a single layer.
- ensuring there are no backwards facing edges that were not split
into a bunch of parts to simplify laying them out.
- ensuring there are no self loops (they are treated similarly to
backwards facing edges, which they theoretically are).
Subproducts include:
- `Classifier` allowing to cheaply determine whether a given node is
adjacent to an artificial edge.
- `Ranks` container allowing to easily determine the layer each of the
nodes belongs to.
Ivan Krysak