de.cau.cs.kieler.klay.layered.intermediate
Class NorthSouthPortPreprocessor

java.lang.Object
  extended by de.cau.cs.kieler.core.alg.AbstractAlgorithm
      extended by de.cau.cs.kieler.klay.layered.intermediate.NorthSouthPortPreprocessor
All Implemented Interfaces:
IAlgorithm, ILayoutProcessor

public class NorthSouthPortPreprocessor
extends AbstractAlgorithm
implements ILayoutProcessor

Inserts dummy nodes to cope with northern and southern ports.

For each node with northern or southern ports, dummy nodes are inserted in the node's layer above or below the node. (for northern and southern ports, respectively) Assume that a node has several northern ports. First, the ports are assembled in left-to-right order according to their position. Then, the ports are partitioned into ports with only incoming edges (in ports), ports with only outgoing edges (out ports) and ports with both, incoming and outgoing edges (in/out ports). Note that this does not rely on port type information.

In and out ports are now matched up left to right and right to left, respectively, as long as the out port is right of the in port. In the example below, ports P1 and P6 will be matched, as will be ports P2 and P5. Ports P3 and P4 will not be matched since P3 is an out port and not right of P4.

For each pair of matched ports, a dummy node is then inserted that is shared by both ports. This leads to edges of both ports sharing the same y coordinate, which is fine as long as the out port is right of the in port. When this is no longer the case, ports cannot share a dummy node anymore. (the horizontal edge segments would overlap and thus introduce ambiguity) Thus, P4 and P3 each get their own dummy node.

Once in and out ports are processed, in/out ports are given their own dummy node.

                      ------------------------------
                      |
 ---------------------+----
                      |   |
 ------------------   |   |   ----------------------
                  |   |   |   |
 --------------   |   |   |   |   ------------------
              |   |   |   |   |   |
              P1  P2  P3  P4  P5  P6
 

Self-loops are a special case that is handled party by this processor. For this to work, the SelfLoopProcessor must have been executed prior to this processor's execution. Then, this processor correctly processes all kinds of self-loops involving northern or southern ports as follows: (due to the SelfLoopProcessor, only the cases detailled below must be handled)

Precondition:
a layered graph; nodes have fixed port sides.
Postcondition:
dummy nodes have been inserted for edges connected to ports on north and south sides, with layout groups and node successor constraints set.
Slots:
Before phase 3.
Same-slot dependencies:
PortListSorter, SelfLoopProcessor

See Also:
NorthSouthPortPostprocessor, PortListSorter, SelfLoopProcessor
Rating red

Constructor Summary
NorthSouthPortPreprocessor()
           
 
Method Summary
 void process(LayeredGraph layeredGraph)
          Performs the phase's work on the given graph.
 
Methods inherited from class de.cau.cs.kieler.core.alg.AbstractAlgorithm
getMonitor, reset, reset, setProgressMonitor
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface de.cau.cs.kieler.core.alg.IAlgorithm
reset, reset, setProgressMonitor
 

Constructor Detail

NorthSouthPortPreprocessor

public NorthSouthPortPreprocessor()
Method Detail

process

public void process(LayeredGraph layeredGraph)
Performs the phase's work on the given graph.

Specified by:
process in interface ILayoutProcessor
Parameters:
layeredGraph - a layered graph