y.algo
Class RankAssignments

java.lang.Object
  y.algo.RankAssignments

public class RankAssignments
extends Object

Provides algorithms for solving the rank assignment problem.

Let G=(V,E) be a directed acyclic graph. Let length(e) denote the minimal length and weight(e) the weight of an edge e. The rank assignment problem is to find values x(v) for all v in V, such that x(v) - x(w) >= length(v,w) for all (v,w) in E, and that the sum weight(v,w)*(x(v)-x(w)) over all (v,w) in E is minimal.

Constructor Summary

RankAssignments()

Method Summary

static int	simple(Graph g, int[] rank, int[] minLength) This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
static int	simple(Graph g, int[] rank, int[] minLength, long maximalDuration) This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
static int	simple(Graph g, NodeMap rank, EdgeMap minLength) This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
static int	simple(Graph g, NodeMap rank, EdgeMap minLength, long maximalDuration) This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
static int	simplex(Graph g, NodeMap layer, DataProvider w, DataProvider minLength) Solves the rank assignment problem using the simplex method.
static int	simplex(Graph g, NodeMap layer, DataProvider w, DataProvider minLength, EdgeMap tree, Node _root, boolean validRanking) Similar to simplex(Graph,NodeMap,DataProvider,DataProvider).
static int	simplex(Graph g, NodeMap layer, DataProvider w, DataProvider minLength, EdgeMap tree, Node _root, boolean validRanking, long maximalDuration) Similar to simplex(Graph,NodeMap,DataProvider,DataProvider).
static int	simplex(Graph g, NodeMap layer, DataProvider w, DataProvider minLength, long maximalDuration) Solves the rank assignment problem using the simplex method.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RankAssignments

public RankAssignments()

Method Detail

simplex

public static int simplex(Graph g,
                          NodeMap layer,
                          DataProvider w,
                          DataProvider minLength)

Solves the rank assignment problem using the simplex method. This method assigns a minimal rank to the nodes in a acyclic graph. Although its time complexity has not been proven polynomial, in practice it takes few iterations and runs quickly.

The algorithm is based on:

E.R. Gansner et al, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, Vol.19, No.3, March 1993,

Parameters:

g - the graph for which the layers are determined.

layer - here the ranking is stored.

w - here the weight of an edge is stored.

minLength - here the minimal length of an edge is stored.

Returns:

the number of layers

Preconditions:

GraphChecker.isAcyclic(graph)

minLength.getInt(e) defined for each edge in graph.

simplex

public static int simplex(Graph g,
                          NodeMap layer,
                          DataProvider w,
                          DataProvider minLength,
                          long maximalDuration)

Solves the rank assignment problem using the simplex method. This method assigns a minimal rank to the nodes in a acyclic graph. Although its time complexity has not been proven polynomial, in practice it takes few iterations and runs quickly.

The algorithm is based on:

E.R. Gansner et al, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, Vol.19, No.3, March 1993,

Parameters:

g - the graph for which the layers are determined.

layer - here the ranking is stored.

w - here the weight of an edge is stored.

minLength - here the minimal length of an edge is stored.

maximalDuration - a preferred time limit for the algorithm in milliseconds.

Returns:

the number of layers

Preconditions:

GraphChecker.isAcyclic(graph)

minLength.getInt(e) defined for each edge in graph.

simplex

public static int simplex(Graph g,
                          NodeMap layer,
                          DataProvider w,
                          DataProvider minLength,
                          EdgeMap tree,
                          Node _root,
                          boolean validRanking)

Similar to simplex(Graph,NodeMap,DataProvider,DataProvider). Additionally it is possible to provide a valid initial tree solution for the problem.

Parameters:

g - the graph for which the layers are determined.

layer - here the ranking is stored.

w - here the weight of an edge is stored.

minLength - here the minimal length of an edge is stored.

validRanking - if true, the argument layer contains a valid ranking.

tree - may contain a valid tree solution.

_root - the root of the tree solution.

Returns:

the number of layers

simplex

public static int simplex(Graph g,
                          NodeMap layer,
                          DataProvider w,
                          DataProvider minLength,
                          EdgeMap tree,
                          Node _root,
                          boolean validRanking,
                          long maximalDuration)

Similar to simplex(Graph,NodeMap,DataProvider,DataProvider). Additionally it is possible to provide a valid initial tree solution for the problem.

Parameters:

g - the graph for which the layers are determined.

layer - here the ranking is stored.

w - here the weight of an edge is stored.

minLength - here the minimal length of an edge is stored.

validRanking - if true, the argument layer contains a valid ranking.

tree - may contain a valid tree solution.

_root - the root of the tree solution.

maximalDuration - a preferred time limit for the algorithm in milliseconds.

Returns:

the number of layers

simple

public static int simple(Graph g,
                         NodeMap rank,
                         EdgeMap minLength)

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Parameters:

g - the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]

rank - the initial ranking

minLength - the minimal (tight) lengths for each edge. Values must be non-negative.

Returns:

the number of layers.

simple

public static int simple(Graph g,
                         NodeMap rank,
                         EdgeMap minLength,
                         long maximalDuration)

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Parameters:

g - the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]

rank - the initial ranking

minLength - the minimal (tight) lengths for each edge. Values must be non-negative.

maximalDuration - a preferred time limit for the algorithm in milliseconds.

Returns:

the number of layers.

simple

public static int simple(Graph g,
                         int[] rank,
                         int[] minLength)

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Parameters:

g - the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]

rank - the initial ranking

minLength - the minimal (tight) lengths for each edge. Values must be non-negative.

Returns:

the number of layers.

simple

public static int simple(Graph g,
                         int[] rank,
                         int[] minLength,
                         long maximalDuration)

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Parameters:

g - the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]

rank - the initial ranking

minLength - the minimal (tight) lengths for each edge. Values must be non-negative.

maximalDuration - a preferred time limit for the algorithm in milliseconds.

Returns:

the number of layers.