C

RankAssignment

Show Usages
Solves the rank assignment problem.
Inheritance Hierarchy

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

Calculating the minimum rank to the nodes.
// 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}`)
  }
}

See Also

Developer's Guide

API

simplexRankAssignment

Members

No filters for this type

Constructors

RankAssignment

()

Parameters

Properties

minimumEdgeLengths

: ItemMapping<IEdge, number>
Gets or sets a mapping for each edge's desired minimum length.

The minimum length of an edge is the minimum number of ranks it spans.

Minimum edge lengths must not be negative.

conversionfinal

stopDuration

: TimeSpan
Gets or sets the preferred time limit for the algorithm.

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.

conversionfinal

subgraphEdges

: ItemCollection<IEdge>
Gets or sets the collection of edges which define a subset of the graph for the algorithm to work on.

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.

The edges provided here must belong to the graph which is passed to the run method.
conversionfinal

Examples

Calculating the minimum rank to the nodes of a subset of the graph
// 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}`)
  }
}

subgraphNodes

: ItemCollection<INode>
Gets or sets the collection of nodes which define a subset of the graph for the algorithm to work on.

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.

The nodes provided here must belong to the graph which is passed to the run method.
conversionfinal

Examples

Calculating the minimum rank to the nodes of a subset of the graph
// 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}`)
  }
}

weights

: ItemMapping<IEdge, number>
Gets or sets a mapping for edge weights.

Edges with higher weights are more likely to have their minimumEdgeLengths honored.

Weights must not be negative.

conversionfinal

Methods

run

(graph: IGraph): RankAssignmentResult
Solves the rank assignment problem.
If the algorithm exceeds the stopDuration , the result might not be optimal in the sense that the sum of all weighted edge lengths is not minimal.
final

Parameters

graph: IGraph
The input graph to run the algorithm on.

Return Value

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

Calculating the minimum rank to the nodes.
// 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}`)
  }
}