Package org.jgrapht.alg
Class ConnectivityInspector<V,E>
java.lang.Object
org.jgrapht.alg.ConnectivityInspector<V,E>
- All Implemented Interfaces:
EventListener
,GraphListener<V,
,E> VertexSetListener<V>
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.
- Since:
- Aug 6, 2003
- Author:
- Barak Naveh, John V. Sichi
-
Constructor Summary
ConstructorsConstructorDescriptionCreates a connectivity inspector for the specified directed graph.Creates a connectivity inspector for the specified undirected graph. -
Method Summary
Modifier and TypeMethodDescriptionconnectedSetOf
(V vertex) Returns a set of all vertices that are in the maximally connected component together with the specified vertex.Returns a list ofSet
s, where each set contains all vertices that are in the same maximally connected component.void
Notifies that an edge has been added to the graph.void
Notifies that an edge has been removed from the graph.boolean
Test if the inspected graph is connected.boolean
pathExists
(V sourceVertex, V targetVertex) Tests if there is a path from the specified source vertex to the specified target vertices.void
Notifies that a vertex has been added to the graph.void
Notifies that a vertex has been removed from the graph.
-
Constructor Details
-
ConnectivityInspector
Creates a connectivity inspector for the specified undirected graph.- Parameters:
g
- the graph for which a connectivity inspector to be created.
-
ConnectivityInspector
Creates a connectivity inspector for the specified directed graph.- Parameters:
g
- the graph for which a connectivity inspector to be created.
-
-
Method Details
-
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.
-
connectedSetOf
Returns a set of all vertices that are in the maximally connected component together with the specified vertex. For more on maximally connected component, see http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html.- 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
Returns a list ofSet
s, where each set contains all vertices that are in the same maximally connected component. All graph vertices occur in exactly one set. For more on maximally connected component, see http://www.nist.gov/dads/HTML/maximallyConnectedComponent.html.- Returns:
- Returns a list of
Set
s, where each set contains all vertices that are in the same maximally connected component.
-
edgeAdded
Description copied from interface:GraphListener
Notifies that an edge has been added to the graph.- Specified by:
edgeAdded
in interfaceGraphListener<V,
E> - Parameters:
e
- the edge event.- See Also:
-
edgeRemoved
Description copied from interface:GraphListener
Notifies that an edge has been removed from the graph.- Specified by:
edgeRemoved
in interfaceGraphListener<V,
E> - Parameters:
e
- the edge event.- See Also:
-
pathExists
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
Description copied from interface:VertexSetListener
Notifies that a vertex has been added to the graph.- Specified by:
vertexAdded
in interfaceVertexSetListener<V>
- Parameters:
e
- the vertex event.- See Also:
-
vertexRemoved
Description copied from interface:VertexSetListener
Notifies that a vertex has been removed from the graph.- Specified by:
vertexRemoved
in interfaceVertexSetListener<V>
- Parameters:
e
- the vertex event.- See Also:
-