net.sourceforge.combean.interfaces.graph.alg.spath
Interface CycleInPredMapDetectionAlg

All Superinterfaces:

GraphAlgorithm

All Known Implementing Classes:

CycleInPredMapByDoubleTraversalDetectionAlg

public interface CycleInPredMapDetectionAlg
extends GraphAlgorithm

An algorithm to detect a cycle in a graph given by a predecessor map (occurs as subproblem when negative cycles in shortest path trees shall be identified).

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	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 interface net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm

getGraph, run, setGraph

Method Detail

setPredMap

void setPredMap(FixedNodeMap predMap)

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

Parameters:

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

setSingleStartNode

void setSingleStartNode(Node startNode)

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.

Parameters:

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

setPathForCycle

void setPathForCycle(Path p)

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

Parameters:

p - the path where the cycle shall be stored

cycleFound

boolean cycleFound()

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

Returns:

true if the algorithm has detected a cycle.

getCycle

FixedPath getCycle()

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

Returns:

the cycle which has been found.