y.algo
Class NodeAggregation

java.lang.Object
  y.algo.NodeAggregation

public class NodeAggregation
extends java.lang.Object

This class realizes an algorithm that aggregates nodes and creates a hierarchical clustering structure 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 we encode by means of a set of AggregationInfo instances. More precisely, each node of the original graph is mapped to a unique AggregationInfo instance. This mapping is stored in the NodeMap that is passed to method aggregate(Graph, NodeMap). Each AggregationInfo has a reference to its parent which induces a directed tree structure. There is always exactly one AggregationInfo without a parent that represents the root of the tree. Property setNodesOnlyOnLeavesAllowed(boolean) allows to specify whether nodes are only mapped to leaves of the tree structure or if they can also be mapped to inner nodes.

Property setAggregationPolicy(byte) allows to specify whether the algorithm should consider structural properties (i.e., considering the connectivity) for the aggregation or geometric properties (i.e., the distance between nodes). For the second policy, the coordinates of the nodes have to be specified by the user by means of a DataProvider registered with key NODE_CENTER_DPKEY.

Field Summary

static byte	AGGREGATION_POLICY_GEOMETRIC An aggregation policy that specifies that nodes are aggregated according to their geometric position.
static byte	AGGREGATION_POLICY_STRUCTURAL An aggregation policy that specifies that nodes are aggregated according to their structure, that is, the connectivity.
static java.lang.Object	EDGE_DIRECTEDNESS_DPKEY A DataProvider key for specifying the directedness of edges.
static java.lang.Object	EDGE_WEIGHT_DPKEY A DataProvider key for specifying the (non-negative) weights of the edges.
static java.lang.Object	NODE_CENTER_DPKEY A DataProvider key for specifying the coordinates of the nodes.
static java.lang.Object	NODE_TYPE_DPKEY A DataProvider key for specifying the type of the nodes.
static byte	NODE_TYPE_HANDLING_IGNORE A node type handling policy that specifies that the types are ignored.
static byte	NODE_TYPE_HANDLING_SEPARATE_AT_LEAVES A node type handling policy that specifies that nodes of different types are always separated at the leaves.
static byte	NODE_TYPE_HANDLING_SEPARATE_AT_ROOT A node type handling policy that specifies that nodes of different types are always separated right at the root.
static java.lang.Object	NODE_WEIGHT_DPKEY A DataProvider key for specifying the (non-negative) weights of the nodes.
static java.lang.Object	TOP_LEVEL_NODES_DPKEY A DataProvider key for specifying the top-level nodes of the aggregation info.

Constructor Summary

NodeAggregation()
Creates a new NodeAggregation instance with default settings.

Method Summary

void	aggregate(Graph graph, NodeMap aggregationResult) Starts the node aggregation for the specified graph.
byte	getAggregationPolicy() Returns the policy applied for determining the clusters.
int	getMaximumClusterSize() Returns the preferred maximum number of elements contained in a cluster.
long	getMaximumDuration() Returns the maximum duration in milliseconds that this layout algorithm is allowed to run.
int	getMinimumClusterSize() Returns the preferred minimum number of elements contained in a cluster.
byte	getNodeTypeHandlingPolicy() Returns the policy for handling nodes of different type.
boolean	isMultiThreadingAllowed() Returns whether or not the layout algorithm may use multi-threading to reduce the running time.
boolean	isNodesOnlyOnLeavesAllowed() Returns whether or not all original nodes are only mapped to leaves of the directed rooted aggregation tree that represents the hierarchical clustering structure.
void	setAggregationPolicy(byte aggregationPolicy) Specifies the policy applied for determining the clusters.
void	setMaximumClusterSize(int maximumClusterSize) Specifies the preferred maximum number of elements contained in a cluster.
void	setMaximumDuration(long maximumDurationMillis) Specifies the maximum duration in milliseconds that this layout algorithm is allowed to run.
void	setMinimumClusterSize(int minimumClusterSize) Specifies the preferred minimum number of elements contained in a cluster.
void	setMultiThreadingAllowed(boolean multiThreadingAllowed) Specifies whether or not the layout algorithm may use multi-threading to reduce the running time.
void	setNodesOnlyOnLeavesAllowed(boolean nodesOnlyOnLeavesAllowed) Specifies whether or not all original nodes are only mapped to leaves of the directed rooted aggregation tree that represents the hierarchical clustering structure.
void	setNodeTypeHandlingPolicy(byte nodeTypeHandlingPolicy) Specifies the policy for handling nodes of different type.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

NODE_TYPE_HANDLING_IGNORE

public static final byte NODE_TYPE_HANDLING_IGNORE

A node type handling policy that specifies that the types are ignored.

See Also:

setNodeTypeHandlingPolicy(byte), NODE_TYPE_DPKEY, Constant Field Values

NODE_TYPE_HANDLING_SEPARATE_AT_ROOT

