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 java.lang.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).
java.util.Set<V>	getDominated(V a)	Returns all nodes dominated by the given vertex.
java.util.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 Detail

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

java.lang.IllegalArgumentException - if there are no source vertices in the graph

Method Detail

getDominated

public java.util.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 java.util.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:

java.lang.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:

java.lang.IllegalArgumentException - if there is not at least one sink node in the graph