This class provides algorithms for solving the rank assignment problem.
Inheritance Hierarchy
RankAssignmentAlgorithm
Remarks
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)inEand,- the sum
∑(weight(v,w) * (rank(v) - rank(w)))over all(v,w)inEis minimized.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.RankAssignments
Static Methods
This method quickly calculates a tight tree given a maximum time duration for the algorithm.
Remarks
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.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the input graph in which all the edges have directions, such that
rank[source] < rank[target]andrank[target] - rank[source] >= minlength[edge] - rank - INodeMap
- the INodeMap that will be filled during the execution and returns the integer ranking of each node
Domain YNode Values number a non-negative value representing the ranking of each node - minLength - IEdgeMap
- the IEdgeMap that returns an integer value (minimum/tight length) of each edge
Domain Edge Values number a non-negative value representing the minimum length of each edge - maximalDuration - number
- a preferred time limit for the algorithm (in milliseconds)
See Also
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).
Like simple, but arrays are used instead of INodeMaps and IEdgeMaps.
Remarks
Minimum edge length and weights should be non-negative.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the input graph in which all the edges have directions, such that
rank[source] < rank[target]andrank[target] - rank[source] >= minlength[edge] - rank - number[]
- an array that will be filled with the ranking
rof each nodevsuch thatrank[v.index] == r - minLength - number[]
- an array holding a non-negative value
lenof each edgeesuch thatminLength[e.index] == len - maximalDuration - number
- a preferred time limit for the algorithm (in milliseconds)
Returns
- ↪number
- the number of layers
See Also
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).
If the algorithm exceeds the maximum duration, the result may be invalid (not a valid ranking).
simplex
(graph: Graph, layer: INodeMap, w: IDataProvider, minLength: IDataProvider, maximalDuration?: number) : numberSolves the rank assignment problem using the simplex method given a maximum time duration for the algorithm.
Remarks
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.
Preconditions
- The graph must be acyclic.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given graph
- layer - INodeMap
- the INodeMap that will be filled during the execution and returns the zero-based ranking index for each node
Domain YNode Values number the zero-based ranking index for each node - w - IDataProvider
- the IDataProvider that returns an integer value (weight) of each edge
Domain Edge Values number a non-negative value representing the weight of each edge - minLength - IDataProvider
- the IDataProvider that returns an integer value (minimum length) of each edge
Domain Edge Values number a non-negative value representing the minimum length of each edge - maximalDuration - number
- a preferred time limit for the algorithm (in milliseconds)
Returns
- ↪number
- the number of layers
See Also
RankAssignmentAlgorithm.simplex(Graph,INodeMap,IDataProvider,IDataProvider,number),
RankAssignmentAlgorithm.simplex(Graph,INodeMap,IDataProvider,IDataProvider,IEdgeMap,YNode,boolean,number)
If the algorithm exceeds the maximum duration, the result may not be optimal.
simplex
(graph: Graph, layer: INodeMap, w: IDataProvider, minLength: IDataProvider, tree: IEdgeMap, root: YNode, validRanking: boolean, maximalDuration?: number) : numberSimilar to simplex but, additionally, it is possible to provide a valid initial tree solution for the problem.
Remarks
Minimum edge length and weights should be non-negative.
Parameters
options - Object
A map of options to pass to the method.
A map of options to pass to the method.
- graph - Graph
- the given graph
- layer - INodeMap
- the INodeMap that will be filled during the execution and returns the zero-based ranking index for each node
Domain YNode Values number the zero-based ranking index for each node - w - IDataProvider
- the IDataProvider that returns an integer value (weight) of each edge
Domain Edge Values number a non-negative value representing the weight of each edge - minLength - IDataProvider
- the IDataProvider that returns an integer value (minimum length) of each edge
Domain Edge Values number a non-negative value representing the minimum length of each edge - tree - IEdgeMap
- the IEdgeMap that returns a boolean value indicating whether or not an edge is a tree edge
Domain Edge Values boolean trueif the edge is a tree edge,falseotherwise - root - YNode
- the given root node of the tree solution
- validRanking - boolean
trueif the argumentlayercontains a valid ranking,falseotherwise- maximalDuration - number
- a preferred time limit for the algorithm (in milliseconds)
Returns
- ↪number
- the number of layers
See Also
RankAssignmentAlgorithm.simplex(Graph,INodeMap,IDataProvider,IDataProvider,number),
RankAssignmentAlgorithm.simplex(Graph,INodeMap,IDataProvider,IDataProvider,IEdgeMap,YNode,boolean,number)
If the algorithm exceeds the maximum duration, the result may not be optimal.