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 Summary

Constructors

Constructor	Description
WeaklyConnectedComponentsAlgoAbstract()	Default constructor.

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.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

WeaklyConnectedComponentsAlgoAbstract

public WeaklyConnectedComponentsAlgoAbstract()

Default constructor.

Method Detail

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