C

NodeAggregation

Show Usages
Aggregates the nodes of a given graph and creates a hierarchical clustering structure subject to user-specified constraints.
Inheritance Hierarchy

Remarks

The result is subject to user-specified constraints like the type of nodes as well as the preferred minimum and maximum size of a cluster. The result of the aggregation can be used to (interactively) visualize parts of large graphs.

Note that the resulting clustering structure corresponds to a directed rooted tree which is encoded by means of a set of NodeAggregate instances. More precisely, each node of the original graph is mapped to a unique NodeAggregate instance. Each NodeAggregate has a reference to its parent which induces a directed tree structure. There is always exactly one NodeAggregate without a parent that represents the root of the tree.

aggregationPolicy specifies whether the algorithm should consider STRUCTURAL properties (i.e., considering the connectivity) for the aggregation or GEOMETRIC properties (i.e., the distance between nodes).

Examples

// prepare the node aggregation algorithm
const algorithm = new NodeAggregation({
  // group according to the node types which are specified in the node's tag
  nodeTypePolicy: NodeTypePolicy.SEPARATE_AT_ROOT,
  nodeTypes: (node: INode): any => node.tag,
  // determine substructures according to the graph structure, not the geometry
  aggregationPolicy: NodeAggregationPolicy.STRUCTURAL,
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the nodes of the aggregates with different styles
// group by the top level aggregates
let index = 0
for (const aggregate of result.root.children) {
  for (const node of aggregate.nodes) {
    graph.setStyle(node, clusterStyles.get(index)!)
  }
  index++
}

See Also

Developer's Guide

Members

No filters for this type

Constructors

NodeAggregation

()
Creates a new instance with default settings.

Parameters

Properties

aggregationPolicy

: NodeAggregationPolicy
Gets or sets the policy applied for determining the clusters.
Default is STRUCTURAL.
conversionfinal

Property Value

One of the predefined policies for determining the clusters.

See Also

Developer's Guide

edgeDirectedness

: ItemMapping<IEdge, number>
Gets or sets a mapping for specifying the directedness of edges.
Generally, for this node aggregation algorithm, the effect of specifying an edge directedness is quite low. It is mainly used for the detection of substructures, e.g. TreeSubstructures or CycleSubstructures. A substructure is only identified as such if all edges are either undirected or consistently directed with respect to the specified directedness.
  • A directedness value of 1 indicates that the edge is considered to be directed from source to target.
  • A directedness value of -1 indicates that the edge is considered to be directed from target to source.
  • A directedness value of 0 indicates that the edge is considered to be undirected.
If left unspecified, the algorithm assumes that all edges have directedness 0.0.
conversionfinal

edgeWeights

: ItemMapping<IEdge, number>
Gets or sets a mapping for specifying the (non-negative) weights of the edges.
If the aggregationPolicy is set to STRUCTURAL nodes connected by edges with high weights are more likely to be clustered together.
Edge weights are only considered if the aggregationPolicy mode is set to STRUCTURAL.
conversionfinal

maximumClusterSize

: number
Gets or sets the preferred maximum number of elements contained in a cluster.
Default is 10
The algorithm doesn't guarantee that the found solution observes this value.
final

Property Value

The preferred maximum number of elements associated with a cluster.

Throws

Exception ({ name: 'ArgumentError' })
if a value < 2 is set.

See Also

Developer's Guide

minimumClusterSize

: number
Gets or sets the preferred minimum number of elements contained in a cluster.
Default is 5
The algorithm doesn't guarantee that the found solution observes this value.
final

Property Value

The preferred minimum number of elements associated with a cluster.

Throws

Exception ({ name: 'ArgumentError' })
if a value < 1 is set.

See Also

Developer's Guide

nodesOnlyOnLeaves

: boolean
Gets or sets whether nodes are only mapped to leaves of the directed rooted NodeAggregate tree that represents the hierarchical clustering structure.

If set to false, nodes can also represent inner nodes and, thus, the associated NodeAggregate can contain other node elements. This may allow a more efficient representation of the resulting tree structure. For example, for a star-like structure in the input graph, the root of the star can directly represent the parent aggregate of the star. Otherwise, an additional virtual tree node is inserted.

Default is true.

final

Property Value

true if nodes are only mapped to leaves, false otherwise.

See Also

Developer's Guide

nodeTypePolicy

: NodeTypePolicy
Gets or sets how node types are handled for aggregation.

The types are provided by nodeTypes. Nodes with equal objects mapped to them are handled as equal types.

Default is IGNORE.

conversionfinal

See Also

Developer's Guide

nodeTypes

: ItemMapping<INode, any>
Gets or sets a mapping which maps nodes to an object that specifies their type.

The type objects can be arbitrary objects. Nodes mapped to equal objects are considered to be of the same type. After aggregating, the resulting clusters do not contain nodes with different type.

Node types are ignored if nothing is set here. Also, if the nodeTypePolicy is set to IGNORE, the node types are not considered, either.

conversionfinal

See Also

Developer's Guide

nodeWeights

: ItemMapping<INode, number>
Gets or sets a mapping for specifying the (non-negative) weights of the nodes.
Depending on the exact setting, the algorithm applies multiple different aggregation approaches and chooses the best one. If nodes have weights, it prefers aggregation results where nodes with higher weight are closer to the root of the aggregation hierarchy.
conversionfinal

See Also

Developer's Guide

stopDuration

: TimeSpan
Gets or sets the duration that this algorithm should preferably run before stopping.
The default, which is MAX_VALUE lets the algorithm run unrestricted.
Restricting the stop duration may result in a lower layout quality. Furthermore, the real runtime may exceed the stop duration since the aggregation algorithm still has to find a valid solution.
conversionfinal

Property Value

The non-negative duration the algorithm is allowed to run.

Throws

Exception ({ name: 'ArgumentError' })
if the specified duration is less than ZERO.

subgraphEdges

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

If nothing is set, all edges of the graph will be processed.

If only the excludes are set, all edges in the graph except those provided in the excludes are processed.

Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered 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 be part of the graph which is passed to the run method.
conversionfinal

Examples

Aggregating the clusters on a subset of the graph
// prepare the node aggregation algorithm
const algorithm = new NodeAggregation({
  // Ignore edges without target arrow heads
  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)

// highlight the nodes of the aggregates with different styles
// group by the top level aggregates
let index = 0
for (const aggregate of result.root.children) {
  for (const node of aggregate.nodes) {
    graph.setStyle(node, clusterStyles.get(index)!)
  }
  index++
}

subgraphNodes

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

If nothing is set, all nodes of the graph will be processed.

If only the excludes are set, all nodes in the graph except those provided in the 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 be part of the graph which is passed to the run method.
conversionfinal

Examples

Aggregating the clusters on a subset of the graph
// prepare the node aggregation algorithm
const algorithm = new NodeAggregation({
  subgraphNodes: {
    // only consider elliptical nodes in the graph
    includes: (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)

// highlight the nodes of the aggregates with different styles
// group by the top level aggregates
let index = 0
for (const aggregate of result.root.children) {
  for (const node of aggregate.nodes) {
    graph.setStyle(node, clusterStyles.get(index)!)
  }
  index++
}
Considering only selected nodes
algorithm.subgraphNodes = graphComponent.selection.nodes
Ignoring all group nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)
Considering selected nodes but ignoring group nodes
algorithm.subgraphNodes = graphComponent.selection.nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)

topLevelNodes

: ItemCollection<INode>
Gets or sets the top-level nodes of the aggregation info.
Top-level nodes are directly contained in the root cluster of the aggregation result or in direct children of the root if there are top-level nodes with different types (nodes of different type are not allowed to be directly contained in the same cluster). The only exception to this rule is if there are group nodes because a group is a kind of user-specified cluster and, thus, a top-level node contained in a group is always placed in the cluster associated with that group.
conversionfinal

See Also

Developer's Guide

Methods

run

(graph: IGraph): NodeAggregationResult
Aggregates the nodes of the given graph and creates a hierarchical clustering structure.
The aggregation result corresponds to a directed rooted tree which is encoded by means of a set of NodeAggregate instances. More precisely, each node of the original graph is mapped to a unique NodeAggregate instance. Each NodeAggregate has references to its parent and children which induces a directed tree structure. There is always exactly one NodeAggregate without a parent that represents the root of the tree.
The result obtained from this algorithm is a snapshot which is no longer valid once the graph has changed, e.g. by adding or removing nodes or edges.
final

Parameters

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

Return Value

NodeAggregationResult
The hierarchical clustering of the graph.

Throws

Exception ({ name: 'InvalidOperationError' })
If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.

Examples

// prepare the node aggregation algorithm
const algorithm = new NodeAggregation({
  // group according to the node types which are specified in the node's tag
  nodeTypePolicy: NodeTypePolicy.SEPARATE_AT_ROOT,
  nodeTypes: (node: INode): any => node.tag,
  // determine substructures according to the graph structure, not the geometry
  aggregationPolicy: NodeAggregationPolicy.STRUCTURAL,
})
// run the algorithm
const result = algorithm.run(graph)

// highlight the nodes of the aggregates with different styles
// group by the top level aggregates
let index = 0
for (const aggregate of result.root.children) {
  for (const node of aggregate.nodes) {
    graph.setStyle(node, clusterStyles.get(index)!)
  }
  index++
}