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

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