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

java.lang.Object
  extended by 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 red

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
 

Constructor Detail

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

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.