Package org.graph4j.route

Class CycleFinder

java.lang.Object
org.graph4j.GraphAlgorithm
org.graph4j.route.CycleFinder
public class CycleFinder extends GraphAlgorithm
Algorithms for finding cycles in a directed or undirected graph. Multigraphs and pseudographs are supported.
Author:
Cristian Frăsinaru

  • Constructor Details

    • CycleFinder

      public CycleFinder(Graph graph)
      Parameters:
      graph - the input graph.

  • Method Details

    • containsCycle

      public boolean containsCycle()
      Returns:
      true if the graph contains a cycle.

    • findAnyCycle

      public Cycle findAnyCycle()
      Uses DFS in order to find a cycle.
      Returns:
      the first cycle found, or null if the graph is acyclic.

    • findAnyCycle

      public Cycle findAnyCycle(int target)
      Parameters:
      target - a vertex number.
      Returns:
      the first cycle found that passes through target, or null if none exists.

    • findShortestCycle

      public Cycle findShortestCycle()
      Uses BFS in order to find a cycle.
      Returns:
      the shortest cycle in the graph, or null if the graph is acyclic.

    • findShortestCycle

      public Cycle findShortestCycle(int target)
      Parameters:
      target - a vertex number.
      Returns:
      the shortest cycle in the graph that passes through target, or null if none exists.

    • findOddCycle

      public Cycle findOddCycle()
      Returns:
      the first odd cycle found, or null if the graph contains no odd cycles.

    • findEvenCycle

      public Cycle findEvenCycle()
      Returns:
      the first even cycle found, or null if the graph contains no even cycles.

    • findLongCycle

      public Cycle findLongCycle()
      An heuristic for finding a long cycle. There is no guarantee that the cycle returned is the longest cycle in the graph.
      Returns:
      a cycle that is supposed to be long.