Package org.graph4j.connectivity

Class ConnectivityAlgorithm

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.connectivity.ConnectivityAlgorithm
public class ConnectivityAlgorithm extends SimpleGraphAlgorithm
Determines the connected components of a graph. In case of directed graph, the algorithm is executed on its support graph, analyzing the weak-connectivity of the digraph.
Author:
Cristian Frăsinaru

  • Constructor Details

    • ConnectivityAlgorithm

      public ConnectivityAlgorithm(Graph graph)
      Creates an algorithm for analyzing the connectivity of a graph.
      Parameters:
      graph - the input graph.

  • Method Details

    • isConnected

      public boolean isConnected()
      A graph is connected if there is a path from any vertex to any other vertex in the graph.
      Returns:
      true if the graph is connected.

    • countConnectedComponents

      public int countConnectedComponents()
      Determines the number of connected components, without creating the actual components.
      Returns:
      the number of connected components.

    • hasPath

      public boolean hasPath(int v, int u)
      Determines if there is a path from v to u in the graph.
      Parameters:
      v - a vertex number.
      u - a vertex number.
      Returns:
      true if v and u are connected, false otherwise.

    • getConnectedSets

      public List<VertexSet> getConnectedSets()
      Each connected component is represented by its vertices. In order to obtain the subgraph induced by the vertices of a connected component, you may use Graph.subgraph(VertexSet). 
         Graph cc = graph.subgraph(set.vertices());
      Returns:
      the list of the connected sets.

    • getConnectedSet

      public VertexSet getConnectedSet(int v)
      Returns the vertex set of the connected component the specified vertex belongs to.
      Parameters:
      v - a vertex number.
      Returns:
      the connected set containing v.

    • getConnectedComponents

      public List<Graph> getConnectedComponents()
      Returns the connected components of the graph. If only the vertices of the connected components are needed, the getConnectedSets() method should be used.
      Returns:
      the connected components.

    • getConnectedComponent

      public Graph getConnectedComponent(int v)
      Returns the connected component the specified vertex belongs to. If only the vertices of the connected component are needed, the getConnectedSet(int) method should be used.
      Parameters:
      v - a vertex number.
      Returns:
      the connected component containing v.