y.algo
Class RankAssignments

java.lang.Object
  y.algo.RankAssignments

public class RankAssignments
extends java.lang.Object

This class provides algorithms for solving the rank assignment problem.

Definitions

Let G=(V,E) be a directed acyclic graph. Let length(e) denote the minimum length and weight(e) the weight of an edge e.

The rank assignment problem is the problem of finding integer values rank(v) for all v in V, such that:

• rank(v) - rank(w) >= length(v,w), for all (v,w) in E and,
• the sum ∑(weight(v,w) * (rank(v) - rank(w))) over all (v,w) in E is minimized.

Method Summary

static int	simple(Graph graph, int[] rank, int[] minLength) Like simple(Graph, NodeMap, EdgeMap), but arrays are used instead of NodeMaps and EdgeMaps.
static int	simple(Graph graph, int[] rank, int[] minLength, long maximalDuration) Like simple(Graph, NodeMap, EdgeMap, long), but arrays are used instead of NodeMaps and EdgeMaps.
static int	simple(Graph graph, NodeMap rank, EdgeMap minLength) This method quickly calculates a tight tree.
static int	simple(Graph graph, NodeMap rank, EdgeMap minLength, long maximalDuration) This method quickly calculates a tight tree given a maximum time duration for the algorithm.
static int	simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength) Solves the rank assignment problem using the simplex method.
static int	simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength, EdgeMap tree, Node root, boolean validRanking) Similar to simplex(Graph, NodeMap, DataProvider, DataProvider) but, additionally, it is possible to provide a valid initial tree solution for the problem.
static int	simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength, EdgeMap tree, Node root, boolean validRanking, long maximalDuration) Similar to simplex(Graph, NodeMap, DataProvider, DataProvider) but, additionally, it is possible to provide a valid initial tree solution for the problem.
static int	simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength, long maximalDuration) Solves the rank assignment problem using the simplex method given a maximum time duration for the algorithm.

Methods inherited from class java.lang.Object

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

Method Detail

simplex

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

Solves the rank assignment problem using the simplex method.

This method assigns a minimum 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.

Minimum edge length and weights should be non-negative.

Precondition:

The graph must be acyclic.

Parameters:

graph - the given graph

layer - the NodeMap that will be filled during the execution and returns the zero-based ranking index for each node

w - the DataProvider that returns an integer value (weight) of each edge

minLength - the DataProvider that returns an integer value (minimum length) of each edge

Returns:

the number of layers

See Also:

simplex(Graph, NodeMap, DataProvider, DataProvider, long), simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean), simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean, long)

simplex

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

Solves the rank assignment problem using the simplex method given a maximum time duration for the algorithm.

This method assigns a minimum 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.

Minimum edge length and weights should be non-negative.

If the algorithm exceeds the maximum duration, the result may not be optimal.

Precondition:

The graph must be acyclic.

Parameters:

graph - the given graph

layer - the NodeMap that will be filled during the execution and returns the zero-based ranking index for each node

w - the DataProvider that returns an integer value (weight) of each edge

minLength - the DataProvider that returns an integer value (minimum length) of each edge

maximalDuration - a preferred time limit for the algorithm (in milliseconds)

Returns:

the number of layers

See Also:

simplex(Graph, NodeMap, DataProvider, DataProvider), simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean), simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean, long)

simplex

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

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

Minimum edge length and weights should be non-negative.

Parameters:

graph - the given graph

layer - the NodeMap that will be filled during the execution and returns the zero-based ranking index for each node

w - the DataProvider that returns an integer value (weight) of each edge

minLength - the DataProvider that returns an integer value (minimum length) of each edge

tree - the EdgeMap that returns a boolean value indicating whether or not an edge is a tree edge

root - the given root node of the tree solution

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

Returns:

the number of layers

See Also:

simplex(Graph, NodeMap, DataProvider, DataProvider), simplex(Graph, NodeMap, DataProvider, DataProvider, long), simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean, long)

simplex

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

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

Minimum edge length and weights should be non-negative.

If the algorithm exceeds the maximum duration, the result may not be optimal.

Parameters:

graph - the given graph

layer - the NodeMap that will be filled during the execution and returns the zero-based ranking index for each node

w - the DataProvider that returns an integer value (weight) of each edge

minLength - the DataProvider that returns an integer value (minimum length) of each edge

tree - the EdgeMap that returns a boolean value indicating whether or not an edge is a tree edge

root - the given root node of the tree solution

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

maximalDuration - a preferred time limit for the algorithm (in milliseconds)

Returns:

the number of layers

See Also:

simplex(Graph, NodeMap, DataProvider, DataProvider), simplex(Graph, NodeMap, DataProvider, DataProvider, long), simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean)

simple

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

This method quickly calculates a tight tree.

The algorithm is using a highly optimized version of Gansner's algorithm:

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

Minimum edge length and weights should be non-negative.

The calculated result is a valid but not optimal solution of the rank assignment problem.

Parameters:

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

rank - the NodeMap that will be filled during the execution and returns the integer ranking of each node

minLength - the EdgeMap that returns an integer value (minimum/tight length) of each edge

Returns:

the number of layers

See Also:

simple(Graph, int[], int[]), simple(Graph, int[], int[], long), simple(Graph, NodeMap, EdgeMap, long)

simple

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

This method quickly calculates a tight tree given a maximum time duration for the algorithm.

The algorithm is using a highly optimized version of Gansner's algorithm:

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

Minimum edge length and weights should be non-negative.

The calculated result is a valid but not optimal solution of the rank assignment problem.

If the algorithm exceeds the maximum duration, the result may be invalid (not a valid ranking).

Parameters:

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

rank - the NodeMap that will be filled during the execution and returns the integer ranking of each node

minLength - the EdgeMap that returns an integer value (minimum/tight length) of each edge

maximalDuration - a preferred time limit for the algorithm (in milliseconds)

See Also:

simple(Graph, NodeMap, EdgeMap), simple(Graph, int[], int[]), simple(Graph, int[], int[], long)

simple

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

Like simple(Graph, NodeMap, EdgeMap), but arrays are used instead of NodeMaps and EdgeMaps.

The algorithm is using a highly optimized version of Gansner's algorithm:

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

Minimum edge length and weights should be non-negative.

The calculated result is a valid but not optimal solution of the rank assignment problem.

Parameters:

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

rank - an array that will be filled with the ranking r of each node v such that rank[v.index] == r

minLength - an array holding a non-negative value len of each edge e such that minLength[e.index] == len

Returns:

the number of layers

See Also:

simple(Graph, NodeMap, EdgeMap), simple(Graph, int[], int[], long), simple(Graph, NodeMap, EdgeMap, long)

simple

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

Like simple(Graph, NodeMap, EdgeMap, long), but arrays are used instead of NodeMaps and EdgeMaps.

Minimum edge length and weights should be non-negative.

The calculated result is a valid but not optimal solution of the rank assignment problem.

If the algorithm exceeds the maximum duration, the result may be invalid (not a valid ranking).

Parameters:

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

rank - an array that will be filled with the ranking r of each node v such that rank[v.index] == r

minLength - an array holding a non-negative value len of each edge e such that minLength[e.index] == len

Returns:

the number of layers

See Also:

simple(Graph, NodeMap, EdgeMap), simple(Graph, int[], int[]), simple(Graph, NodeMap, EdgeMap, long)