Packagecom.yworks.yfiles.algo
Classpublic class RankAssignments
InheritanceRankAssignments Inheritance YObject Inheritance 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.


Public Methods
 MethodDefined By
  
RankAssignments(init:Boolean = true)
RankAssignments
 Inherited
equals(o:Object):Boolean
YObject
  
getClass():Class
[override]
RankAssignments
 Inherited
hashCode():int
YObject
  
newRankAssignments():RankAssignments
[static]
RankAssignments
  
simple(g:Graph, rank:NodeMap, minLength:EdgeMap):int
[static] This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
RankAssignments
  
simple2(g:Graph, rank:Vector.<int>, minLength:Vector.<int>):int
[static] This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
RankAssignments
  
simple3(g:Graph, rank:NodeMap, minLength:EdgeMap, maximalDuration:uint):int
[static] This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
RankAssignments
  
simple4(g:Graph, rank:Vector.<int>, minLength:Vector.<int>, maximalDuration:uint):int
[static] This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .
RankAssignments
  
simplex(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider):int
[static] Solves the rank assignment problem using the simplex method.
RankAssignments
  
simplex2(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider, maximalDuration:uint):int
[static] Solves the rank assignment problem using the simplex method.
RankAssignments
  
simplex3(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider, tree:EdgeMap, _root:Node, validRanking:Boolean):int
[static] Similar to simplex().
RankAssignments
  
simplex4(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider, tree:EdgeMap, _root:Node, validRanking:Boolean, maximalDuration:uint):int
[static] Similar to simplex().
RankAssignments
Protected Methods
 MethodDefined By
  
initRankAssignments():void
RankAssignments
Constructor Detail
RankAssignments()Constructor
public function RankAssignments(init:Boolean = true)



Parameters
init:Boolean (default = true)
Method Detail
getClass()method
override public function getClass():Class

Returns
Class
initRankAssignments()method 
protected final function initRankAssignments():void

newRankAssignments()method 
public static function newRankAssignments():RankAssignments

Returns
RankAssignments
simple()method 
public static function simple(g:Graph, rank:NodeMap, minLength:EdgeMap):int

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Parameters

g:Graph — the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]
 
rank:NodeMap — the initial ranking
 
minLength:EdgeMap — the minimal (tight) lengths for each edge. Values must be non-negative.

Returns
int — the number of layers.
simple2()method 
public static function simple2(g:Graph, rank:Vector.<int>, minLength:Vector.<int>):int

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Parameters

g:Graph — the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]
 
rank:Vector.<int> — the initial ranking
 
minLength:Vector.<int> — the minimal (tight) lengths for each edge. Values must be non-negative.

Returns
int — the number of layers.
simple3()method 
public static function simple3(g:Graph, rank:NodeMap, minLength:EdgeMap, maximalDuration:uint):int

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Note: if the algorithm exceeds the maximal duration, the result may be invalid (not a valid ranking).

Parameters

g:Graph — the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]
 
rank:NodeMap — the initial ranking
 
minLength:EdgeMap — the minimal (tight) lengths for each edge. Values must be non-negative.
 
maximalDuration:uint — a preferred time limit for the algorithm in milliseconds.

Returns
int — the number of layers.
simple4()method 
public static function simple4(g:Graph, rank:Vector.<int>, minLength:Vector.<int>, maximalDuration:uint):int

This method quickly calculates a tight tree using a highly optimized version of Gansner's algorithm .

Note: if the algorithm exceeds the maximal duration, the result may be invalid (not a valid ranking).

Parameters

g:Graph — the graph, where all the edges have directions, such that rank[source] < rank[target] and rank[target] - rank[source] >= minlength[edge]
 
rank:Vector.<int> — the initial ranking
 
minLength:Vector.<int> — the minimal (tight) lengths for each edge. Values must be non-negative.
 
maximalDuration:uint — a preferred time limit for the algorithm in milliseconds.

Returns
int — the number of layers.
simplex()method 
public static function simplex(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider):int

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,

Precondition GraphChecker.isAcyclic(graph)

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

Parameters

g:Graph — the graph for which the layers are determined.
 
layer:NodeMap — here the ranking is stored.
 
w:DataProvider — here the weight of an edge is stored.
 
minLength:DataProvider — here the minimal length of an edge is stored.

Returns
int — the number of layers
simplex2()method 
public static function simplex2(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider, maximalDuration:uint):int

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,

Note: if the algorithm exceeds the maximal duration, the result may not be optimal.

Precondition GraphChecker.isAcyclic(graph)

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

Parameters

g:Graph — the graph for which the layers are determined.
 
layer:NodeMap — here the ranking is stored.
 
w:DataProvider — here the weight of an edge is stored.
 
minLength:DataProvider — here the minimal length of an edge is stored.
 
maximalDuration:uint — a preferred time limit for the algorithm in milliseconds.

Returns
int — the number of layers
simplex3()method 
public static function simplex3(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider, tree:EdgeMap, _root:Node, validRanking:Boolean):int

Similar to simplex(). Additionally it is possible to provide a valid initial tree solution for the problem.

Parameters

g:Graph — the graph for which the layers are determined.
 
layer:NodeMap — here the ranking is stored.
 
w:DataProvider — here the weight of an edge is stored.
 
minLength:DataProvider — here the minimal length of an edge is stored.
 
tree:EdgeMap — may contain a valid tree solution.
 
_root:Node — the root of the tree solution.
 
validRanking:Boolean — if true, the argument layer contains a valid ranking.

Returns
int — the number of layers

See also

simplex()
simplex4()method 
public static function simplex4(g:Graph, layer:NodeMap, w:DataProvider, minLength:DataProvider, tree:EdgeMap, _root:Node, validRanking:Boolean, maximalDuration:uint):int

Similar to simplex(). Additionally it is possible to provide a valid initial tree solution for the problem.

Note: if the algorithm exceeds the maximal duration, the result may not be optimal.

Parameters

g:Graph — the graph for which the layers are determined.
 
layer:NodeMap — here the ranking is stored.
 
w:DataProvider — here the weight of an edge is stored.
 
minLength:DataProvider — here the minimal length of an edge is stored.
 
tree:EdgeMap — may contain a valid tree solution.
 
_root:Node — the root of the tree solution.
 
validRanking:Boolean — if true, the argument layer contains a valid ranking.
 
maximalDuration:uint — a preferred time limit for the algorithm in milliseconds.

Returns
int — the number of layers

See also

simplex()




Wed Oct 7 2015, 04:43 PM +02:00