Package com.jgalgo.alg

Interface WeaklyConnectedComponentsAlgo

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. A builder obtained via newBuilder() may support different options to obtain different implementations.

Author:

Barak Ugav

See Also:

StronglyConnectedComponentsAlgo

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	WeaklyConnectedComponentsAlgo.Builder	A builder for WeaklyConnectedComponentsAlgo objects.

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.Builder	newBuilder()	Create a new weakly connected algorithm builder.
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. The WeaklyConnectedComponentsAlgo.Builder might support different options to obtain different implementations.

Returns:

a default implementation of WeaklyConnectedComponentsAlgo

newBuilder

static WeaklyConnectedComponentsAlgo.Builder newBuilder()

Create a new weakly connected algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build WeaklyConnectedComponentsAlgo objects