net.sourceforge.combean.graph.alg.spath
Class CycleInPredMapByDoubleTraversalDetectionAlg

java.lang.Object
  net.sourceforge.combean.graph.alg.AbstractGraphAlg
      net.sourceforge.combean.graph.alg.spath.CycleInPredMapByDoubleTraversalDetectionAlg

All Implemented Interfaces:

GraphAlgorithm, CycleInPredMapDetectionAlg

public class CycleInPredMapByDoubleTraversalDetectionAlg
extends AbstractGraphAlg
implements CycleInPredMapDetectionAlg

Identify cycles in a predecessor map with a two pass algorithm. In the first pass a node in a cycle is identified (if such a node exists) and in a second pass the cycle is constructed.

Constructor Summary

CycleInPredMapByDoubleTraversalDetectionAlg()
constructor

Method Summary

boolean	cycleFound() Check whether a cycle has been found (must be called after run()).
FixedPath	getCycle() Retrieve the cycle that has been found.
void	run() Execute the algorithm.
void	setPathForCycle(Path p) Optional.
void	setPredMap(FixedNodeMap predMap) The predecessor map defining the graph where the cycle shall be found.
void	setSingleStartNode(Node startNode) Search for cycles starting from a single start node.

Methods inherited from class net.sourceforge.combean.graph.alg.AbstractGraphAlg

getGraph, setGraph

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm

getGraph, setGraph

Constructor Detail

CycleInPredMapByDoubleTraversalDetectionAlg

public CycleInPredMapByDoubleTraversalDetectionAlg()

constructor

Method Detail

setPredMap

public void setPredMap(FixedNodeMap predMap)

Description copied from interface: CycleInPredMapDetectionAlg

The predecessor map defining the graph where the cycle shall be found.

Specified by:

setPredMap in interface CycleInPredMapDetectionAlg

Parameters:

predMap - a node map which contains the predecessor of every node (or null of a node has no predecessor)

setSingleStartNode

public void setSingleStartNode(Node startNode)

Description copied from interface: CycleInPredMapDetectionAlg

Search for cycles starting from a single start node. If this method is called, only the predecessors of the given node are checked for containing a cycle. Otherwise, the complete node map is checked. For this variant of the algorithm the global nodes property is not required.

Specified by:

setSingleStartNode in interface CycleInPredMapDetectionAlg

Parameters:

startNode - the node where the search for cycles shall be started

setPathForCycle

public void setPathForCycle(Path p)

Description copied from interface: CycleInPredMapDetectionAlg

Optional. Set a Path object which shall be filled with the cycle found (if any).

Specified by:

setPathForCycle in interface CycleInPredMapDetectionAlg

Parameters:

p - the path where the cycle shall be stored

run

public void run()

Description copied from interface: GraphAlgorithm

Execute the algorithm.

Specified by:

run in interface GraphAlgorithm

cycleFound

public boolean cycleFound()

Description copied from interface: CycleInPredMapDetectionAlg

Check whether a cycle has been found (must be called after run()).

Specified by:

cycleFound in interface CycleInPredMapDetectionAlg

Returns:

true if the algorithm has detected a cycle.

getCycle

public FixedPath getCycle()

Description copied from interface: CycleInPredMapDetectionAlg

Retrieve the cycle that has been found. May only be called if cycleFound() returns true.

Specified by:

getCycle in interface CycleInPredMapDetectionAlg

Returns:

the cycle which has been found.