Class AbstractLengauerTarjanDominatorsFinder

    • Field Detail

      • root

        protected int root
      • n

        protected int n
      • k

        protected int k
      • parent

        protected int[] parent
      • vertex

        protected int[] vertex
      • bucket

        protected int[] bucket
      • ancestor

        protected int[] ancestor
      • label

        protected int[] label
      • semi

        protected int[] semi
      • dom

        protected int[] dom
      • succs

        protected ISet[] succs
      • preds

        protected ISet[] preds
      • list

        protected gnu.trove.list.array.TIntArrayList list
    • Constructor Detail

      • AbstractLengauerTarjanDominatorsFinder

        public AbstractLengauerTarjanDominatorsFinder​(int s,
                                                      DirectedGraph g)
        Object that finds dominators of the given flow graph g(s)
    • Method Detail

      • findDominators

        public boolean findDominators()
        Find immediate dominators of the given graph and preprocess dominance requests
        Returns:
        false iff the source cannot reach all nodes (contradiction)
      • findPostDominators

        public boolean findPostDominators()
        Find immediate postdominators of the given graph and preprocess dominance requests post dominators are dominators of the inverse graph
        Returns:
        false iff the source cannot reach all nodes (contradiction)
      • initParams

        protected void initParams​(boolean inverseGraph)
      • link

        protected abstract void link​(int v,
                                     int w)
      • eval

        protected abstract int eval​(int v)
      • compress

        protected abstract void compress​(int v)
      • getImmediateDominatorsOf

        public int getImmediateDominatorsOf​(int x)
        Returns:
        the immediate dominator of x in the flow graph
      • isDomminatedBy

        public boolean isDomminatedBy​(int x,
                                      int y)
        BEWARE requires preprocessDominanceRequests()
        Returns:
        true iff x is dominated by y
      • getDominatorTree

        public DirectedGraph getDominatorTree()
        Get the dominator tree formed with arcs (x,y) such that x is the immediate dominator of y
        Returns:
        the dominator of the flow graph