Module org.jgrapht.core
Package org.jgrapht.alg.connectivity

Class ConnectivityInspector<V,​E>

java.lang.Object
org.jgrapht.alg.connectivity.ConnectivityInspector<V,​E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
java.util.EventListener, GraphListener<V,​E>, VertexSetListener<V>
public class ConnectivityInspector<V,​E>
extends java.lang.Object
implements GraphListener<V,​E>
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 KosarajuStrongConnectivityInspector 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.

Author:
Barak Naveh, John V. Sichi

  • Constructor Summary

    Constructors 
    Constructor Description
    ConnectivityInspector​(Graph<V,​E> g)
    Creates a connectivity inspector for the specified graph.

  • Method Summary

    Modifier and Type Method Description
    java.util.Set<V> connectedSetOf​(V vertex)
    Returns a set of all vertices that are in the maximally connected component together with the specified vertex.
    java.util.List<java.util.Set<V>> connectedSets()
    Returns a list of Set s, where each set contains all vertices that are in the same maximally connected component.
    void edgeAdded​(GraphEdgeChangeEvent<V,​E> e)
    Notifies that an edge has been added to the graph.
    void edgeRemoved​(GraphEdgeChangeEvent<V,​E> e)
    Notifies that an edge has been removed from the graph.
    boolean isConnected()
    Test if the inspected graph is connected.
    boolean pathExists​(V sourceVertex, V targetVertex)
    Tests whether two vertices lay respectively in the same connected component (undirected graph), or in the same weakly connected component (directed graph).
    void vertexAdded​(GraphVertexChangeEvent<V> e)
    Notifies that a vertex has been added to the graph.
    void vertexRemoved​(GraphVertexChangeEvent<V> e)
    Notifies that a vertex has been removed from the graph.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.jgrapht.event.GraphListener

    edgeWeightUpdated