
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.RankAssignments
public class RankAssignments
This class provides algorithms for solving the rank assignment problem.
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,∑(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 

public static int simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength)
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:
Minimum edge length and weights should be nonnegative.
graph
 the given graphlayer
 the NodeMap
that will be filled during the execution and returns the zerobased ranking index
for each nodew
 the DataProvider
that returns an integer value (weight) of each edgeminLength
 the DataProvider
that returns an integer value (minimum length) of each edge
simplex(Graph, NodeMap, DataProvider, DataProvider, long)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean, long)
public static int simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength, long maximalDuration)
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:
Minimum edge length and weights should be nonnegative.
graph
 the given graphlayer
 the NodeMap
that will be filled during the execution and returns the zerobased ranking index
for each nodew
 the DataProvider
that returns an integer value (weight) of each edgeminLength
 the DataProvider
that returns an integer value (minimum length) of each edgemaximalDuration
 a preferred time limit for the algorithm (in milliseconds)
simplex(Graph, NodeMap, DataProvider, DataProvider)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean, long)
public static int simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength, EdgeMap tree, Node root, boolean validRanking)
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 nonnegative.
graph
 the given graphlayer
 the NodeMap
that will be filled during the execution and returns the zerobased ranking index
for each nodew
 the DataProvider
that returns an integer value (weight) of each edgeminLength
 the DataProvider
that returns an integer value (minimum length) of each edgetree
 the EdgeMap
that returns a boolean value indicating whether or not an edge is a tree edgeroot
 the given root node of the tree solutionvalidRanking
 true
if the argument layer
contains a valid ranking,
false
otherwise
simplex(Graph, NodeMap, DataProvider, DataProvider)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, long)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean, long)
public static int simplex(Graph graph, NodeMap layer, DataProvider w, DataProvider minLength, EdgeMap tree, Node root, boolean validRanking, long maximalDuration)
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 nonnegative.
graph
 the given graphlayer
 the NodeMap
that will be filled during the execution and returns the zerobased ranking index
for each nodew
 the DataProvider
that returns an integer value (weight) of each edgeminLength
 the DataProvider
that returns an integer value (minimum length) of each edgetree
 the EdgeMap
that returns a boolean value indicating whether or not an edge is a tree edgeroot
 the given root node of the tree solutionvalidRanking
 true
if the argument layer
contains a valid ranking,
false
otherwisemaximalDuration
 a preferred time limit for the algorithm (in milliseconds)
simplex(Graph, NodeMap, DataProvider, DataProvider)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, long)
,
simplex(Graph, NodeMap, DataProvider, DataProvider, EdgeMap, Node, boolean)
public static int simple(Graph graph, NodeMap rank, EdgeMap minLength)
The algorithm is using a highly optimized version of Gansner's algorithm:
Minimum edge length and weights should be nonnegative.
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
nodeminLength
 the EdgeMap
that returns an integer value (minimum/tight length) of each edge
simple(Graph, int[], int[])
,
simple(Graph, int[], int[], long)
,
simple(Graph, NodeMap, EdgeMap, long)
public static int simple(Graph graph, NodeMap rank, EdgeMap minLength, long maximalDuration)
The algorithm is using a highly optimized version of Gansner's algorithm:
Minimum edge length and weights should be nonnegative.
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
nodeminLength
 the EdgeMap
that returns an integer value (minimum/tight length) of each edgemaximalDuration
 a preferred time limit for the algorithm (in milliseconds)simple(Graph, NodeMap, EdgeMap)
,
simple(Graph, int[], int[])
,
simple(Graph, int[], int[], long)
public static int simple(Graph graph, int[] rank, int[] minLength)
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:
Minimum edge length and weights should be nonnegative.
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 nonnegative value len
of each edge e
such that minLength[e.index] == len
simple(Graph, NodeMap, EdgeMap)
,
simple(Graph, int[], int[], long)
,
simple(Graph, NodeMap, EdgeMap, long)
public static int simple(Graph graph, int[] rank, int[] minLength, long maximalDuration)
simple(Graph, NodeMap, EdgeMap, long)
, but arrays are used instead of
NodeMap
s and EdgeMap
s.
Minimum edge length and weights should be nonnegative.
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 nonnegative value len
of each edge e
such that minLength[e.index] == len
simple(Graph, NodeMap, EdgeMap)
,
simple(Graph, int[], int[])
,
simple(Graph, NodeMap, EdgeMap, long)

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 