Search this API

## y.algo Class RankAssignments

```java.lang.Object
y.algo.RankAssignments
```

`public class RankAssignmentsextends 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 `NodeMap`s and `EdgeMap`s.
`static int` ```simple(Graph graph, int[] rank, int[] minLength, long maximalDuration)```
Like `simple(Graph, NodeMap, EdgeMap, long)`, but arrays are used instead of `NodeMap`s and `EdgeMap`s.
`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
`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
`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
`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
`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
`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)
`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 `NodeMap`s and `EdgeMap`s.

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
`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 `NodeMap`s and `EdgeMap`s.

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
`simple(Graph, NodeMap, EdgeMap)`, `simple(Graph, int[], int[])`, `simple(Graph, NodeMap, EdgeMap, long)`