NodeAggregation

Show usages

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

Inheritance Hierarchy

NodeAggregation

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++
}

Type Details

yFiles module: view-layout-bridge

Constructors

NodeAggregation

()

Creates a new instance with default settings.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

subgraphNodes - ItemCollection<INode>: The collection of nodes which define a subset of the graph for the algorithms 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 algorithms 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.
topLevelNodes - ItemCollection<INode>: The top-level nodes of the aggregation info. This option either sets the value directly or recursively sets properties to the instance of the topLevelNodes property on the created object.
nodeTypes - ItemMapping<INode,any>: A mapping which maps nodes to an object that specifies their type. This option either sets the value directly or recursively sets properties to the instance of the nodeTypes property on the created object.
nodeWeights - ItemMapping<INode,number>: A mapping for specifying the (non-negative) weights of the nodes. This option either sets the value directly or recursively sets properties to the instance of the nodeWeights property on the created object.
edgeWeights - ItemMapping<IEdge,number>: A mapping for specifying the (non-negative) weights of the edges. This option either sets the value directly or recursively sets properties to the instance of the edgeWeights property on the created object.
edgeDirectedness - ItemMapping<IEdge,number>: A mapping for specifying the directedness of edges. This option either sets the value directly or recursively sets properties to the instance of the edgeDirectedness property on the created object.
aggregationPolicy - NodeAggregationPolicy: The policy applied for determining the clusters. This option sets the aggregationPolicy property on the created object.
nodeTypePolicy - NodeTypePolicy: How node types are handled for aggregation. This option sets the nodeTypePolicy property on the created object.
minimumClusterSize - number: The preferred minimum number of elements contained in a cluster. This option sets the minimumClusterSize property on the created object.
maximumClusterSize - number: The preferred maximum number of elements contained in a cluster. This option sets the maximumClusterSize property on the created object.
stopDuration - TimeSpan: The duration that this algorithm should preferably run before stopping. This option sets the stopDuration property on the created object.
nodesOnlyOnLeaves - boolean: Whether nodes are only mapped to leaves of the directed rooted NodeAggregate tree that represents the hierarchical clustering structure. This option sets the nodesOnlyOnLeaves property on the created object.

Properties

aggregationPolicy

: NodeAggregationPolicy

Gets or sets the policy applied for determining the clusters.

Remarks

Default is STRUCTURAL.

Property Value

One of the predefined policies for determining the clusters.

edgeDirectedness

: ItemMapping<IEdge,number>

Gets or sets a mapping for specifying the directedness of edges.

Remarks

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.

edgeWeights

: ItemMapping<IEdge,number>

Gets or sets a mapping for specifying the (non-negative) weights of the edges.

Remarks

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.

maximumClusterSize

: number

Gets or sets the preferred maximum number of elements contained in a cluster.

Remarks

Default is 10

Property Value

The preferred maximum number of elements associated with a cluster.

Throws

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

The algorithm doesn't guarantee that the found solution observes this value.

minimumClusterSize

: number

Gets or sets the preferred minimum number of elements contained in a cluster.

Remarks

Default is 5

Property Value

The preferred minimum number of elements associated with a cluster.

Throws

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

The algorithm doesn't guarantee that the found solution observes this value.

nodesOnlyOnLeaves

: boolean

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

Remarks

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.

Property Value

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

nodeTypePolicy

: NodeTypePolicy

Gets or sets how node types are handled for aggregation.

Remarks

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

Default is IGNORE.

nodeTypes

: ItemMapping<INode,any>

Gets or sets a mapping which maps nodes to an object that specifies their type.

Remarks

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.

nodeWeights

: ItemMapping<INode,number>

Gets or sets a mapping for specifying the (non-negative) weights of the nodes.

Remarks

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.

stopDuration

: TimeSpan

Gets or sets the duration that this algorithm should preferably run before stopping.

Remarks

The default, which is MAX_VALUE lets the algorithm run unrestricted.

Property Value

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

Throws

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

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.

subgraphEdges

: ItemCollection<IEdge>

Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.

Remarks

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.

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++
}

The edges provided here must be part of the graph which is passed to the run method.

subgraphNodes

: ItemCollection<INode>

Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.

Remarks

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.

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)

The nodes provided here must be part of the graph which is passed to the run method.

topLevelNodes

: ItemCollection<INode>

Gets or sets the top-level nodes of the aggregation info.

Remarks

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.

Methods

run

(graph: IGraph) : NodeAggregationResult

Aggregates the nodes of the given graph and creates a hierarchical clustering structure.

Remarks

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.

Parameters

options - Object
A map of options to pass to the method.

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

Returns

↪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++
}

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.