de.cau.cs.kieler.klay.layered.p3order
Class BarycenterHeuristic
java.lang.Object
de.cau.cs.kieler.klay.layered.p3order.BarycenterHeuristic
- All Implemented Interfaces:
- ICrossingMinimizationHeuristic
public class BarycenterHeuristic
- extends Object
- implements ICrossingMinimizationHeuristic
Determines the node order of a given free layer. Uses heuristic methods to find an ordering that
minimizes edge crossings between the given free layer and a neighboring layer with fixed node
order. The barycenter heuristic is used here.
- Rating

Constructor Summary |
BarycenterHeuristic(IPortDistributor selPortDistributor,
Random graphRandom)
Constructs a BarycenterHeuristic with the given portDistributor, selected by the
LayerSweepCrossingMinimizer. |
Method Summary |
int |
minimizeCrossings(List<NodeGroup> layerNodeGroups,
com.google.common.collect.Multimap<LNode,LNode> layoutUnits,
int layerIndex,
boolean preOrdered,
boolean randomize,
boolean forward,
float[] portPos,
Map<LNode,NodeGroup>[] singleNodeNodeGroups)
Minimize the number of crossings for the edges between the given layer and either its
predecessor or its successor. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
BarycenterHeuristic
public BarycenterHeuristic(IPortDistributor selPortDistributor,
Random graphRandom)
- Constructs a BarycenterHeuristic with the given portDistributor, selected by the
LayerSweepCrossingMinimizer.
- Parameters:
selPortDistributor
- the port distributor chosen by the LayerSweepCrossingMinimizer.graphRandom
- the random number generator.
minimizeCrossings
public int minimizeCrossings(List<NodeGroup> layerNodeGroups,
com.google.common.collect.Multimap<LNode,LNode> layoutUnits,
int layerIndex,
boolean preOrdered,
boolean randomize,
boolean forward,
float[] portPos,
Map<LNode,NodeGroup>[] singleNodeNodeGroups)
- Minimize the number of crossings for the edges between the given layer and either its
predecessor or its successor. Resolve violated constraints. Calculate Port Ranks.
- Specified by:
minimizeCrossings
in interface ICrossingMinimizationHeuristic
- Parameters:
layerNodeGroups
- the free layer whose nodes are reordered.layoutUnits
- a map associating layout units with their respective members.layerIndex
- the free layer's index.preOrdered
- whether the nodes have been ordered in a previous run.randomize
- true
if this layer's node order should just be randomized. In that case,
preOrdered
is assumed to be false
and the return value is
0
.forward
- whether the free layer is after the fixed layer.portPos
- position array.singleNodeNodeGroups
- Map of single node vertices for each layer.
- Returns:
- the total number of edges going either in or out of the given layer.