Class GraphAlgorithms
- java.lang.Object
-
- ghidra.graph.GraphAlgorithms
-
public class GraphAlgorithms extends java.lang.Object
A set of convenience methods for performing graph algorithms on a graph.Some definitions:
- dominance: a node 'a' dominates node 'b' if all paths from start to 'b' contain 'a'; a node always dominates itself (except in 'strict dominance', which is all dominators except for itself)
- post-dominance: A node 'b' is said to post-dominate node 'a' if all paths from 'a' to END contain 'b'
- immediate dominator: the closest dominator of a node
- dominance tree: A dominator tree is a tree where each node's children are those nodes it *immediately* dominates (a idom b)
- dominance frontier: the immediate successors of the nodes dominated by 'a'; it is the set of nodes where d's dominance stops.
- strongly connected components: a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected.
-
graph density:
E Density = -------- V(V-1)
-
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <V,E extends GEdge<V>>
GDirectedGraph<V,E>createSubGraph(GDirectedGraph<V,E> g, java.util.Collection<V> vertices)
Creates a subgraph of the given graph for each edge of the given graph that is contained in the list of vertices.static <V,E extends GEdge<V>>
java.util.List<java.util.List<V>>findCircuits(GDirectedGraph<V,E> g, boolean uniqueCircuits, TaskMonitor monitor)
Finds all the circuits, or cycles, in the given graph.static <V,E extends GEdge<V>>
java.util.List<java.util.List<V>>findCircuits(GDirectedGraph<V,E> g, boolean uniqueCircuits, TimeoutTaskMonitor monitor)
Finds all the circuits, or cycles, in the given graph.static <V,E extends GEdge<V>>
java.util.List<java.util.List<V>>findCircuits(GDirectedGraph<V,E> g, TaskMonitor monitor)
Finds all the circuits, or cycles, in the given graph.static <V,E extends GEdge<V>>
java.util.Set<V>findDominance(GDirectedGraph<V,E> g, V from, TaskMonitor monitor)
Returns a set of all vertices that are dominated by the given vertex.static <V,E extends GEdge<V>>
GDirectedGraph<V,GEdge<V>>findDominanceTree(GDirectedGraph<V,E> g, TaskMonitor monitor)
Returns the dominance tree of the given graph.static <V,E extends GEdge<V>>
voidfindPaths(GDirectedGraph<V,E> g, V start, V end, Accumulator<java.util.List<V>> accumulator, TaskMonitor monitor)
Finds all paths fromstart
toend
in the given graph.static <V,E extends GEdge<V>>
voidfindPaths(GDirectedGraph<V,E> g, V start, V end, Accumulator<java.util.List<V>> accumulator, TimeoutTaskMonitor monitor)
Finds all paths fromstart
toend
in the given graph.static <V,E extends GEdge<V>>
java.util.Set<V>findPostDominance(GDirectedGraph<V,E> g, V from, TaskMonitor monitor)
Returns a set of all vertices that are post-dominated by the given vertex.static <V,E extends GEdge<V>>
java.util.Set<V>getAncestors(GDirectedGraph<V,E> g, java.util.Collection<V> vertices)
Returns all ancestors for the given vertices in the given graph.static <V,E extends GEdge<V>>
java.util.Map<V,java.lang.Integer>getComplexityDepth(GDirectedGraph<V,E> g)
Calculates 'complexity depth', which is, for each vertex, the deepest/longest path from that vertex for a depth-first traversal.static <V,E extends GEdge<V>>
java.util.Set<V>getDescendants(GDirectedGraph<V,E> g, java.util.Collection<V> vertices)
Returns all descendants for the given vertices in the given graph.static <V,E extends GEdge<V>>
java.util.Set<E>getEdgesFrom(GDirectedGraph<V,E> g, java.util.Collection<V> vertices, boolean topDown)
Returns a set of all edges that are reachable from the given collection of vertices.static <V,E extends GEdge<V>>
java.util.Set<E>getEdgesFrom(GDirectedGraph<V,E> g, V v, boolean topDown)
Returns a set of all edges that are reachable from the given vertex.static <V,E extends GEdge<V>>
java.util.Set<V>getEntryPoints(GDirectedGraph<V,E> g)
Returns all entry points in the given graph.static <V,E extends GEdge<V>>
java.util.Set<V>getSinks(GDirectedGraph<V,E> g)
Returns all sink vertices (those with no outgoing edges) in the graph.static <V,E extends GEdge<V>>
java.util.Set<V>getSources(GDirectedGraph<V,E> g)
Returns all source vertices (those with no incoming edges) in the graph.static <V,E extends GEdge<V>>
java.util.Set<java.util.Set<V>>getStronglyConnectedComponents(GDirectedGraph<V,E> g)
Returns a list where each set therein is a strongly connected component of the given graph.static <V,E extends GEdge<V>>
java.util.List<V>getVerticesInPostOrder(GDirectedGraph<V,E> g, GraphNavigator<V,E> navigator)
Returns the vertices of the graph in post-order.static <V,E extends GEdge<V>>
java.util.List<V>getVerticesInPreOrder(GDirectedGraph<V,E> g, GraphNavigator<V,E> navigator)
Returns the vertices of the graph in pre-order.static <V,E extends GEdge<V>>
voidprintGraph(GDirectedGraph<V,E> g, java.io.PrintStream ps)
A method to debug the given graph by printing it.static <V,E extends GEdge<V>>
java.util.Set<E>retainEdges(GDirectedGraph<V,E> graph, java.util.Set<V> vertices)
Retain all edges in the graph where each edge's endpoints are in the given set of vertices.static <V,E extends GEdge<V>>
java.util.Set<V>toVertices(java.util.Collection<E> edges)
Returns the set of vertices contained within the given edges.
-
-
-
Method Detail
-
getSources
public static <V,E extends GEdge<V>> java.util.Set<V> getSources(GDirectedGraph<V,E> g)
Returns all source vertices (those with no incoming edges) in the graph.- Parameters:
g
- the graph- Returns:
- source vertices
-
getSinks
public static <V,E extends GEdge<V>> java.util.Set<V> getSinks(GDirectedGraph<V,E> g)
Returns all sink vertices (those with no outgoing edges) in the graph.- Parameters:
g
- the graph- Returns:
- sink vertices
-
getDescendants
public static <V,E extends GEdge<V>> java.util.Set<V> getDescendants(GDirectedGraph<V,E> g, java.util.Collection<V> vertices)
Returns all descendants for the given vertices in the given graph. Descendants for a given vertex are all nodes at the outgoing side of an edge, as well as their outgoing vertices, etc.- Parameters:
g
- the graphvertices
- the vertices for which to find descendants- Returns:
- the descendants
-
getAncestors
public static <V,E extends GEdge<V>> java.util.Set<V> getAncestors(GDirectedGraph<V,E> g, java.util.Collection<V> vertices)
Returns all ancestors for the given vertices in the given graph. Ancestors for a given vertex are all nodes at the incoming side of an edge, as well as their incoming vertices, etc.- Parameters:
g
- the graphvertices
- the vertices for which to find descendants- Returns:
- the ancestors
-
getEdgesFrom
public static <V,E extends GEdge<V>> java.util.Set<E> getEdgesFrom(GDirectedGraph<V,E> g, V v, boolean topDown)
Returns a set of all edges that are reachable from the given vertex.- Parameters:
g
- the graphv
- the vertex for which to get edgestopDown
- true for outgoing edges; false for incoming edges- Returns:
- the set of edges
-
getEdgesFrom
public static <V,E extends GEdge<V>> java.util.Set<E> getEdgesFrom(GDirectedGraph<V,E> g, java.util.Collection<V> vertices, boolean topDown)
Returns a set of all edges that are reachable from the given collection of vertices.- Parameters:
g
- the graphvertices
- the vertices for which to get edgestopDown
- true for outgoing edges; false for incoming edges- Returns:
- the set of edges
-
createSubGraph
public static <V,E extends GEdge<V>> GDirectedGraph<V,E> createSubGraph(GDirectedGraph<V,E> g, java.util.Collection<V> vertices)
Creates a subgraph of the given graph for each edge of the given graph that is contained in the list of vertices.- Parameters:
g
- the existing graphvertices
- the vertices to be in the new graph- Returns:
- the new subgraph
-
getStronglyConnectedComponents
public static <V,E extends GEdge<V>> java.util.Set<java.util.Set<V>> getStronglyConnectedComponents(GDirectedGraph<V,E> g)
Returns a list where each set therein is a strongly connected component of the given graph. Each strongly connected component is that in which each vertex is reachable from any other vertex in that set.This method can be used to determine reachability of a set of vertices.
This can also be useful for cycle detection, as a multi-vertex strong component is by definition a cycle. This method differs from
findCircuits(GDirectedGraph, boolean, TaskMonitor)
in that the latter will return cycles within the strong components, or sub-cycles.- Parameters:
g
- the graph- Returns:
- the list of strongly connected components
-
getEntryPoints
public static <V,E extends GEdge<V>> java.util.Set<V> getEntryPoints(GDirectedGraph<V,E> g)
Returns all entry points in the given graph. This includes sources, vertices which have no incoming edges, as well as strongly connected sub-graphs. The latter being a group vertices where each vertex is reachable from every other vertex. In the case of strongly connected components, we pick one of them arbitrarily to be the entry point.- Parameters:
g
- the graph- Returns:
- the entry points into the graph
-
findDominanceTree
public static <V,E extends GEdge<V>> GDirectedGraph<V,GEdge<V>> findDominanceTree(GDirectedGraph<V,E> g, TaskMonitor monitor) throws CancelledException
Returns the dominance tree of the given graph. A dominator tree of the vertices where each node's children are those nodes it *immediately* dominates (a idom b)- Parameters:
g
- the graphmonitor
- the task monitor- Returns:
- the tree
- Throws:
CancelledException
- if the monitor is cancelled
-
findDominance
public static <V,E extends GEdge<V>> java.util.Set<V> findDominance(GDirectedGraph<V,E> g, V from, TaskMonitor monitor) throws CancelledException
Returns a set of all vertices that are dominated by the given vertex. A node 'a' dominates node 'b' if all paths from start to 'b' contain 'a'; a node always dominates itself (except in 'strict dominance', which is all dominators except for itself)- Parameters:
g
- the graphfrom
- the vertex for which to find dominated verticesmonitor
- the monitor- Returns:
- the set of dominated vertices
- Throws:
CancelledException
- if the monitor is cancelled
-
findPostDominance
public static <V,E extends GEdge<V>> java.util.Set<V> findPostDominance(GDirectedGraph<V,E> g, V from, TaskMonitor monitor) throws CancelledException
Returns a set of all vertices that are post-dominated by the given vertex. A node 'b' is said to post-dominate node 'a' if all paths from 'a' to END contain 'b'.- Parameters:
g
- the graphfrom
- the vertex for which to get post-dominated verticesmonitor
- the monitor- Returns:
- the post-dominated vertices
- Throws:
CancelledException
- if the monitor is cancelled
-
findCircuits
public static <V,E extends GEdge<V>> java.util.List<java.util.List<V>> findCircuits(GDirectedGraph<V,E> g, TaskMonitor monitor) throws CancelledException
Finds all the circuits, or cycles, in the given graph.- Parameters:
g
- the graphmonitor
- the task monitor- Returns:
- the circuits
- Throws:
CancelledException
- if the monitor is cancelled
-
findCircuits
public static <V,E extends GEdge<V>> java.util.List<java.util.List<V>> findCircuits(GDirectedGraph<V,E> g, boolean uniqueCircuits, TaskMonitor monitor) throws CancelledException
Finds all the circuits, or cycles, in the given graph.- Parameters:
g
- the graphuniqueCircuits
- true signals to return only unique circuits, where no two circuits will contain the same vertexmonitor
- the task monitor- Returns:
- the circuits
- Throws:
CancelledException
- if the monitor is cancelled
-
findCircuits
public static <V,E extends GEdge<V>> java.util.List<java.util.List<V>> findCircuits(GDirectedGraph<V,E> g, boolean uniqueCircuits, TimeoutTaskMonitor monitor) throws CancelledException, TimeoutException
Finds all the circuits, or cycles, in the given graph. This version offindCircuits()
takes aTimeoutTaskMonitor
, which allows for the client to control the duration of work. This is useful for finding paths on very large, dense graphs.- Parameters:
g
- the graphuniqueCircuits
- true signals to return only unique circuits, where no two circuits will contain the same vertexmonitor
- the timeout task monitor- Returns:
- the circuits
- Throws:
CancelledException
- if the monitor is cancelledTimeoutException
- if the algorithm times-out, as defined by the monitor
-
findPaths
public static <V,E extends GEdge<V>> void findPaths(GDirectedGraph<V,E> g, V start, V end, Accumulator<java.util.List<V>> accumulator, TaskMonitor monitor) throws CancelledException
Finds all paths fromstart
toend
in the given graph.Warning: for large, dense graphs (those with many interconnected vertices) this algorithm could run indeterminately, possibly causing the JVM to run out of memory.
You are encouraged to call this method with a monitor that will limit the work to be done, such as the
TimeoutTaskMonitor
.- Parameters:
g
- the graphstart
- the start vertexend
- the end vertexaccumulator
- the accumulator into which results will be placedmonitor
- the task monitor- Throws:
CancelledException
- if the operation is cancelled
-
findPaths
public static <V,E extends GEdge<V>> void findPaths(GDirectedGraph<V,E> g, V start, V end, Accumulator<java.util.List<V>> accumulator, TimeoutTaskMonitor monitor) throws CancelledException, TimeoutException
Finds all paths fromstart
toend
in the given graph. This version offindPaths()
takes aTimeoutTaskMonitor
, which allows for the client to control the duration of work. This is useful for finding paths on very large, dense graphs.Warning: for large, dense graphs (those with many interconnected vertices) this algorithm could run indeterminately, possibly causing the JVM to run out of memory.
- Parameters:
g
- the graphstart
- the start vertexend
- the end vertexaccumulator
- the accumulator into which results will be placedmonitor
- the timeout task monitor- Throws:
CancelledException
- if the operation is cancelledTimeoutException
- if the operation passes the timeout period
-
getVerticesInPostOrder
public static <V,E extends GEdge<V>> java.util.List<V> getVerticesInPostOrder(GDirectedGraph<V,E> g, GraphNavigator<V,E> navigator)
Returns the vertices of the graph in post-order. Pre-order is the order the vertices are last visited when performing a depth-first traversal.- Parameters:
g
- the graphnavigator
- the knower of the direction the graph should be traversed- Returns:
- the vertices
-
getVerticesInPreOrder
public static <V,E extends GEdge<V>> java.util.List<V> getVerticesInPreOrder(GDirectedGraph<V,E> g, GraphNavigator<V,E> navigator)
Returns the vertices of the graph in pre-order. Pre-order is the order the vertices are encountered when performing a depth-first traversal.- Parameters:
g
- the graphnavigator
- the knower of the direction the graph should be traversed- Returns:
- the vertices
-
getComplexityDepth
public static <V,E extends GEdge<V>> java.util.Map<V,java.lang.Integer> getComplexityDepth(GDirectedGraph<V,E> g)
Calculates 'complexity depth', which is, for each vertex, the deepest/longest path from that vertex for a depth-first traversal. So, for a vertex with a single successor that has no children, the depth would be 1.- Parameters:
g
- the graph- Returns:
- the map of each vertex to its complexity depth
-
retainEdges
public static <V,E extends GEdge<V>> java.util.Set<E> retainEdges(GDirectedGraph<V,E> graph, java.util.Set<V> vertices)
Retain all edges in the graph where each edge's endpoints are in the given set of vertices.- Parameters:
graph
- the graphvertices
- the vertices of the edges to keep- Returns:
- the set of edges
-
toVertices
public static <V,E extends GEdge<V>> java.util.Set<V> toVertices(java.util.Collection<E> edges)
Returns the set of vertices contained within the given edges.- Parameters:
edges
- the edges- Returns:
- the vertices
-
printGraph
public static <V,E extends GEdge<V>> void printGraph(GDirectedGraph<V,E> g, java.io.PrintStream ps)
A method to debug the given graph by printing it.- Parameters:
g
- the graph to printps
- the output stream
-
-