public static final byte NODE_TYPE_HANDLING_SEPARATE_AT_ROOT

A node type handling policy that specifies that nodes of different types are always separated right at the root.

Separating at the root means that the top-level cluster of the aggregation is the only one that may (indirectly) contain nodes of different types. The only exception to this rules is if there are group nodes, because a group is a kind of user-specified cluster and, thus, may contain nodes with different types.

See Also:

setNodeTypeHandlingPolicy(byte), NODE_TYPE_DPKEY, Constant Field Values

NODE_TYPE_HANDLING_SEPARATE_AT_LEAVES

public static final byte NODE_TYPE_HANDLING_SEPARATE_AT_LEAVES

A node type handling policy that specifies that nodes of different types are always separated at the leaves.

More precisely, all direct children of a cluster of the aggregation are associated with the same type. Note that, for this policy, the algorithm may assign nodes without type to any cluster (even though the cluster already has some nodes of a specific type).

See Also:

setNodeTypeHandlingPolicy(byte), NODE_TYPE_DPKEY, Constant Field Values

TOP_LEVEL_NODES_DPKEY

public static final java.lang.Object TOP_LEVEL_NODES_DPKEY

A DataProvider key for specifying 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 rules 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.

NODE_CENTER_DPKEY

public static final java.lang.Object NODE_CENTER_DPKEY

A DataProvider key for specifying the coordinates of the nodes.

If the aggregation policy is set to AGGREGATION_POLICY_GEOMETRIC, these coordinates are considered during the aggregation of nodes.

The coordinates are only considered if the aggregation policy is set to AGGREGATION_POLICY_GEOMETRIC.

See Also:

setAggregationPolicy(byte), AGGREGATION_POLICY_GEOMETRIC

NODE_TYPE_DPKEY

public static final java.lang.Object NODE_TYPE_DPKEY

A DataProvider key for specifying the type of the nodes.

Nodes mapped to equal objects are considered to be of the same type. Property setNodeTypeHandlingPolicy(byte) specifies how the algorithm should handle nodes of different type.

See Also:

setNodeTypeHandlingPolicy(byte)

NODE_WEIGHT_DPKEY

public static final java.lang.Object NODE_WEIGHT_DPKEY

A DataProvider key 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.

EDGE_WEIGHT_DPKEY

public static final java.lang.Object EDGE_WEIGHT_DPKEY

A DataProvider key for specifying the (non-negative) weights of the edges.

If the aggregation policy is set to AGGREGATION_POLICY_STRUCTURAL, nodes connected by edges with high weights are more likely to be clustered together.

Edge weights are only considered if the aggregation policy is set to AGGREGATION_POLICY_STRUCTURAL.

See Also:

setAggregationPolicy(byte), AGGREGATION_POLICY_STRUCTURAL

EDGE_DIRECTEDNESS_DPKEY

public static final java.lang.Object EDGE_DIRECTEDNESS_DPKEY

A DataProvider key 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, see Substructures. 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 no DataProvider is registered with this key, the algorithm assumes that all edges have directedness 0.0.

AGGREGATION_POLICY_STRUCTURAL

public static final byte AGGREGATION_POLICY_STRUCTURAL

An aggregation policy that specifies that nodes are aggregated according to their structure, that is, the connectivity.

See Also:

setAggregationPolicy(byte), NODE_CENTER_DPKEY, Constant Field Values

AGGREGATION_POLICY_GEOMETRIC

public static final byte AGGREGATION_POLICY_GEOMETRIC

An aggregation policy that specifies that nodes are aggregated according to their geometric position.

More precisely, nodes that are placed close to each other are more likely to be contained in the same cluster. The coordinates of the nodes have to be specified by the user by means of a DataProvider registered to the graph with key NODE_CENTER_DPKEY.

Using this policy, the edges are completely ignored during the aggregation.

See Also:

setAggregationPolicy(byte), NODE_CENTER_DPKEY, Constant Field Values

Constructor Detail

NodeAggregation

public NodeAggregation()

Creates a new NodeAggregation instance with default settings.

Method Detail

isNodesOnlyOnLeavesAllowed

public boolean isNodesOnlyOnLeavesAllowed()

Returns whether or not all original nodes are only mapped to leaves of the directed rooted aggregation tree that represents the hierarchical clustering structure.

If this property is disabled, nodes can also represent inner nodes and, thus, 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 must be inserted.

Returns:

true if nodes are only mapped to leaves, false otherwise

See Also:

setNodesOnlyOnLeavesAllowed(boolean)

setNodesOnlyOnLeavesAllowed

public void setNodesOnlyOnLeavesAllowed(boolean nodesOnlyOnLeavesAllowed)

Specifies whether or not all original nodes are only mapped to leaves of the directed rooted aggregation tree that represents the hierarchical clustering structure.

If this property is disabled, nodes can also represent inner nodes and, thus, 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 must be inserted.

Default Value:

The default value is true. Nodes are only mapped to leaves of the aggregation tree.

