Class AbstractLengauerTarjanDominatorsFinder
- java.lang.Object
-
- org.chocosolver.util.graphOperations.dominance.AbstractLengauerTarjanDominatorsFinder
-
- Direct Known Subclasses:
AlphaDominatorsFinder,SimpleDominatorsFinder
public abstract class AbstractLengauerTarjanDominatorsFinder extends Object
Class that finds dominators of a given flow graph g(s)
-
-
Field Summary
Fields Modifier and Type Field Description protected int[]ancestorprotected int[]bucketprotected int[]domprotected DirectedGraphgprotected Iterator<Integer>[]iteratorprotected intkprotected int[]labelprotected gnu.trove.list.array.TIntArrayListlistprotected intnprotected int[]parentprotected ISet[]predsprotected introotprotected int[]semiprotected ISet[]succsprotected DirectedGraphTprotected int[]vertex
-
Constructor Summary
Constructors Constructor Description AbstractLengauerTarjanDominatorsFinder(int s, DirectedGraph g)Object that finds dominators of the given flow graph g(s)
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected abstract voidcompress(int v)protected abstract inteval(int v)booleanfindDominators()Find immediate dominators of the given graph and preprocess dominance requestsbooleanfindPostDominators()Find immediate postdominators of the given graph and preprocess dominance requests post dominators are dominators of the inverse graphDirectedGraphgetDominatorTree()Get the dominator tree formed with arcs (x,y) such that x is the immediate dominator of yintgetImmediateDominatorsOf(int x)protected voidinitParams(boolean inverseGraph)booleanisDomminatedBy(int x, int y)BEWARE requires preprocessDominanceRequests()protected abstract voidlink(int v, int w)
-
-
-
Field Detail
-
g
protected DirectedGraph g
-
T
protected DirectedGraph T
-
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
-
-