com.yworks.yfiles.algorithms

Class RankAssignments

java.lang.Object

com.yworks.yfiles.algorithms.RankAssignments

public final class RankAssignments
extends 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

Modifier and Type	Method and Description
static int	simple(Graph graph, INodeMap rank, IEdgeMap minLength) This method quickly calculates a tight tree given a maximum time duration for the algorithm.
static int	simple(Graph graph, INodeMap rank, IEdgeMap minLength, long maximalDuration) This method quickly calculates a tight tree given a maximum time duration for the algorithm.
static int	simple(Graph graph, int[] rank, int[] minLength) Like simple(Graph, INodeMap, IEdgeMap, long), but arrays are used instead of INodeMaps and IEdgeMaps.
static int	simple(Graph graph, int[] rank, int[] minLength, long maximalDuration) Like simple(Graph, INodeMap, IEdgeMap, long), but arrays are used instead of INodeMaps and IEdgeMaps.
static int	simplex(Graph graph, INodeMap layer, IDataProvider w, IDataProvider minLength) Solves the rank assignment problem using the simplex method given a maximum time duration for the algorithm.
static int	simplex(Graph graph, INodeMap layer, IDataProvider w, IDataProvider minLength, IEdgeMap tree, Node _root, boolean validRanking) Similar to simplex(Graph, INodeMap, IDataProvider, IDataProvider, long) but, additionally, it is possible to provide a valid initial tree solution for the problem.
static int	simplex(Graph graph, INodeMap layer, IDataProvider w, IDataProvider minLength, IEdgeMap tree, Node _root, boolean validRanking, long maximalDuration) Similar to simplex(Graph, INodeMap, IDataProvider, IDataProvider, long) but, additionally, it is possible to provide a valid initial tree solution for the problem.
static int	simplex(Graph graph, INodeMap layer, IDataProvider w, IDataProvider 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

simple

public static final int simple(Graph graph,
                               INodeMap rank,
                               IEdgeMap minLength)

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 INodeMap that will be filled during the execution and returns the integer ranking of each node

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

See Also:

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

simple

public static final int simple(Graph graph,
                               INodeMap rank,
                               IEdgeMap 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 INodeMap that will be filled during the execution and returns the integer ranking of each node

minLength - the IEdgeMap 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, int[], int[], long)

simple

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

Like simple(Graph, INodeMap, IEdgeMap, long), but arrays are used instead of INodeMaps and IEdgeMaps.

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, INodeMap, IEdgeMap, long)

simple

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

Like simple(Graph, INodeMap, IEdgeMap, long), but arrays are used instead of INodeMaps and IEdgeMaps.

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

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

Returns:

the number of layers

See Also:

simple(Graph, INodeMap, IEdgeMap, long)

simplex

public static final int simplex(Graph graph,
                                INodeMap layer,
                                IDataProvider w,
                                IDataProvider minLength)

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 INodeMap that will be filled during the execution and returns the zero-based ranking index for each node

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

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

Returns:

the number of layers

See Also:

simplex(Graph, INodeMap, IDataProvider, IDataProvider, long), simplex(Graph, INodeMap, IDataProvider, IDataProvider, IEdgeMap, Node, boolean, long)

simplex

public static final int simplex(Graph graph,
                                INodeMap layer,
                                IDataProvider w,
                                IDataProvider minLength,
                                IEdgeMap tree,
                                Node _root,
                                boolean validRanking)

Similar to simplex(Graph, INodeMap, IDataProvider, IDataProvider, long) 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 INodeMap that will be filled during the execution and returns the zero-based ranking index for each node

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

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

tree - the IEdgeMap 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, INodeMap, IDataProvider, IDataProvider, long), simplex(Graph, INodeMap, IDataProvider, IDataProvider, IEdgeMap, Node, boolean, long)

simplex

public static final int simplex(Graph graph,
                                INodeMap layer,
                                IDataProvider w,
                                IDataProvider minLength,
                                IEdgeMap tree,
                                Node _root,
                                boolean validRanking,
                                long maximalDuration)

Similar to simplex(Graph, INodeMap, IDataProvider, IDataProvider, long) 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 INodeMap that will be filled during the execution and returns the zero-based ranking index for each node

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

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

tree - the IEdgeMap 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, INodeMap, IDataProvider, IDataProvider, long), simplex(Graph, INodeMap, IDataProvider, IDataProvider, IEdgeMap, Node, boolean, long)

simplex

public static final int simplex(Graph graph,
                                INodeMap layer,
                                IDataProvider w,
                                IDataProvider 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 INodeMap that will be filled during the execution and returns the zero-based ranking index for each node

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

minLength - the IDataProvider 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, INodeMap, IDataProvider, IDataProvider, long), simplex(Graph, INodeMap, IDataProvider, IDataProvider, IEdgeMap, Node, boolean, long)