de.cau.cs.kieler.klay.layered.p2layers
Class NetworkSimplexLayerer

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

public class NetworkSimplexLayerer
extends AbstractAlgorithm
implements ILayoutPhase

The main class of the network simplex layerer component. It offers an algorithm to determine an optimal layering of all nodes in the graph concerning a minimal length of all edges using the network simplex algorithm described in Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-Phong Vo: "A Technique for Drawing Directed Graphs", AT&T Bell Laboratories.

Precondition:
the graph has no cycles
Postcondition:
all nodes have been assigned a layer such that edges connect only nodes from layers with increasing indices

Rating red

Constructor Summary
NetworkSimplexLayerer()
           
 
Method Summary
 IntermediateProcessingStrategy getIntermediateProcessingStrategy(LayeredGraph graph)
          Returns the intermediate layout processors this phase depends on.
 void process(LayeredGraph theLayeredGraph)
          The main method of the network simplex layerer.
 
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

NetworkSimplexLayerer

public NetworkSimplexLayerer()
Method Detail

getIntermediateProcessingStrategy

public IntermediateProcessingStrategy getIntermediateProcessingStrategy(LayeredGraph graph)
Returns the intermediate layout processors this phase depends on.

Specified by:
getIntermediateProcessingStrategy in interface ILayoutPhase
Parameters:
graph - the layered graph to be processed. The strategy may vary depending on certain properties of the graph.
Returns:
intermediate processing strategy. May be null.

process

public void process(LayeredGraph theLayeredGraph)
The main method of the network simplex layerer. It determines an optimal layering of all nodes in the graph concerning a minimal length of all edges by using the network simplex algorithm described in {@literal Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-Phong Vo: "A Technique for Drawing Directed Graphs", AT&T Bell Laboratories. Note that the execution time of this implemented algorithm has not been proven quadratic yet.

Specified by:
process in interface ILayoutProcessor
Parameters:
theLayeredGraph - a layered graph which initially only contains layerless nodes and is then filled with layers
See Also:
ILayerer