Package ghidra.graph.algo

Class ChkDominanceAlgorithm<V,E extends GEdge<V>>

java.lang.Object
ghidra.graph.algo.ChkDominanceAlgorithm<V,E>
Type Parameters:
V - the vertex type
E - the edge type
Direct Known Subclasses:
ChkPostDominanceAlgorithm
public class ChkDominanceAlgorithm<V,E extends GEdge<V>> extends Object
This algorithm is an implementation of the Cooper, Harvey, Kennedy algorithm.

The algorithm processes the graph in reverse post-order. The runtime of this algorithm is approximately O(V+E*D) per iteration of the loop, where D is the size of the largest dominator set. The number of iterations is bound at d(G) + 3, where d(G) is the "loop connectedness" of the graph.

  • Constructor Details

  • Method Details

    • getDominated

      public Set<V> getDominated(V a)
      Returns all nodes dominated by the given vertex. A node 'a' dominates node 'b' if all paths from start to 'b' contain 'a'.
      Parameters:
      a - the vertex
      Returns:
      the dominated vertices

    • getDominators

      public Set<V> getDominators(V a)
      Returns all nodes that dominate the given vertex. A node 'a' dominates node 'b' if all paths from start to 'b' contain 'a'.
      Parameters:
      a - the vertex
      Returns:
      the dominating vertices

    • getDominanceTree

      public GDirectedGraph<V,GEdge<V>> getDominanceTree()
      Returns the dominance tree for the given graph, which is tree where each node's children are those nodes it *immediately* dominates (a idom b).
      Returns:
      the dominance tree

    • clear

      public void clear()
      Releases cached values used by internal data structures

    • unifySources

      protected static <V, E extends GEdge<V>> V unifySources(MutableGDirectedGraphWrapper<V,E> graph, GraphNavigator<V,E> graphNavigator)
      Converts multiple source/root nodes in a graph into a single source of which those become children.
      Parameters:
      graph - the graph
      graphNavigator - the navigator to determine graph direction
      Returns:
      the new single source
      Throws:
      IllegalArgumentException - if there is not at least one source node in the graph

    • unifySinks

      protected static <V, E extends GEdge<V>> V unifySinks(MutableGDirectedGraphWrapper<V,E> graph, GraphNavigator<V,E> graphNavigator)
      Converts multiple sink/exit nodes in a graph into a single sink of which those become parents.
      Parameters:
      graph - the graph
      graphNavigator - the navigator to determine graph direction
      Returns:
      the new single sink
      Throws:
      IllegalArgumentException - if there is not at least one sink node in the graph