org._3pq.jgrapht.alg

Class ConnectivityInspector

Implemented Interfaces:
EventListener, GraphListener, VertexSetListener

public class ConnectivityInspector
extends java.lang.Object
implements GraphListener

Allows obtaining various connectivity aspects of a graph. The inspected graph is specified at construction time and cannot be modified. Currently, the inspector supports connected components for an undirected graph and weakly connected components for a directed graph. To find strongly connected components, use StrongConnectivityInspector instead.

The inspector methods work in a lazy fashion: no computation is performed unless immediately necessary. Computation are done once and results and cached within this class for future need.

The inspector is also a GraphListener. If added as a listener to the inspected graph, the inspector will amend internal cached results instead of recomputing them. It is efficient when a few modifications are applied to a large graph. If many modifications are expected it will not be efficient due to added overhead on graph update operations. If inspector is added as listener to a graph other than the one it inspects, results are undefined.

Authors:
Barak Naveh
John V. Sichi
Since:
Aug 6, 2003

Constructor Summary

ConnectivityInspector(DirectedGraph g)
Creates a connectivity inspector for the specified directed graph.
ConnectivityInspector(UndirectedGraph g)
Creates a connectivity inspector for the specified undirected graph.

Method Summary

Set
connectedSetOf(Object vertex)
Returns a set of all vertices that are in the maximally connected component together with the specified vertex.
List
connectedSets()
Returns a list of Sets, where each set contains all vertices that are in the same maximally connected component.
void
edgeAdded(GraphEdgeChangeEvent e)
void
edgeRemoved(GraphEdgeChangeEvent e)
boolean
isGraphConnected()
Test if the inspected graph is connected.
boolean
pathExists(Object sourceVertex, Object targetVertex)
Tests if there is a path from the specified source vertex to the specified target vertices.
void
vertexAdded(GraphVertexChangeEvent e)
void
vertexRemoved(GraphVertexChangeEvent e)

Constructor Details

ConnectivityInspector

public ConnectivityInspector(DirectedGraph g)
Creates a connectivity inspector for the specified directed graph.
Parameters:
g - the graph for which a connectivity inspector to be created.

ConnectivityInspector

public ConnectivityInspector(UndirectedGraph g)
Creates a connectivity inspector for the specified undirected graph.
Parameters:
g - the graph for which a connectivity inspector to be created.

Method Details

connectedSetOf

public Set connectedSetOf(Object vertex)
Parameters:
vertex - the vertex for which the connected set to be returned.
Returns:
a set of all vertices that are in the maximally connected component together with the specified vertex.

connectedSets

public List connectedSets()
Returns:
Returns a list of Sets, where each set contains all vertices that are in the same maximally connected component.

edgeAdded

public void edgeAdded(GraphEdgeChangeEvent e)
Specified by:
edgeAdded in interface GraphListener

edgeRemoved

public void edgeRemoved(GraphEdgeChangeEvent e)
Specified by:
edgeRemoved in interface GraphListener

isGraphConnected

public boolean isGraphConnected()
Test if the inspected graph is connected. An empty graph is not considered connected.
Returns:
true if and only if inspected graph is connected.

pathExists

public boolean pathExists(Object sourceVertex,
                          Object targetVertex)
Tests if there is a path from the specified source vertex to the specified target vertices. For a directed graph, direction is ignored for this interpretation of path.

Note: Future versions of this method might not ignore edge directions for directed graphs.

Parameters:
sourceVertex - one end of the path.
targetVertex - another end of the path.
Returns:
true if and only if there is a path from the source vertex to the target vertex.

vertexAdded

public void vertexAdded(GraphVertexChangeEvent e)
Specified by:
vertexAdded in interface VertexSetListener

vertexRemoved

public void vertexRemoved(GraphVertexChangeEvent e)
Specified by:
vertexRemoved in interface VertexSetListener