Package ghidra.graph

Class GraphAlgorithms

java.lang.Object

ghidra.graph.GraphAlgorithms

public class GraphAlgorithms
extends 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

Modifier and Type	Method	Description
static <V, E extends GEdge<V>> GDirectedGraph<V,E>	createSubGraph(GDirectedGraph<V,E> g, 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>> List<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>> List<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>> List<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>> 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<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<List<V>> accumulator, TimeoutTaskMonitor monitor)	Finds all paths from start to end in the given graph.
static <V, E extends GEdge<V>> 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>> Set<V>	getAncestors(GDirectedGraph<V,E> g, Collection<V> vertices)	Returns all ancestors for the given vertices in the given graph.
static <V, E extends GEdge<V>> Map<V,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>> Set<V>	getDescendants(GDirectedGraph<V,E> g, Collection<V> vertices)	Returns all descendants for the given vertices in the given graph.
static <V, E extends GEdge<V>> Set<E>	getEdgesFrom(GDirectedGraph<V,E> g, 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>> 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>> Set<V>	getEntryPoints(GDirectedGraph<V,E> g)	Returns all entry points in the given graph.
static <V, E extends GEdge<V>> 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>> 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>> Set<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>> 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>> 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, PrintStream ps)	A method to debug the given graph by printing it.
static <V, E extends GEdge<V>> Set<E>	retainEdges(GDirectedGraph<V,E> graph, 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>> List<V>	topologicalSort(GDirectedGraph<V,E> g, V root, Comparator<E> edgeComparator)	Returns a list of list of vertices sorted topologically such that for every edge V1 -> V2, the V1 vertex will appear in the resulting list before the V2 vertex.
static <V, E extends GEdge<V>> GDirectedGraph<V,E>	toTree(GDirectedGraph<V,E> g, V root, Comparator<E> edgeComparator)	Converts a general directed graph into a tree graph with the given vertex as the root.
static <V, E extends GEdge<V>> Set<V>	toVertices(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 Details

getSources

public static <V,
E extends GEdge<V>> 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>> 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>> Set<V> getDescendants(GDirectedGraph<V,E> g,
 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>> Set<V> getAncestors(GDirectedGraph<V,E> g,
 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>> 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>> Set<E> getEdgesFrom(GDirectedGraph<V,E> g,
 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,
 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>> Set<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>> 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 graph

monitor - the task monitor

Returns:

the tree

Throws:

CancelledException - if the monitor is cancelled

findDominance

public static <V,
E extends GEdge<V>> 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 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>> 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 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>> List<List<V>> findCircuits(GDirectedGraph<V,E> g,
 TaskMonitor monitor)
                                                          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>> List<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 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>> List<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 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<List<V>> accumulator,
 TaskMonitor monitor)
                                              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<List<V>> accumulator,
 TimeoutTaskMonitor monitor)
                                              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>> 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>> 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>>
Map<V,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>> Set<E> retainEdges(GDirectedGraph<V,E> graph,
 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>> Set<V> toVertices(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,
 PrintStream ps)

A method to debug the given graph by printing it.

Parameters:

g - the graph to print

ps - the output stream

topologicalSort

public static <V,
E extends GEdge<V>> List<V> topologicalSort(GDirectedGraph<V,E> g,
 V root,
 Comparator<E> edgeComparator)

Returns a list of list of vertices sorted topologically such that for every edge V1 -> V2, the V1 vertex will appear in the resulting list before the V2 vertex. Normally, this is only defined for acyclic graphs. For purposes of this implementation, a root vertex is given as a start point and any edge encountered by following edges from the root that results in a "back" edge (i.e any edge that points to a previously visited vertex) is ignored, effectively making the graph acyclic (somewhat arbitrarily depending the order in which vertexes are visited which is determined by the given edge comparator). Also, note that any vertex in the graph that is not reachable from the given root will not appear in the resulting list of sorted vertices.

Type Parameters:

V - the vertex type

E - the edge type

Parameters:

g - the graph

root - the start node for traversing the graph (will always be the first node in the resulting list)

edgeComparator - provides an ordering for traversing the graph which can impact which edges are ignored as "back" edges and ultimately affect the final ordering

Returns:

a list of vertices reachable from the given root vertex, sorted topologically

toTree

public static <V,
E extends GEdge<V>>
GDirectedGraph<V,E> toTree(GDirectedGraph<V,E> g,
 V root,
 Comparator<E> edgeComparator)

Converts a general directed graph into a tree graph with the given vertex as the root. It does this by first doing a topological sort (which ignores back edges) and greedily accepting the first incoming edge based on the sorted vertex order.

Type Parameters:

V - the vertex type

E - the edge type

Parameters:

g - the graph to be converted into a tree

root - the vertex to be used as the root

edgeComparator - provides a priority ordering of edges with higher priority edges getting first shot at claiming children for its sub-tree.

Returns:

a graph with edges removed such that the graph is a tree.