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 classE
- 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
All Methods Instance Methods Concrete Methods 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.
-
-
-
Constructor Detail
-
TarjanSCCVisitor
public TarjanSCCVisitor(Graph<N,E> graph, SCCListener<N> listener)
Constructor.- Parameters:
graph
- the graphlistener
- 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 interfaceGraphTraversalVisitor<N,E,TarjanSCCRecord>
- Parameters:
initialNode
- the node that is processedholder
- 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 interfaceGraphTraversalVisitor<N,E,TarjanSCCRecord>
- Parameters:
node
- the node whose exploration is about to be starteddata
- 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 interfaceGraphTraversalVisitor<N,E,TarjanSCCRecord>
- Parameters:
node
- the node whose exploration is being finisheddata
- 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 interfaceGraphTraversalVisitor<N,E,TarjanSCCRecord>
- Parameters:
srcNode
- the source nodesrcData
- the user data associated with the source nodeedge
- the edge that is being processedtgtNode
- the target nodetgtHolder
- 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 interfaceGraphTraversalVisitor<N,E,TarjanSCCRecord>
- Parameters:
srcNode
- the source nodesrcData
- the user data associated with the source nodeedge
- the edge that is being processedtgtNode
- the target nodetgtData
- the user data associated with the target node
-
hasVisited
public boolean hasVisited(N node)
-
-