de.cau.cs.kieler.klay.layered.p3order
Class CompoundGraphLayerCrossingMinimizer
java.lang.Object
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

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 |
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.
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.