Class Acyclic

java.lang.Object
com.ibm.wala.util.graph.Acyclic

public class Acyclic extends Object
Utilities for dealing with acyclic subgraphs
  • Field Details

    • THRESHOLD_FOR_NONRECURSIVE_DFS

      public static final int THRESHOLD_FOR_NONRECURSIVE_DFS
      See Also:
  • Method Details

    • isAcyclic

      public static <T> boolean isAcyclic(NumberedGraph<T> G, T root)
      This is slow. Fix it.
    • computeBackEdges

      public static <T> IBinaryNaturalRelation computeBackEdges(NumberedGraph<T> G, T root)
      Compute a relation R s.t. (i,j) \in R iff (i,j) is a backedge according to a DFS of a numbered graph starting from some root.

      Not efficient. Recursive and uses hash sets.

    • hasIncomingBackEdges

      public static <T> boolean hasIncomingBackEdges(Path p, NumberedGraph<T> G, T root)
    • computeAcyclicPaths

      public static <T> Collection<Path> computeAcyclicPaths(NumberedGraph<T> G, T root, T src, T sink, int max)
      Compute a set of acyclic paths through a graph G from a node src to a node sink.

      This is not terribly efficient.

      Parameters:
      max - the max number of paths to return.