public class CycleDetector
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
private static java.lang.Integer |
NOT_VISTITED |
private static java.lang.Integer |
VISITED |
private static java.lang.Integer |
VISITING |
Constructor and Description |
---|
CycleDetector() |
Modifier and Type | Method and Description |
---|---|
private static boolean |
dfsVisit(Vertex vertex,
java.util.LinkedList<java.lang.String> cycle,
java.util.Map<Vertex,java.lang.Integer> vertexStateMap) |
static java.util.List<java.lang.String> |
hasCycle(DAG graph) |
static java.util.List<java.lang.String> |
introducesCycle(Vertex vertex) |
static java.util.List<java.lang.String> |
introducesCycle(Vertex vertex,
java.util.Map<Vertex,java.lang.Integer> vertexStateMap)
This method will be called when an edge 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<Vertex,java.lang.Integer> vertexStateMap) |
private static boolean |
isVisiting(Vertex vertex,
java.util.Map<Vertex,java.lang.Integer> vertexStateMap) |
private static final java.lang.Integer NOT_VISTITED
private static final java.lang.Integer VISITING
private static final java.lang.Integer VISITED
public static java.util.List<java.lang.String> hasCycle(DAG graph)
public static java.util.List<java.lang.String> introducesCycle(Vertex vertex, java.util.Map<Vertex,java.lang.Integer> vertexStateMap)
vertex
- vertexStateMap
- public static java.util.List<java.lang.String> introducesCycle(Vertex vertex)
private static boolean isNotVisited(Vertex vertex, java.util.Map<Vertex,java.lang.Integer> vertexStateMap)
vertex
- vertexStateMap
- private static boolean isVisiting(Vertex vertex, java.util.Map<Vertex,java.lang.Integer> vertexStateMap)
vertex
- vertexStateMap
-