Class TarjanSimpleCycles<V,E>

java.lang.Object

org.jgrapht.alg.cycle.TarjanSimpleCycles<V,E>

Type Parameters:

V - the vertex type.

E - the edge type.

All Implemented Interfaces:

DirectedSimpleCycles<V,E>

public class TarjanSimpleCycles<V,E>
extends Object
implements DirectedSimpleCycles<V,E>

Find all simple cycles of a directed graph using the Tarjan's algorithm.

See:
R. Tarjan, Enumeration of the elementary circuits of a directed graph, SIAM J. Comput., 2 (1973), pp. 211-216.

Field Summary

Fields

Modifier and Type	Field	Description
private Consumer<List<V>>	cycleConsumer
private Graph<V,E>	graph
private Set<V>	marked
private ArrayDeque<V>	markedStack
private ArrayDeque<V>	pointStack
private Map<V,Set<V>>	removed
private Map<V,Integer>	vToI

Constructor Summary

Constructors

Constructor	Description
TarjanSimpleCycles()	Create a simple cycle finder with an unspecified graph.
TarjanSimpleCycles(Graph<V,E> graph)	Create a simple cycle finder for the specified graph.

Method Summary

Modifier and Type	Method	Description
private boolean	backtrack(V start, V vertex)
private void	clearState()
void	findSimpleCycles(Consumer<List<V>> consumer)	Find the simple cycles of the graph.
Graph<V,E>	getGraph()	Get the graph
private Set<V>	getRemoved(V v)
private void	initState(Consumer<List<V>> consumer)
void	setGraph(Graph<V,E> graph)	Set the graph
private Integer	toI(V v)

Methods inherited from class Object

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

Methods inherited from interface DirectedSimpleCycles

findSimpleCycles

Field Details

graph

private Graph<V,E> graph

cycleConsumer

private Consumer<List<V>> cycleConsumer

marked

private Set<V> marked

markedStack

private ArrayDeque<V> markedStack

pointStack

private ArrayDeque<V> pointStack

vToI

private Map<V,Integer> vToI

removed

private Map<V,Set<V>> removed

Constructor Details

TarjanSimpleCycles

public TarjanSimpleCycles()

Create a simple cycle finder with an unspecified graph.

TarjanSimpleCycles

public TarjanSimpleCycles(Graph<V,E> graph)

Create a simple cycle finder for the specified graph.

Parameters:

graph - - the DirectedGraph in which to find cycles.

Throws:

IllegalArgumentException - if the graph argument is null.

Method Details

getGraph

public Graph<V,E> getGraph()

Get the graph

Returns:

graph

setGraph

public void setGraph(Graph<V,E> graph)

Set the graph

Parameters:

graph - graph

findSimpleCycles

public void findSimpleCycles(Consumer<List<V>> consumer)

Find the simple cycles of the graph.

Specified by:

findSimpleCycles in interface DirectedSimpleCycles<V,E>

Parameters:

consumer - Consumer that will be called with each cycle found.

backtrack

private boolean backtrack(V start,
 V vertex)

initState

private void initState(Consumer<List<V>> consumer)

clearState

private void clearState()

toI

private Integer toI(V v)

getRemoved

private Set<V> getRemoved(V v)