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[]
ancestor
protected int[]
bucket
protected int[]
dom
protected DirectedGraph
g
protected Iterator<Integer>[]
iterator
protected int
k
protected int[]
label
protected gnu.trove.list.array.TIntArrayList
list
protected int
n
protected int[]
parent
protected ISet[]
preds
protected int
root
protected int[]
semi
protected ISet[]
succs
protected DirectedGraph
T
protected 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 void
compress(int v)
protected abstract int
eval(int v)
boolean
findDominators()
Find immediate dominators of the given graph and preprocess dominance requestsboolean
findPostDominators()
Find immediate postdominators of the given graph and preprocess dominance requests post dominators are dominators of the inverse graphDirectedGraph
getDominatorTree()
Get the dominator tree formed with arcs (x,y) such that x is the immediate dominator of yint
getImmediateDominatorsOf(int x)
protected void
initParams(boolean inverseGraph)
boolean
isDomminatedBy(int x, int y)
BEWARE requires preprocessDominanceRequests()protected abstract void
link(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
-
-