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 Summary

  Constructors
  Constructor
  Description
  `ChkDominanceAlgorithm(GDirectedGraph<V,E> g, TaskMonitor monitor)`
  Constructor.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `clear()`
  Releases cached values used by internal data structures
  `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).
  `Set<V>`
  `getDominated(V a)`
  Returns all nodes dominated by the given vertex.
  `Set<V>`
  `getDominators(V a)`
  Returns all nodes that dominate the given vertex.
  `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.
  `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.

  ### Methods inherited from class java.lang.Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Constructor Details

  - ### ChkDominanceAlgorithm

    public ChkDominanceAlgorithm(GDirectedGraph<V,E> g, TaskMonitor monitor) throws CancelledException
    Constructor.
    Parameters:
      `g` - the graph
      `monitor` - the monitor
    Throws:
      `CancelledException` - if the algorithm is cancelled
      `IllegalArgumentException` - if there are no source vertices in the graph

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