public class DirectedAcyclicGraphVerifier extends Object
Constructor and Description |
---|
DirectedAcyclicGraphVerifier() |
Modifier and Type | Method and Description |
---|---|
static <T> int |
findVertex(List<Vertex<T>> vertexList,
String name) |
static <T> void |
resetVertices(List<Vertex<T>> vertices)
Resets all the vertices so that the visitation flags and indegrees are
reset to their start values.
|
static <T> void |
topologicalSort(List<Vertex<T>> vertices)
Sort a set of vertices so that no dependency is before its vertex.
|
static <T> void |
verify(List<Vertex<T>> vertices)
Verify a set of vertices and all their dependencies have no cycles.
|
static <T> void |
verify(Vertex<T> vertex)
Verify that a vertex and its set of dependencies have no cycles.
|
public static <T> void verify(Vertex<T> vertex) throws CyclicDependencyException
vertex
- The vertex we want to test.CyclicDependencyException
- if there is a cycle.public static <T> void verify(List<Vertex<T>> vertices) throws CyclicDependencyException
vertices
- The list of vertices we want to test.CyclicDependencyException
- if there is a cycle.public static <T> void topologicalSort(List<Vertex<T>> vertices) throws CyclicDependencyException
Implementation Detail: This particular algorithm is a more efficient variation of the typical Topological Sort algorithm. It uses a Queue (Linked List) to ensure that each edge (connection between two vertices) or vertex is checked only once. The efficiency is O = (|V| + |E|).
vertices
- CyclicDependencyException
public static <T> void resetVertices(List<Vertex<T>> vertices)
vertices
- Copyright © 2020 The Apache Software Foundation. All rights reserved.