Package com.jgalgo.alg.connect

Interface WeaklyConnectedComponentsAlgo

All Known Implementing Classes:
WeaklyConnectedComponentsAlgoAbstract, WeaklyConnectedComponentsAlgoImpl
public interface WeaklyConnectedComponentsAlgo
Weakly Connected components algorithm.

Given a graph \(G=(V,E)\), two vertices \(u,v \in V\) are weakly connected if there is an undirected path from \(u\) to \(v\). A weakly connected component is a maximal set of vertices that each pair in the set is weakly connected. This definition hold for both directed and undirected graphs. For undirected graphs, the strongly and weakly connected components are identical. The set of vertices \(V\) can be partitioned into disjoint weakly connected components.

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav
See Also:

  • Method Details

    • findWeaklyConnectedComponents

      <V, E> VertexPartition<V,E> findWeaklyConnectedComponents(Graph<V,E> g)
      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.

      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

      <V, E> boolean isWeaklyConnected(Graph<V,E> g)
      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.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      true if the graph is weakly connected, false otherwise

    • newInstance

      static WeaklyConnectedComponentsAlgo newInstance()
      Create a new weakly connected components algorithm object.

      This is the recommended way to instantiate a new WeaklyConnectedComponentsAlgo object.

      Returns:
      a default implementation of WeaklyConnectedComponentsAlgo