Package org.graph4j.connectivity

Class BridgeDetectionAlgorithm

java.lang.Object

org.graph4j.SimpleGraphAlgorithm

org.graph4j.connectivity.BridgeDetectionAlgorithm

public class BridgeDetectionAlgorithm
extends SimpleGraphAlgorithm

A bridge in an undirected graph is defined as an edge which, when removed, increases the number of connected components in the graph). The algorithm runs in linear time, and is based on depth-first search.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.SimpleGraphAlgorithm

graph

Constructor Summary

Constructors

Constructor	Description
BridgeDetectionAlgorithm(Graph graph)

Method Summary

Modifier and Type	Method	Description
EdgeSet	getBridges()
boolean	isBridgeless()

Methods inherited from class org.graph4j.SimpleGraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Constructor Details

BridgeDetectionAlgorithm

public BridgeDetectionAlgorithm(Graph graph)

Parameters:

graph - the input graph.

Method Details

isBridgeless

public boolean isBridgeless()

Returns:

true if the graph contains no bridge.

getBridges

public EdgeSet getBridges()

Returns:

the bridges of the graph.