org.codehaus.plexus.util.dag

Class 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 Integer
NOT_VISTITED
private static Integer
VISITED
private static Integer
VISITING

Method Summary

private static boolean
dfsVisit(Vertex vertex, LinkedList cycle, Map vertexStateMap)
static List
hasCycle(DAG graph)
static List
introducesCycle(Vertex vertex)
static List
introducesCycle(Vertex vertex, 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, Map vertexStateMap)
private static boolean
isVisiting(Vertex vertex, Map vertexStateMap)

Field Details

NOT_VISTITED

private static final Integer NOT_VISTITED

VISITED

private static final Integer VISITED

VISITING

private static final Integer VISITING

Method Details

dfsVisit

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

hasCycle

public static List hasCycle(DAG graph)

introducesCycle

public static List introducesCycle(Vertex vertex)

introducesCycle

public static List introducesCycle(Vertex vertex,
                                   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:

isNotVisited

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

isVisiting

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