de.cau.cs.kieler.klay.layered.p3order
Class CompoundGraphLayerCrossingMinimizer

java.lang.Object
  extended by de.cau.cs.kieler.klay.layered.p3order.CompoundGraphLayerCrossingMinimizer

public class CompoundGraphLayerCrossingMinimizer
extends Object

Implements the actual crossing minimization step for a given free layer. In a flat graph, an ICrossingMinimizationHeuristic is directly used to compute the node ordering. For compound graphs it computes orderings for each compound node seperately, working its way from the innermost compound node to the outermost, using calculated node orders as atomic sets of nodes for the next calculations. This approach is inspired by Michael Forster: "Applying Crossing Reduction Strategies to Layered Compound Graphs", University of Passau.

Rating red

Constructor Summary
protected CompoundGraphLayerCrossingMinimizer(IPortDistributor selPortDistributor, Random graphRandom, boolean handleHierarchy, float[] portRanks, Map<LNode,NodeGroup>[] oneNodeNodeGroups, com.google.common.collect.Multimap<LNode,LNode> layoutUnit)
          Constructs a CompoundGraphLayerCrossingMinimizer with the given IPortDistributor, Random, isCompound, portPos array, single-node-nodeGroup map and layoutUnits.
 
Method Summary
protected  int compoundMinimizeCrossings(LNode[] layer, int layerIndex, boolean forward, boolean preOrdered, boolean randomize, LayeredGraph layeredGraph)
          Uses an ICrossingMinimizationHeuristic to compute a node order for a given layer.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

CompoundGraphLayerCrossingMinimizer

protected CompoundGraphLayerCrossingMinimizer(IPortDistributor selPortDistributor,
                                              Random graphRandom,
                                              boolean handleHierarchy,
                                              float[] portRanks,
                                              Map<LNode,NodeGroup>[] oneNodeNodeGroups,
                                              com.google.common.collect.Multimap<LNode,LNode> layoutUnit)
Constructs a CompoundGraphLayerCrossingMinimizer with the given IPortDistributor, Random, isCompound, portPos array, single-node-nodeGroup map and layoutUnits.

Parameters:
selPortDistributor - the IPortDistributor chosen by the crossing minimizer.
graphRandom - the random number generator.
handleHierarchy - whether the graph to be laid out is a compound one.
portRanks - the array of port ranks.
oneNodeNodeGroups - map of single node vertices for each layer.
layoutUnit - map associating layoutUnits with their members.
Method Detail

compoundMinimizeCrossings

protected int compoundMinimizeCrossings(LNode[] layer,
                                        int layerIndex,
                                        boolean forward,
                                        boolean preOrdered,
                                        boolean randomize,
                                        LayeredGraph layeredGraph)
Uses an ICrossingMinimizationHeuristic to compute a node order for a given layer. If the graph to be laid out is a compound graph, it prepares slices of work for the ICrossingMinimizationHeuristic: Each compound node is ordered separately, from the innermost one to the outermost. After ordering, the nodes of a compound node are treated as an atomic entity with fixed node order, represented by a NodeGroup for the next calculations.

Parameters:
layer - the nodes of the layer, whose order is to be determined.
layerIndex - the index of that layer.
forward - whether the fixed layer is located after the free layer.
preOrdered - whether the nodes have been ordered in a previous run.
randomize - whether the layer's node order should just be randomized.
layeredGraph - The layered graph that is to be laid out.
Returns:
the total number of edges going either in or out of the given layer.