Package com.jgalgo.alg.connect

Class WeaklyConnectedComponentsAlgoAbstract

java.lang.Object
com.jgalgo.alg.connect.WeaklyConnectedComponentsAlgoAbstract
All Implemented Interfaces:
WeaklyConnectedComponentsAlgo
Direct Known Subclasses:
WeaklyConnectedComponentsAlgoImpl
public abstract class WeaklyConnectedComponentsAlgoAbstract extends Object implements WeaklyConnectedComponentsAlgo
Abstract class for computing weakly connected components in a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:
Barak Ugav

  • Constructor Details

    • WeaklyConnectedComponentsAlgoAbstract

      public WeaklyConnectedComponentsAlgoAbstract()
      Default constructor.

  • Method Details

    • findWeaklyConnectedComponents

      public <V, E> VertexPartition<V,E> findWeaklyConnectedComponents(Graph<V,E> g)
      Description copied from interface: WeaklyConnectedComponentsAlgo
      Compute all weakly connected components in a graph.

      Given a directed graph, if we replace all the directed edges with undirected edges and compute the (strongly) connected components in the result undirected graph.

      If g is an IntGraph, a IVertexPartition object will be returned.

      Specified by:
      findWeaklyConnectedComponents in interface WeaklyConnectedComponentsAlgo
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      a result object containing the partition of the vertices into weakly connected components

    • isWeaklyConnected

      public <V, E> boolean isWeaklyConnected(Graph<V,E> g)
      Description copied from interface: WeaklyConnectedComponentsAlgo
      Check whether a graph is weakly connected.

      A graph is weakly connected if there is an undirected path from any vertex to any other vertex. Namely if the the whole graph is a single weakly connected component.

      If g is an IntGraph, a IVertexPartition object will be returned.

      Specified by:
      isWeaklyConnected in interface WeaklyConnectedComponentsAlgo
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      true if the graph is weakly connected, false otherwise