org.codehaus.plexus.util.dag
Class CycleDetector

java.lang.Object
  extended by org.codehaus.plexus.util.dag.CycleDetector

public class CycleDetector
extends java.lang.Object

Version:
$Id: CycleDetector.java 1106 2004-10-07 19:29:57Z jdcasey $
Author:
Michal Maczka

Field Summary
private static java.lang.Integer NOT_VISTITED
           
private static java.lang.Integer VISITED
           
private static java.lang.Integer VISITING
           
 
Constructor Summary
CycleDetector()
           
 
Method Summary
private static boolean dfsVisit(Vertex vertex, java.util.LinkedList cycle, java.util.Map vertexStateMap)
           
static java.util.List hasCycle(DAG graph)
           
static java.util.List introducesCycle(Vertex vertex)
           
static java.util.List introducesCycle(Vertex vertex, java.util.Map vertexStateMap)
          This method will be called when an egde leading to given vertex was added and we want to check if introduction of this edge has not resulted in apparition of cycle in the graph
private static boolean isNotVisited(Vertex vertex, java.util.Map vertexStateMap)
           
private static boolean isVisiting(Vertex vertex, java.util.Map vertexStateMap)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NOT_VISTITED

private static final java.lang.Integer NOT_VISTITED

VISITING

private static final java.lang.Integer VISITING

VISITED

private static final java.lang.Integer VISITED
Constructor Detail

CycleDetector

public CycleDetector()
Method Detail

hasCycle

public static java.util.List hasCycle(DAG graph)

introducesCycle

public static java.util.List introducesCycle(Vertex vertex,
                                             java.util.Map vertexStateMap)
This method will be called when an egde leading to given vertex was added and we want to check if introduction of this edge has not resulted in apparition of cycle in the graph

Parameters:
vertex -
vertexStateMap -
Returns:

introducesCycle

public static java.util.List introducesCycle(Vertex vertex)

isNotVisited

private static boolean isNotVisited(Vertex vertex,
                                    java.util.Map vertexStateMap)
Parameters:
vertex -
vertexStateMap -
Returns:

isVisiting

private static boolean isVisiting(Vertex vertex,
                                  java.util.Map vertexStateMap)
Parameters:
vertex -
vertexStateMap -
Returns:

dfsVisit

private static boolean dfsVisit(Vertex vertex,
                                java.util.LinkedList cycle,
                                java.util.Map vertexStateMap)