Package net.automatalib.util.graph.scc

Class TarjanSCCVisitor<N,E>

java.lang.Object

net.automatalib.util.graph.scc.TarjanSCCVisitor<N,E>

Type Parameters:

N - node class

E - edge class

All Implemented Interfaces:

GraphTraversalVisitor<N,E,TarjanSCCRecord>

public class TarjanSCCVisitor<N,E>
extends Object
implements GraphTraversalVisitor<N,E,TarjanSCCRecord>

Depth-first traversal visitor realizing Tarjan's algorithm for finding all strongly-connected components (SCCs) in a graph.

Constructor Summary

Constructors

Constructor	Description
TarjanSCCVisitor(Graph<N,E> graph, SCCListener<N> listener)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	backtrackEdge(N srcNode, TarjanSCCRecord srcData, E edge, N tgtNode, TarjanSCCRecord tgtData)	Called when an edge is backtracked.
void	finishExploration(N node, TarjanSCCRecord data)	Called when the exploration of a node is finished.
boolean	hasVisited(N node)
GraphTraversalAction	processEdge(N srcNode, TarjanSCCRecord srcData, E edge, N tgtNode, Holder<TarjanSCCRecord> tgtHolder)	Called when an edge is processed.
GraphTraversalAction	processInitial(N initialNode, Holder<TarjanSCCRecord> holder)	Called when the initial nodes (as passed to the traversal method) are processed.
boolean	startExploration(N node, TarjanSCCRecord data)	Called when the exploration of a node is started.

Methods inherited from class java.lang.Object

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

Constructor Detail

TarjanSCCVisitor

public TarjanSCCVisitor(Graph<N,E> graph,
                        SCCListener<N> listener)

Constructor.

Parameters:

graph - the graph

listener - the SCC listener to use, must not be null

Method Detail

processInitial

public GraphTraversalAction processInitial(N initialNode,
                                           Holder<TarjanSCCRecord> holder)

Description copied from interface: GraphTraversalVisitor

Called when the initial nodes (as passed to the traversal method) are processed.

Specified by:

processInitial in interface GraphTraversalVisitor<N,E,TarjanSCCRecord>

Parameters:

initialNode - the node that is processed

holder - a writable reference whose (node-specific) data is passed to the corresponding methods during traversal

Returns:

the action to perform

startExploration

public boolean startExploration(N node,
                                TarjanSCCRecord data)

Description copied from interface: GraphTraversalVisitor

Called when the exploration of a node is started.

Specified by:

startExploration in interface GraphTraversalVisitor<N,E,TarjanSCCRecord>

Parameters:

node - the node whose exploration is about to be started

data - the user data associated with this node

Returns:

true, if the node should be explored, false otherwise

finishExploration

public void finishExploration(N node,
                              TarjanSCCRecord data)

Description copied from interface: GraphTraversalVisitor

Called when the exploration of a node is finished.

Specified by:

finishExploration in interface GraphTraversalVisitor<N,E,TarjanSCCRecord>

Parameters:

node - the node whose exploration is being finished

data - the user data associated with this node

processEdge

public GraphTraversalAction processEdge(N srcNode,
                                        TarjanSCCRecord srcData,
                                        E edge,
                                        N tgtNode,
                                        Holder<TarjanSCCRecord> tgtHolder)

Description copied from interface: GraphTraversalVisitor

Called when an edge is processed.

Specified by:

processEdge in interface GraphTraversalVisitor<N,E,TarjanSCCRecord>

Parameters:

srcNode - the source node

srcData - the user data associated with the source node

edge - the edge that is being processed

tgtNode - the target node

tgtHolder - a writable reference to provide user data that should be associated with the target node

Returns:

the action to perform

backtrackEdge

public void backtrackEdge(N srcNode,
                          TarjanSCCRecord srcData,
                          E edge,
                          N tgtNode,
                          TarjanSCCRecord tgtData)

Description copied from interface: GraphTraversalVisitor

Called when an edge is backtracked. This typically happens only in depth-first style traversals.

Specified by:

backtrackEdge in interface GraphTraversalVisitor<N,E,TarjanSCCRecord>

Parameters:

srcNode - the source node

srcData - the user data associated with the source node

edge - the edge that is being processed

tgtNode - the target node

tgtData - the user data associated with the target node

hasVisited

public boolean hasVisited(N node)