Class CycleDetector<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class CycleDetector<V,​E>
    extends java.lang.Object
    Performs cycle detection on a graph. The inspected graph is specified at construction time and cannot be modified. Currently, the detector supports only directed graphs.
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  CycleDetector.CycleDetectedException
      Exception thrown internally when a cycle is detected during a yes/no cycle test.
      private static class  CycleDetector.ProbeIterator<V,​E>
      Version of DFS which maintains a backtracking path used to probe for cycles.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private Graph<V,​E> graph
      Graph on which cycle detection is being performed.
    • Constructor Summary

      Constructors 
      Constructor Description
      CycleDetector​(Graph<V,​E> graph)
      Creates a cycle detector for the specified graph.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean detectCycles()
      Performs yes/no cycle detection on the entire graph.
      boolean detectCyclesContainingVertex​(V v)
      Performs yes/no cycle detection on an individual vertex.
      private void execute​(java.util.Set<V> s, V v)  
      java.util.Set<V> findCycles()
      Finds the vertex set for the subgraph of all cycles.
      java.util.Set<V> findCyclesContainingVertex​(V v)
      Finds the vertex set for the subgraph of all cycles which contain a particular vertex.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private Graph<V,​E> graph
        Graph on which cycle detection is being performed.
    • Constructor Detail

      • CycleDetector

        public CycleDetector​(Graph<V,​E> graph)
        Creates a cycle detector for the specified graph. Currently only directed graphs are supported.
        Parameters:
        graph - the directed graph in which to detect cycles
    • Method Detail

      • detectCycles

        public boolean detectCycles()
        Performs yes/no cycle detection on the entire graph.
        Returns:
        true iff the graph contains at least one cycle
      • detectCyclesContainingVertex

        public boolean detectCyclesContainingVertex​(V v)
        Performs yes/no cycle detection on an individual vertex.
        Parameters:
        v - the vertex to test
        Returns:
        true if v is on at least one cycle
      • findCycles

        public java.util.Set<V> findCycles()
        Finds the vertex set for the subgraph of all cycles.
        Returns:
        set of all vertices which participate in at least one cycle in this graph
      • findCyclesContainingVertex

        public java.util.Set<V> findCyclesContainingVertex​(V v)
        Finds the vertex set for the subgraph of all cycles which contain a particular vertex.

        REVIEW jvs 25-Aug-2006: This implementation is not guaranteed to cover all cases. If you want to be absolutely certain that you report vertices from all cycles containing v, it's safer (but less efficient) to use StrongConnectivityAlgorithm instead and return the strongly connected component containing v.

        Parameters:
        v - the vertex to test
        Returns:
        set of all vertices reachable from v via at least one cycle
      • execute

        private void execute​(java.util.Set<V> s,
                             V v)