net.automatalib.util.graphs.scc

Class TarjanSCCVisitor<N,E>

java.lang.Object

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

Type Parameters:

N - node class

E - edge class

All Implemented Interfaces:

GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

@ParametersAreNonnullByDefault
public class TarjanSCCVisitor<N,E>
extends Object
implements GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

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

Author:

Malte Isberner

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	backtrackEdge(N srcNode, net.automatalib.util.graphs.scc.TarjanSCCRecord srcData, E edge, N tgtNode, net.automatalib.util.graphs.scc.TarjanSCCRecord tgtData)
void	finishExploration(N node, net.automatalib.util.graphs.scc.TarjanSCCRecord data) Called when the exploration of a node is finished.
boolean	hasVisited(N node)
GraphTraversalAction	processEdge(N srcNode, net.automatalib.util.graphs.scc.TarjanSCCRecord srcData, E edge, N tgtNode, Holder<net.automatalib.util.graphs.scc.TarjanSCCRecord> dataHolder) Called when an edge is processed.
GraphTraversalAction	processInitial(N initialNode, Holder<net.automatalib.util.graphs.scc.TarjanSCCRecord> outData) Called when a node is processed initially.
boolean	startExploration(N node, net.automatalib.util.graphs.scc.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<net.automatalib.util.graphs.scc.TarjanSCCRecord> outData)

Description copied from interface: GraphTraversalVisitor

Called when a node is processed initially.

Specified by:

processInitial in interface GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

Parameters:

initialNode - the node that is processed

Returns:

the action to perform

startExploration

public boolean startExploration(N node,
                                net.automatalib.util.graphs.scc.TarjanSCCRecord data)

Description copied from interface: GraphTraversalVisitor

Called when the exploration of a node is started.

Specified by:

startExploration in interface GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

Parameters:

node - the node which's exploration is about to be started

data - the user data associated with this node

Returns:

the action to perform

finishExploration

public void finishExploration(N node,
                              net.automatalib.util.graphs.scc.TarjanSCCRecord data)

Description copied from interface: GraphTraversalVisitor

Called when the exploration of a node is finished.

Specified by:

finishExploration in interface GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

Parameters:

node - the node which's exploration is being finished

data - the user data associated with this node

processEdge

public GraphTraversalAction processEdge(N srcNode,
                                        net.automatalib.util.graphs.scc.TarjanSCCRecord srcData,
                                        E edge,
                                        N tgtNode,
                                        Holder<net.automatalib.util.graphs.scc.TarjanSCCRecord> dataHolder)

Description copied from interface: GraphTraversalVisitor

Called when an edge is processed.

Specified by:

processEdge in interface GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

Parameters:

srcNode - the source node

srcData - the user data associated with the source node

edge - the edge that is being processed

Returns:

the action to perform

backtrackEdge

public void backtrackEdge(N srcNode,
                          net.automatalib.util.graphs.scc.TarjanSCCRecord srcData,
                          E edge,
                          N tgtNode,
                          net.automatalib.util.graphs.scc.TarjanSCCRecord tgtData)

Specified by:

backtrackEdge in interface GraphTraversalVisitor<N,E,net.automatalib.util.graphs.scc.TarjanSCCRecord>

hasVisited

public boolean hasVisited(N node)