Package ghidra.graph

Class 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 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,
                                                                                              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>> 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 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,
                                                                              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>> 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 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,
                                                                                          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>> 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 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,
                                                          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<java.util.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>> 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