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