mapss.dif
Class DIFClusterManager

java.lang.Object
  mapss.dif.DIFClusterManager

Direct Known Subclasses:

SDFClusterManager

public class DIFClusterManager
extends java.lang.Object

A graph class specializing in maintaining cluster hierarchy. It is usually instanciated to distinguished away from the original flattened graph. Clustering is quite often a useful methodology in algorithm design because of the reduced graph size and complexity. The characteristic of hierarchy is similar to DIFHierarchy. However, DIFHierarchy aims more at application design style than at clustering functionality.

Caution: Any derived cluster manager should consider overriding _newEdgeWeight(), _newNodeWeight(), and _clusterNodesComplete(DIFGraph, Collection, Node) with appropriate edge weight, node weight, and clustering strategy, respectively.

Version:

$Id: DIFClusterManager.java 409 2007-05-13 19:47:16Z plishker $

Author:

Mingyung Ko

Constructor Summary

DIFClusterManager(DIFGraph graph)
A constructor with the original graph.

Method Summary

protected java.util.List	_clusterNodesComplete(DIFGraph graph, java.util.Collection nodeCollection, mocgraph.Node superNode) Given a graph and a collection of nodes, replace the subgraph induced by the node collection with a single node N.
protected java.util.Map	_getEdgeMap() Return the new/old edge map after/before a clustering step.
protected boolean	_isReachable(java.util.Collection nodeCollection1, java.util.Collection nodeCollection2) Test whether the second node collection is reachable from the first.
protected boolean	_isReachable(mocgraph.Node node1, mocgraph.Node node2) Test whether the second node is reachable from the first.
protected DIFEdgeWeight	_newEdgeWeight() Return a valid edge weight for a newly created edge in clustering process.
protected DIFNodeWeight	_newNodeWeight() Return a valid node weight for a newly created node in clustering process.
protected mocgraph.Node	_newSuperNode() Return a new super node with weight type suitable for use in this graph.
protected java.util.Collection	_reachInNodes(java.util.Collection nodeCollection) Get the nodes that reach to the given node collection.
protected java.util.Collection	_reachInNodes(mocgraph.Node node) Get the nodes that reach to the given node.
protected java.util.Collection	_reachOutNodes(java.util.Collection nodeCollection) Get the nodes that can be reached from the given node collection.
protected java.util.Collection	_reachOutNodes(mocgraph.Node node) Get the nodes that can be reached from the given node.
protected void	_setSuperNode(mocgraph.Node superNode, DIFGraph subgraph) Set a node as super node with the associated graph.
protected void	_updateReachability(mocgraph.Node superNode, java.util.Collection nodeCollection) Update reachability for a given super node and the associated node collection.
mocgraph.Node	clusterNodes(java.util.Collection nodeCollection) Cluster a collection of nodes and replace it with a super node.
mocgraph.Node	clusterNodes(DIFGraph graph, java.util.Collection nodeCollection) Cluster a collection of nodes in the given graph and replace it with a super node.
DIFGraph	getGraph() Get the clustered graph.
mocgraph.Edge	getOriginalEdge(mocgraph.Edge newEdge) Get the very original edge before any clustering.
mocgraph.Node	getRootNode() Get the root node if the graph is clustered into a single node.
DIFGraph	getSubgraph(mocgraph.Node superNode) Get the subgraph corresponding to the super node.
boolean	isSuperNode(mocgraph.Node node) Test the given node super or not.
boolean	testAcyclicClustering(java.util.Collection nodeCollection) Test whether the clustering of the node collection leads to acyclic topology.

Methods inherited from class java.lang.Object

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

Constructor Detail

DIFClusterManager

public DIFClusterManager(DIFGraph graph)

A constructor with the original graph. The original graph must be an instance of DIFGraph.

Method Detail

clusterNodes

public mocgraph.Node clusterNodes(DIFGraph graph,
                                  java.util.Collection nodeCollection)

Cluster a collection of nodes in the given graph and replace it with a super node. The newly created super node is returned. The given graph can be the top level graph or any lower level subgraph. If it is a subgraph, then the reachability won't be updated. Reachability computation is only for the top level.

Parameters:

graph - The given graph.

nodeCollection - The collection of nodes to cluster.

Returns:

The super node in place of the node collection.

clusterNodes

public mocgraph.Node clusterNodes(java.util.Collection nodeCollection)

Cluster a collection of nodes and replace it with a super node. All nodes in the collection must be in top level graph and cannot be in the subgraph. The newly created super node is returned.

Parameters:

nodeCollection - The collection of nodes to cluster.

Returns:

The super node in place of the node collection.

getGraph

public DIFGraph getGraph()

Get the clustered graph.

Returns:

The clustered graph.

getOriginalEdge

public mocgraph.Edge getOriginalEdge(mocgraph.Edge newEdge)

