Package org._3pq.jgrapht.alg

Class CycleDetector

  • public class CycleDetector
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.
    Since:
    Sept 16, 2004
    Author:
    John V. Sichi

    • Constructor Summary

      Constructors 
      Constructor Description
      CycleDetector​(DirectedGraph 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​(java.lang.Object v)
      Performs yes/no cycle detection on an individual vertex.
      java.util.Set findCycles()
      Finds the vertex set for the subgraph of all cycles.
      java.util.Set findCyclesContainingVertex​(java.lang.Object 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

    • Constructor Detail

      • CycleDetector

        public CycleDetector​(DirectedGraph graph)
        Creates a cycle detector for the specified graph. Currently only directed graphs are supported.
        Parameters:
        graph - the DirectedGraph 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​(java.lang.Object 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 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 findCyclesContainingVertex​(java.lang.Object v)
        Finds the vertex set for the subgraph of all cycles which contain a particular vertex.
        Parameters:
        v - the vertex to test
        Returns:
        set of all vertices reachable from v via at least one cycle