/**
 * This algorithm is an implementation for solving the node placement problem
 * which is posed in phase 4 of the ELK Layered algorithm. Inspired by:
 * <ul>
 *   <li> Ulrik Brandes and Boris K&ouml;pf, Fast and simple horizontal coordinate assignment.
 *     In <i>Proceedings of the 9th International Symposium on Graph Drawing (GD'01)</i>,
 *     LNCS vol. 2265, pp. 33-36, Springer, 2002. </li>
 * </ul>
 * 
 * <p>The original algorithm was extended to be able to cope with ports, node sizes, and node margins,
 * and was made more stable in general. The algorithm is structured in five steps, which include two new
 * steps which were not included in the original algorithm by Brandes and Koepf. The middle three steps
 * are executed four times, traversing the graph in all combinations of TOP or BOTTOM and LEFT or
 * RIGHT.</p>
 * 
 * <p>In ELK Layered we have the general idea of layouting from left to right and
 * transforming in the desired direction later. We decided to translate the terminology of the original
 * algorithm which thinks of a layout from top to bottom. When placing coordinates, we have to differ
 * from the original algorithm, since node placement in ELK Layered has to assign y-coordinates and not
 * x-coordinates.</p>
 * 
 * <p>The variable naming in this code is mostly chosen for an iteration direction within our
 * left to right convention. Arrows describe iteration direction.
 * 
 * LEFT                  RIGHT
 * <----------           ------->
 * 
 * UP    ^              DOWN |
 *       |                   |
 *       |                   v
 * </p>   
 *      
 * <h4>The algorithm:</h4>
 * 
 * <p>The first step checks the graphs' edges and marks short edges which cross long edges (called
 * type 1 conflict). The algorithm indents to draw long edges as straight as possible, thus trying to
 * solve the marked conflicts in a way which keep the long edge straight.</p>
 * 
 * <p>============ UP, DOWN x LEFT, RIGHT ============</p>
 * 
 * <p>The second step traverses the graph in the given directions and tries to group connected nodes
 * into (horizontal) blocks. These blocks, respectively the contained nodes, will be drawn straight when
 * the algorithm is finished. Here, type 1 conflicts are resolved, so that the dummy nodes of a long
 * edge share the same block if possible, such that the long edge is drawn straightly.</p>
 * 
 * <p>The third step contains the addition of node size and port positions to the original algorithm.
 * Each block is investigated from top to bottom. Nodes are moved inside the blocks, such that the port
 * of the edge going to the next node is on the same level as that next node. Furthermore, the size of
 * the block is calculated, regarding node sizes and new space needed due to node movement.</p>
 * 
 * <p>In the fourth step, actual y-coordinates are determined. The blocks are placed, start block and
 * direction determined by the directions of the current iteration. It is tried to place the blocks as
 * compact as possible by grouping blocks.</p>
 *  
 * <p>======================= END =======================</p>
 * 
 * <p>The action of the last step depends on a layout option. If "fixedAlignment" is not set to 
 * BALANCED, one of the four calculated layouts is selected and applied, choosing the layout which 
 * uses the least space. If it is false, a balanced layout is chosen by calculating a median layout 
 * of all four layouts.</p>
 * 
 * <p>In rare cases, it is possible that one or more layouts is not correct, e.g. having nodes which
 * overlap each other or violating the layer ordering constraint. If the algorithm detects that, the
 * respective layout is discarded and another one is chosen.</p>
 * 
 * <dl>
 *   <dt>Preconditions:</dt>
 *     <dd>The graph has a proper layering with optimized nodes ordering</dd>
 *     <dd>Ports are properly arranged</dd>
 *   <dt>Postconditions:</dt>
 *     <dd>Each node is assigned a vertical coordinate such that no two nodes overlap</dd>
 *     <dd>The size of each layer is set according to the area occupied by its nodes</dd>
 *     <dd>The height of the graph is set to the maximal layer height</dd>
 * </dl>
 */

Specifies whether the Brandes Koepf node placer tries to increase the number of straight edges at the expense of diagram size. There is a subtle difference to the ‘favorStraightEdges’ option, which decides whether a balanced placement of the nodes is desired, or not. In bk terms this means combining the four alignments into a single balanced one, or not. This option on the other hand tries to straighten additional edges during the creation of each of the four alignments.

/*
 * Marks all edges in the graph with a type-1 conflict with the "type1Conflict"
 * property. A type-1 conflict is one where a non-inner segment crosses an
 * inner segment. An inner segment is an edge with both incident nodes marked
 * with the "dummy" property.
 *
 * This algorithm scans layer by layer, starting with the second, for type-1
 * conflicts between the current layer and the previous layer. For each layer
 * it scans the nodes from left to right until it reaches one that is incident
 * on an inner segment. It then scans predecessors to determine if they have
 * edges that cross that inner segment. At the end a final scan is done for all
 * nodes on the current rank to see if they cross the last visited inner
 * segment.
 *
 * This algorithm (safely) assumes that a dummy node will only be incident on a
 * single node in the layers being scanned.
 */

The C++ implementation is in igraph in sugiyama.c at
https://github.com/igraph/igraph/blob/master/src/layout/sugiyama.c

/*
 * Implementation of the Sugiyama layout algorithm as described in:
 *
 * [1] K. Sugiyama, S. Tagawa and M. Toda, "Methods for Visual Understanding of
 * Hierarchical Systems". IEEE Transactions on Systems, Man and Cybernetics
 * 11(2):109-125, 1981.
 *
 * The layering (if not given in advance) is calculated by ... TODO
 *
 * [2] TODO
 *
 * The X coordinates of nodes within a layer are calculated using the method of
 * Brandes & Köpf:
 *
 * [3] U. Brandes and B. Köpf, "Fast and Simple Horizontal Coordinate
 * Assignment".  In: Lecture Notes in Computer Science 2265:31-44, 2002.
 *
 * Layer compaction is done according to:
 *
 * [4] N.S. Nikolov and A. Tarassov, "Graph layering by promotion of nodes".
 * Journal of Discrete Applied Mathematics, special issue: IV ALIO/EURO
 * workshop on applied combinatorial optimization, 154(5).
 */

The nodes can have edge connections to nodes at lever higher or level lower (out-edges) nodes.
Every node has upper and lower median nodes in a array.
To set these median nodes the in / out edges list at a node must be sorted on the position of the connecting node.
The upper median nodes are connections to nodes above the node level at level-1 via incoming edges.
similar for the lower median nodes.
The upper median left node is the median node of the incoming edges connected nodes.
the upper median right node is the next node from the left node.
similar for the lower median left and right node.
when node has no in or out edges then the median nodes are the node itself.
This is median as in math, the middle node in a sequence of nodes.