Solves the rank assignment problem.
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 ∈ V, such that:
- rank(v) − rank(w) ≥ length(v, w), for all (v, w) ∈ E and,
- ∑(weight(v, w) ⋅ (rank(v) − rank(w))) over all (v, w) ∈ E is minimized.
Algorithm
The algorithm 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.
Examples
// prepare the rank assignment algorithm
const algorithm = new RankAssignment({
weights,
minimumEdgeLengths,
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual rank
for (const node of graph.nodes) {
const rank = result.nodeRankIds.get(node)
if (rank) {
graph.addLabel(node, `${rank}`)
}
}Type Details
- yFiles module
- view-layout-bridge
See Also
Constructors
Parameters
A map of options to pass to the method.
- stopDuration - TimeSpan
- The preferred time limit for the algorithm. This option sets the stopDuration property on the created object.
- weights - ItemMapping<IEdge,number>
- A mapping for edge weights. This option either sets the value directly or recursively sets properties to the instance of the weights property on the created object.
- minimumEdgeLengths - ItemMapping<IEdge,number>
- A mapping for each edge's desired minimum length. This option either sets the value directly or recursively sets properties to the instance of the minimumEdgeLengths property on the created object.
- subgraphNodes - ItemCollection<INode>
- The collection of nodes which define a subset of the graph for the algorithm to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphNodes property on the created object.
- subgraphEdges - ItemCollection<IEdge>
- The collection of edges which define a subset of the graph for the algorithm to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphEdges property on the created object.
Properties
Gets or sets a mapping for each edge's desired minimum length.
Remarks
The minimum length of an edge is the minimum number of ranks it spans.
Minimum edge lengths must not be negative.
Gets or sets the preferred time limit for the algorithm.
Remarks
This is a soft time limit for computing the solution and may be exceeded slightly. In general, the quality of the result may be lower and not optimal if the algorithm terminated early due to this time limit.
MAX_VALUE indicates no time limit which is also the default.
Gets or sets the collection of edges which define a subset of the graph for the algorithm to work on.
Remarks
If nothing is set, all edges of the graph will be processed.
If only excludes are set, all edges in the graph except those provided in excludes are processed.
Note that edges which start or end at nodes which are not in subgraphNodes are automatically ignored by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// prepare the rank assignment algorithm
const algorithm = new RankAssignment({
weights,
minimumEdgeLengths,
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual rank
for (const node of graph.nodes) {
const rank = result.nodeRankIds.get(node)
if (rank) {
graph.addLabel(node, `${rank}`)
}
}Gets or sets the collection of nodes which define a subset of the graph for the algorithm to work on.
Remarks
If nothing is set, all nodes of the graph will be processed.
If only excludes are set, all nodes in the graph except those provided in excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// prepare the rank assignment algorithm
const algorithm = new RankAssignment({
weights,
minimumEdgeLengths,
subgraphNodes: {
// only consider elliptical nodes in the graph
delegate: (node: INode): boolean =>
node.style instanceof ShapeNodeStyle &&
node.style.shape === ShapeNodeShape.ELLIPSE,
// but ignore the first node, regardless of its shape
excludes: graph.nodes.first()!,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual rank
for (const node of graph.nodes) {
const rank = result.nodeRankIds.get(node)
if (rank) {
graph.addLabel(node, `${rank}`)
}
}Gets or sets a mapping for edge weights.
Remarks
Edges with higher weights are more likely to have their minimumEdgeLengths honored.
Weights must not be negative.
Methods
Solves the rank assignment problem.
Preconditions
- The graph must be acyclic.
Parameters
A map of options to pass to the method.
- graph - IGraph
- The input graph to run the algorithm on.
Returns
- ↪RankAssignmentResult
- A RankAssignmentResult with the calculated ranking for each node.
Throws
- Exception({ name: 'InvalidOperationError' })
- If the algorithm cannot create a valid result due to an invalid graph structure or wrongly configured properties.
Examples
// prepare the rank assignment algorithm
const algorithm = new RankAssignment({
weights,
minimumEdgeLengths,
})
// run the algorithm
const result = algorithm.run(graph)
// add labels indicating the actual rank
for (const node of graph.nodes) {
const rank = result.nodeRankIds.get(node)
if (rank) {
graph.addLabel(node, `${rank}`)
}
}