Get the very original edge before any clustering. New edges are created due to super nodes introduced. The relation between the new edge and its original edge is kept. This may be a useful information in determining alternative candidates selection or tie breaking algorithms.

Parameters:

newEdge - The new edge induced by clustering.

Returns:

The original edge before any clustering.

getRootNode

public mocgraph.Node getRootNode()

Get the root node if the graph is clustered into a single node.

Returns:

The root node.

getSubgraph

public DIFGraph getSubgraph(mocgraph.Node superNode)

Get the subgraph corresponding to the super node.

Parameters:

superNode - The super node.

Returns:

The associated subgraph.

isSuperNode

public boolean isSuperNode(mocgraph.Node node)

Test the given node super or not.

Parameters:

node - The given node.

Returns:

True if it is a super node.

testAcyclicClustering

public boolean testAcyclicClustering(java.util.Collection nodeCollection)

Test whether the clustering of the node collection leads to acyclic topology. This method is for testing purpose and the actual clustering is not performed.

Caution: The present graph status should be acyclic. This method tests cyclic/acyclic property ONLY due to clustering.

Parameters:

nodeCollection - The node collection to test acyclic clustering.

Returns:

True if the clustering will lead to acyclic topology; false otherwise.

_clusterNodesComplete

protected java.util.List _clusterNodesComplete(DIFGraph graph,
                                               java.util.Collection nodeCollection,
                                               mocgraph.Node superNode)

Given a graph and a collection of nodes, replace the subgraph induced by the node collection with a single node N. Depending on users' demand of the clustering functions, multiple results can be generated and returned. Therefore, a List is returned which contains these results and users should be aware of what they are (and their squence in the list). By default, this method returns both the induced subgraph and a map from newly created edges to old edges replaced.

Caution: The clustering implementation considers topology only. Any attributes other than topology may also need to be changed in clustering. Therefore, all sub-classes should consider approriate modifications to all attributes.

Parameters:

graph - The given graph.

nodeCollection - The collection of nodes.

superNode - The super node that will replace the node collection.

Returns:

A list with the first element the subgraph and the second element a map of edges.

_getEdgeMap

protected java.util.Map _getEdgeMap()

Return the new/old edge map after/before a clustering step.

Returns:

The edge map.

_isReachable

protected boolean _isReachable(mocgraph.Node node1,
                               mocgraph.Node node2)

Test whether the second node is reachable from the first.

Parameters:

node1 - The first node.

node2 - The second node.

Returns:

True if node2 is reachable from node1; false otherwise.

_isReachable

protected boolean _isReachable(java.util.Collection nodeCollection1,
                               java.util.Collection nodeCollection2)

Test whether the second node collection is reachable from the first.

Parameters:

nodeCollection1 - The first node collection.

nodeCollection2 - The second node collection.

Returns:

True if nodeCollection2 is reachable from nodeCollection1; false otherwise.

_newEdgeWeight

protected DIFEdgeWeight _newEdgeWeight()

Return a valid edge weight for a newly created edge in clustering process.

Returns:

A valid edge weight.

_newNodeWeight

protected DIFNodeWeight _newNodeWeight()

Return a valid node weight for a newly created node in clustering process.

Returns:

A valid node weight.

_newSuperNode

protected mocgraph.Node _newSuperNode()

Return a new super node with weight type suitable for use in this graph. This method should be overridden in derived classes to return the appropriate type of node weight with the appropriate initialization.

Returns:

A new super node with appropriate node weight.

_reachInNodes

protected java.util.Collection _reachInNodes(mocgraph.Node node)

Get the nodes that reach to the given node.

Parameters:

node - The given node.

Returns:

Nodes that reach to the given node.

_reachInNodes

protected java.util.Collection _reachInNodes(java.util.Collection nodeCollection)

Get the nodes that reach to the given node collection.

Parameters:

node - The given node node collection.

Returns:

Nodes that reach to the given node collection.

_reachOutNodes

protected java.util.Collection _reachOutNodes(mocgraph.Node node)

Get the nodes that can be reached from the given node.

Parameters:

node - The given node.

Returns:

The nodes that can be reached.

_reachOutNodes

protected java.util.Collection _reachOutNodes(java.util.Collection nodeCollection)

Get the nodes that can be reached from the given node collection.

Parameters:

node - The given node Collection.

Returns:

The nodes that can be reached.

_setSuperNode

protected void _setSuperNode(mocgraph.Node superNode,
                             DIFGraph subgraph)

Set a node as super node with the associated graph.

Parameters:

superNode - The node to set as super.

graph - The associated subgraph.

_updateReachability

protected void _updateReachability(mocgraph.Node superNode,
                                   java.util.Collection nodeCollection)

Update reachability for a given super node and the associated node collection.

Parameters:

superNode - The super node.

nodeCollection - The nodes associated with the super node.