prajna.util

Class ClusterGraph<N,E>

java.lang.Object

prajna.util.AbstractGraph<N,E>

prajna.util.ClusterGraph<N,E>

Type Parameters:

N - The class representing the nodes of the graph

E - The class representing the edges of the graph

All Implemented Interfaces:

java.io.Serializable, Graph<N,E>

public class ClusterGraph<N,E>
extends AbstractGraph<N,E>

Graph class implementation which provides utilities to keep track of separate clusters within the graph. A cluster is also known as a connected graph, where a path exists from any node to any other node in the connected graph. The ClusterGraph maintains a list of all clusters within the larger graph. It will update the clusters appropriately when new nodes or edges are added.

Author:

Edward Swing

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface prajna.util.Graph

Graph.Segment<N,E>

Constructor Summary

Constructors

Constructor and Description
ClusterGraph(boolean directedFlag) Instantiates a new cluster graph.
ClusterGraph(Graph<? extends N,? extends E> graph) Instantiates a new cluster graph, loading the nodes and edges from the specified graph.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(N node) Add a node to the ClusterGraph.
boolean	addEdge(E edge, N orig, N dest) Add an edge to the ClusterGraph.
Graph<N,E>	getCluster(N node) Get the cluster that a particular node is contained in
java.util.Set<Graph<N,E>>	getClusterSet() Returns a list of the clusters in this graph.
E	getEdge(N n1, N n2) Get the edge between two nodes.
Graph.Segment<N,E>	getEdgeSegment(E edge) Get the edge segment for the specified edge.
java.util.Set<E>	getEdgeSet() Get the set of edges for this graph.
Graph<N,E>	getLargestCluster() Get the largest cluster in this graph.
int	getMaxDistance(N node) finds the greatest distance from node to any other node in the graph.
N	getMostConnected() Returns the node with the most connections in this graph.
java.util.Set<N>	getNodeSet() Get the set of nodes for this graph.
java.util.Set<Graph.Segment<N,E>>	getSegmentSet() Get the set of edge segments for this graph.
boolean	isDirected() Return whether this graph is a directed graph.
boolean	remove(java.lang.Object obj) Remove an object from the graph.
boolean	removeEdge(java.lang.Object obj) Remove the edge from the graph.
java.lang.String	toString() Returns a string representation of the graph.

Methods inherited from class prajna.util.AbstractGraph

addAll, clear, contains, containsEdge, edgeIterator, equals, getNodeEdges, hashCode, isEmpty, iterator, order, size

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ClusterGraph

public ClusterGraph(boolean directedFlag)

Instantiates a new cluster graph. The directedFlag argument determiens whether the graph should be directed or undirected.

Parameters:

directedFlag - the directed flag

ClusterGraph

public ClusterGraph(Graph<? extends N,? extends E> graph)

Instantiates a new cluster graph, loading the nodes and edges from the specified graph. The ClusterGraph is directed if the graph argument is directed, and undirected otherwise

Parameters:

graph - the graph to initially load into this ClusterGraph

Method Detail

add

public boolean add(N node)

Add a node to the ClusterGraph. Since the node will not have any edges, it will be added to its own cluster initially.

Parameters:

node - the node to add

Returns:

true if the graph was modified

addEdge

public boolean addEdge(E edge,
              N orig,
              N dest)

Add an edge to the ClusterGraph. If the origin and destination node are in separate clusters, the clusters are merged

Parameters:

edge - the edge to add

orig - the origin node for the edge

dest - the destination node for the edge

Returns:

true if the graph was modified

getCluster

public Graph<N,E> getCluster(N node)

Get the cluster that a particular node is contained in

Parameters:

node - The node

Returns:

the graph cluster that the node is contained in, or null if the node is not contained in any of the clusters

getClusterSet

public java.util.Set<Graph<N,E>> getClusterSet()

Returns a list of the clusters in this graph. A cluster is a set of connected nodes and edges.

Returns:

a list of the clusters in this graph.

getEdge

public E getEdge(N n1,
        N n2)

Get the edge between two nodes.

Parameters:

n1 - The first node

n2 - The second node

Returns:

the edge between the two nodes, or null if no edge exists.

getEdgeSegment

public Graph.Segment<N,E> getEdgeSegment(E edge)

Get the edge segment for the specified edge.

Parameters:

edge - the edge

Returns:

the segment containing the edge.

getEdgeSet

public java.util.Set<E> getEdgeSet()

Get the set of edges for this graph.

Returns:

the set of edges

getLargestCluster

public Graph<N,E> getLargestCluster()

Get the largest cluster in this graph. This method returns the graph cluster with the greatest number of nodes. If there are two clusters with the same node count, the cluster returned is random.

Returns:

the graph cluster with the highest node count

getMaxDistance

public int getMaxDistance(N node)

finds the greatest distance from node to any other node in the graph. The distance is defined as the total number of edge-hops from one node to another along the shortest path.

Parameters:

node - the node to check distance from

Returns:

the greatest distance from the node to any other node

getMostConnected

public N getMostConnected()

Returns the node with the most connections in this graph. The node with the highest number of edges is returned.

Returns:

the node with the most connections in this graph

getNodeSet

public java.util.Set<N> getNodeSet()

Get the set of nodes for this graph.

Returns:

the set of nodes

getSegmentSet

public java.util.Set<Graph.Segment<N,E>> getSegmentSet()

Get the set of edge segments for this graph.

Returns:

the set of edge segments

isDirected

public boolean isDirected()

Return whether this graph is a directed graph.

Specified by:

isDirected in interface Graph<N,E>

Specified by:

isDirected in class AbstractGraph<N,E>

Returns:

true if the graph is directed, false if it is undirected.

remove

public boolean remove(java.lang.Object obj)

Remove an object from the graph. This removes the object from the node set, and removes any incident edges as well. In the case of a ClusterGraph, the affected cluster must also be checked to see if it is still connected, or needs to be separated into separate clusters.

Specified by:

remove in interface Graph<N,E>

Overrides:

remove in class AbstractGraph<N,E>

Parameters:

obj - the object to remove

Returns:

true if the graph was changed as a result of this operation

removeEdge

public boolean removeEdge(java.lang.Object obj)

Remove the edge from the graph. In the case of a ClusterGraph, the affected cluster must also be checked to see if it is still connected, or needs to be separated into separate clusters.

Specified by:

removeEdge in interface Graph<N,E>

Overrides:

removeEdge in class AbstractGraph<N,E>

Parameters:

obj - the obj

Returns:

true if the graph was changed as a result of this operation

toString

public java.lang.String toString()

Returns a string representation of the graph.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of the graph