Parameters:

nodesOnlyOnLeavesAllowed - true if nodes should only be mapped to leaves, false otherwise

getMaximumDuration

public long getMaximumDuration()

Returns the maximum duration in milliseconds that this layout algorithm is allowed to run.

The duration needs to be non-negative.

Returns:

a non-negative duration in milliseconds

See Also:

setMaximumDuration(long)

setMaximumDuration

public void setMaximumDuration(long maximumDurationMillis)

Specifies the maximum duration in milliseconds that this layout algorithm is allowed to run.

The duration needs to be non-negative.

Restricting the maximum duration may result in a lower aggregation quality. Furthermore, the real runtime may exceed the maximum duration since the algorithm still has to find a valid solution.

Default Value:

The default value is Long.MAX_VALUE. The algorithm runs unrestricted.

Parameters:

maximumDurationMillis - a non-negative duration in milliseconds

Throws:

java.lang.IllegalArgumentException - if the specified duration has a negative value

getNodeTypeHandlingPolicy

public byte getNodeTypeHandlingPolicy()

Returns the policy for handling nodes of different type.

Returns:

one of the predefined policies for handling nodes of different type

See Also:

setNodeTypeHandlingPolicy(byte)

setNodeTypeHandlingPolicy

public void setNodeTypeHandlingPolicy(byte nodeTypeHandlingPolicy)

Specifies the policy for handling nodes of different type.

Default Value:

The default value is NODE_TYPE_HANDLING_IGNORE

Parameters:

nodeTypeHandlingPolicy - the policy for handling nodes of different type

Throws:

java.lang.IllegalArgumentException - if an unknown policy is provided

getAggregationPolicy

public byte getAggregationPolicy()

Returns the policy applied for determining the clusters.

Returns:

one of the predefined policies for determining the clusters

See Also:

setAggregationPolicy(byte)

setAggregationPolicy

public void setAggregationPolicy(byte aggregationPolicy)

Specifies the policy applied for determining the clusters.

Default Value:

The default value is AGGREGATION_POLICY_STRUCTURAL

Parameters:

aggregationPolicy - the policy applied for determining the clusters

Throws:

java.lang.IllegalArgumentException - if an unknown policy is provided

isMultiThreadingAllowed

public boolean isMultiThreadingAllowed()

Returns whether or not the layout algorithm may use multi-threading to reduce the running time.

Returns:

true if multi-threading is used, false otherwise

See Also:

setMultiThreadingAllowed(boolean)

setMultiThreadingAllowed

public void setMultiThreadingAllowed(boolean multiThreadingAllowed)

Specifies whether or not the layout algorithm may use multi-threading to reduce the running time.

Default Value:

The default value is false. The layout algorithm runs single-threaded.

Parameters:

multiThreadingAllowed - true if multi-threading should be used, false otherwise

getMinimumClusterSize

public int getMinimumClusterSize()

Returns the preferred minimum number of elements contained in a cluster.

The minimum allowed value for this property is 1.

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

Returns:

the preferred minimum number of elements contained in a cluster

See Also:

setMinimumClusterSize(int), setMaximumClusterSize(int)

setMinimumClusterSize

public void setMinimumClusterSize(int minimumClusterSize)

Specifies the preferred minimum number of elements contained in a cluster.

The minimum allowed value for this property is 1.

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

Default Value:

The default value is 5.

Parameters:

minimumClusterSize - the preferred minimum number of elements contained in a cluster

Throws:

java.lang.IllegalArgumentException - if the minimum cluster size is less than 1

See Also:

setMaximumClusterSize(int)

getMaximumClusterSize

public int getMaximumClusterSize()

Returns the preferred maximum number of elements contained in a cluster.

The minimum allowed value for this property is 2.

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

Returns:

the preferred maximum number of elements contained in a cluster

See Also:

setMaximumClusterSize(int), setMinimumClusterSize(int)

setMaximumClusterSize

public void setMaximumClusterSize(int maximumClusterSize)

Specifies the preferred maximum number of elements contained in a cluster.

The minimum allowed value for this property is 2.

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

Default Value:

The default value is 10.

Parameters:

maximumClusterSize - the preferred maximum number of elements contained in a cluster

Throws:

java.lang.IllegalArgumentException - if the maximum cluster size is less than 2

See Also:

setMinimumClusterSize(int)

aggregate

public void aggregate(Graph graph,
                      NodeMap aggregationResult)

Starts the node aggregation for the specified graph.

The aggregation result corresponds to a directed rooted tree which we encode by means of a set of AggregationInfo instances. More precisely, each node of the original graph is mapped to a unique AggregationInfo instance that is stored in the given NodeMap aggregationResult. Each AggregationInfo has a reference to its parent which induces a directed tree structure. There is always exactly one AggregationInfo without a parent that represents the root of the tree.

Parameters:

graph - the input graph

aggregationResult - stores the result of the aggregation