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:

StronglyConnectedComponentsAlgo

Method Summary

Modifier and Type	Method	Description
<V,E> VertexPartition<V,E>	findWeaklyConnectedComponents(Graph<V,E> g)	Compute all weakly connected components in a graph.
<V,E> boolean	isWeaklyConnected(Graph<V,E> g)	Check whether a graph is weakly connected.
static WeaklyConnectedComponentsAlgo	newInstance()	Create a new weakly connected components algorithm object.

Method Detail

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