chord.util.graph
Class CycleTestingSCCVisitor<Node>

java.lang.Object
  chord.util.graph.CycleTestingSCCVisitor<Node>

All Implemented Interfaces:

IGraphEntityVisitor<Node>

public class CycleTestingSCCVisitor<Node>
extends java.lang.Object
implements IGraphEntityVisitor<Node>

A visitor over the Strongly Connected Components (SCCs) of a directed graph that checks for cycles in the graph.

The visitor visits each SCC of the graph and terminates by throwing an GraphEntityVisitorException as soon as it detects a cycle, namely, if it visits an SCC containing more than one node or an SCC containing a single node with a self-loop.

Author:

Mayur Naik (mhn@cs.stanford.edu)

Constructor Summary

CycleTestingSCCVisitor(IGraph<Node> graph)

Method Summary

void	epilogue() Method called just after finishing visiting all nodes of an entity.
void	prologue() Method called just before starting to visit any node of an entity.
void	visit(Node node) Method called while visiting each node of an entity.

Methods inherited from class java.lang.Object

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

Constructor Detail

CycleTestingSCCVisitor

public CycleTestingSCCVisitor(IGraph<Node> graph)

Method Detail

prologue

public void prologue()

Description copied from interface: IGraphEntityVisitor

Method called just before starting to visit any node of an entity.

Specified by:

prologue in interface IGraphEntityVisitor<Node>

visit

public void visit(Node node)

Description copied from interface: IGraphEntityVisitor

Method called while visiting each node of an entity.

Specified by:

visit in interface IGraphEntityVisitor<Node>

Parameters:

node - The visited node.

epilogue

public void epilogue()

Description copied from interface: IGraphEntityVisitor

Method called just after finishing visiting all nodes of an entity.

Specified by:

epilogue in interface IGraphEntityVisitor<Node>