Package ghidra.graph

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:

1. 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)
2. post-dominance: A node 'b' is said to post-dominate node 'a' if all paths from 'a' to END contain 'b'
3. immediate dominator: the closest dominator of a node
4. dominance tree: A dominator tree is a tree where each node's children are those nodes it *immediately* dominates (a idom b)
5. dominance frontier: the immediate successors of the nodes dominated by 'a'; it is the set of nodes where d's dominance stops.
6. 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.
7. graph density:
```                        E
Density =  --------
V(V-1)
```
• Method Summary

All 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>>void` ```findPaths​(GDirectedGraph<V,​E> g, V start, V end, Accumulator<java.util.List<V>> accumulator, TaskMonitor monitor)```
Finds all paths from start to end in the given graph.
`static <V,​E extends GEdge<V>>void` ```findPaths​(GDirectedGraph<V,​E> g, V start, V end, Accumulator<java.util.List<V>> accumulator, TimeoutTaskMonitor monitor)```
Finds all paths from start to end 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>>void` ```printGraph​(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.
• Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• 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 graph
`vertices` - 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 graph
`vertices` - 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 graph
`v` - the vertex for which to get edges
`topDown` - 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 graph
`vertices` - the vertices for which to get edges
`topDown` - 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 graph
`vertices` - 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,
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 graph
`monitor` - 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,
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 graph
`from` - the vertex for which to find dominated vertices
`monitor` - 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,
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 graph
`from` - the vertex for which to get post-dominated vertices
`monitor` - 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,
throws CancelledException```
Finds all the circuits, or cycles, in the given graph.
Parameters:
`g` - the graph
`monitor` - 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,
throws CancelledException```
Finds all the circuits, or cycles, in the given graph.
Parameters:
`g` - the graph
`uniqueCircuits` - true signals to return only unique circuits, where no two circuits will contain the same vertex
`monitor` - 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,
throws CancelledException,
TimeoutException```
Finds all the circuits, or cycles, in the given graph. This version of findCircuits() takes a `TimeoutTaskMonitor`, 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 graph
`uniqueCircuits` - true signals to return only unique circuits, where no two circuits will contain the same vertex
`monitor` - the timeout task monitor
Returns:
the circuits
Throws:
`CancelledException` - if the monitor is cancelled
`TimeoutException` - 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,
throws CancelledException```
Finds all paths from start to end 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 graph
`start` - the start vertex
`end` - the end vertex
`accumulator` - the accumulator into which results will be placed
`monitor` - 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,
throws CancelledException,
TimeoutException```
Finds all paths from start to end in the given graph. This version of findPaths() takes a `TimeoutTaskMonitor`, 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 graph
`start` - the start vertex
`end` - the end vertex
`accumulator` - the accumulator into which results will be placed
`monitor` - the timeout task monitor
Throws:
`CancelledException` - if the operation is cancelled
`TimeoutException` - 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 graph
`navigator` - 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 graph
`navigator` - 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 graph
`vertices` - 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 print
`ps` - the output stream