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
        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
        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)
        the immediate dominator of x in the flow graph
      • isDomminatedBy

        public boolean isDomminatedBy​(int x,
                                      int y)
        BEWARE requires preprocessDominanceRequests()
        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
        the dominator of the flow graph