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 typeE
- 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 atd(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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
Releases cached values used by internal data structuresGDirectedGraph<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>>
VunifySinks(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>>
VunifySources(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.
-
-
-
Constructor Detail
-
ChkDominanceAlgorithm
public ChkDominanceAlgorithm(GDirectedGraph<V,E> g, TaskMonitor monitor) throws CancelledException
Constructor.- Parameters:
g
- the graphmonitor
- the monitor- Throws:
CancelledException
- if the algorithm is cancelledjava.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 graphgraphNavigator
- 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 graphgraphNavigator
- 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
-
-