Package org.codehaus.plexus.util.dag

Class CycleDetector

  • public class CycleDetector
extends java.lang.Object
    Version:
    $Id$

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static java.lang.Integer NOT_VISITED  
      private static java.lang.Integer VISITED  
      private static java.lang.Integer VISITING  

    • Constructor Summary

      Constructors 
      Constructor Description
      CycleDetector()  

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method 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)  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • NOT_VISITED

        private static final java.lang.Integer NOT_VISITED

      • 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<java.lang.String> hasCycle​(DAG graph)

      • introducesCycle

        public 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
        Parameters:
        vertex -
        vertexStateMap -
        Returns:

      • introducesCycle

        public static java.util.List<java.lang.String> introducesCycle​(Vertex vertex)

      • isNotVisited

        private static boolean isNotVisited​(Vertex vertex,
                                    java.util.Map<Vertex,​java.lang.Integer> vertexStateMap)
        Parameters:
        vertex -
        vertexStateMap -
        Returns:

      • isVisiting

        private static boolean isVisiting​(Vertex vertex,
                                  java.util.Map<Vertex,​java.lang.Integer> vertexStateMap)
        Parameters:
        vertex -
        vertexStateMap -
        Returns:

      • dfsVisit

        private static boolean dfsVisit​(Vertex vertex,
                                java.util.LinkedList<java.lang.String> cycle,
                                java.util.Map<Vertex,​java.lang.Integer> vertexStateMap)