Package com.ibm.wala.util.graph
Class Acyclic
- java.lang.Object
-
- com.ibm.wala.util.graph.Acyclic
-
public class Acyclic extends java.lang.Object
Utilities for dealing with acyclic subgraphs
-
-
Field Summary
Fields Modifier and Type Field Description static int
THRESHOLD_FOR_NONRECURSIVE_DFS
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <T> java.util.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.static <T> IBinaryNaturalRelation
computeBackEdges(NumberedGraph<T> G, T root)
Compute a relation R s.t.static <T> boolean
hasIncomingBackEdges(Path p, NumberedGraph<T> G, T root)
static <T> boolean
isAcyclic(NumberedGraph<T> G, T root)
This is slow.
-
-
-
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> java.util.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.
-
-