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 gansners algorithm .
static int	simple(Graph g, NodeMap rank, EdgeMap minLength) This method quickly calculates a tight tree using a highly optimized version of gansners 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 RankAssignments.simplex(Graph,NodeMap,DataProvider,DataProvider).

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,

Preconditions:

GraphChecker.isAsyclic(graph)

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

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

simplex

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

Similar to RankAssignments.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

simple

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

This method quickly calculates a tight tree using a highly optimized version of gansners algorithm .

Parameters:

g - the graph, where all the edes 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)

This method quickly calculates a tight tree using a highly optimized version of gansners algorithm .

Parameters:

g - the graph, where all the edes 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.