Class Acyclic


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

      • THRESHOLD_FOR_NONRECURSIVE_DFS

        public static final int THRESHOLD_FOR_NONRECURSIVE_DFS
        See Also:
        Constant Field Values
    • Method Detail

      • 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.