Module org.jgrapht.core

Package org.jgrapht.alg.cycle

Class JohnsonSimpleCycles<V,E>

java.lang.Object

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

Type Parameters:

V - the vertex type.

E - the edge type.

All Implemented Interfaces:

DirectedSimpleCycles<V,E>

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

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

See:
D.B.Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4 (1975), pp. 77-84.

Field Summary

Fields

Modifier and Type	Field	Description
private Set<V>	blocked
private Map<V,Set<V>>	bSets
private Consumer<List<V>>	cycleConsumer
private List<Set<V>>	foundSCCs
private Graph<V,E>	graph
private int	index
private V[]	iToV
private ArrayDeque<V>	path
private Set<V>	pathSet
private ArrayDeque<V>	stack
private Map<V,Integer>	vIndex
private Map<V,Integer>	vLowlink
private Map<V,Integer>	vToI

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
private void	clearMinSCCState()
private void	clearState()
private boolean	findCyclesInSCG(int startIndex, int vertexIndex, Graph<V,E> scg)
private Pair<Graph<V,E>,Integer>	findMinSCSG(int startIndex)
private List<Set<V>>	findSCCS(int startIndex)
void	findSimpleCycles(Consumer<List<V>> consumer)	Find the simple cycles of the graph.
private Set<V>	getBSet(V v)
private void	getSCCs(int startIndex, int vertexIndex)
private void	initMinSCGState()
private void	initState(Consumer<List<V>> consumer)
private Integer	toI(V vertex)
private V	toV(Integer i)
private void	unblock(V vertex)

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.alg.cycle.DirectedSimpleCycles

findSimpleCycles

Field Details

graph

private Graph<V,E> graph

cycleConsumer

private Consumer<List<V>> cycleConsumer

iToV

private V[] iToV

vToI

private Map<V,Integer> vToI

blocked

private Set<V> blocked

bSets

private Map<V,Set<V>> bSets

stack

private ArrayDeque<V> stack

foundSCCs

private List<Set<V>> foundSCCs

index

private int index

vIndex

private Map<V,Integer> vIndex

vLowlink

private Map<V,Integer> vLowlink

path

private ArrayDeque<V> path

pathSet

private Set<V> pathSet

Constructor Details

JohnsonSimpleCycles

public JohnsonSimpleCycles(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

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.

findMinSCSG

private Pair<Graph<V,E>,Integer> findMinSCSG(int startIndex)

findSCCS

private List<Set<V>> findSCCS(int startIndex)

getSCCs

private void getSCCs(int startIndex,
 int vertexIndex)

findCyclesInSCG

private boolean findCyclesInSCG(int startIndex,
 int vertexIndex,
 Graph<V,E> scg)

unblock

private void unblock(V vertex)

initState

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

clearState

private void clearState()

initMinSCGState

private void initMinSCGState()

clearMinSCCState

private void clearMinSCCState()

toI

private Integer toI(V vertex)

toV

private V toV(Integer i)

getBSet

private Set<V> getBSet(V v)