Java Reference
In-Depth Information
procedure
intervals
S
chwartz
S
harir
(
G
f
,
DFST
)
foreach
node
∈N
f
do
head
(
node
)
←⊥
for
n
=|N
f
|
downto
2
do
66
h
←
vertex
(
n
)
67
ReachUnder
←{
C
ur
I
nt
(
l
)
|
(
l
,
h
)
∈E
f
and
h
l
}
68
while
∃
y
∈
(
ReachUnder
−{
h
}
)
|
head
(
y
)
=⊥
do
69
head
(
y
)
←
h
70
foreach
X
∈{
C
ur
I
nt
(
x
)
|
x
∈
Preds
(
y
)
}
do
71
if
h
X
then
72
/
Irreducible graph (Exercises 23 and 24)
/
73
ReachUnder
←
ReachUnder
∪{
X
}
foreach
y
|
head
(
y
)
←
root
foreach
node
∈N
f
do
Members
(
node
)
=⊥
do
head
(
y
)
74
←∅
traverse tree
(
DFST
)
order
(Pre R-L)
at node
(
n
)
do
Members
(
head
(
n
))
75
←
Members
(
head
(
n
))
∪{
n
}
end
function
C
ur
I
nt
(
X
)
returns
node
if
head
(
X
)
=⊥
then return
(
X
)
else
return
(C
ur
I
nt
(
head
(
X
)))
end
Figure 14.35: Schwartz-Sharir intervals algorithm.
0
Header
ReachUnder
Node
New
h
set at
y
nodes
1
67
69
70
71
2
{
4
}
4
{
3
,
8
}
2
10
{
4
,
3
,
8
}
3
{
2
}
{
4
,
3
,
8
,
2
}
8
{
2
}
3
8
1
{
2
,
6
,
9
}
2
{
2
,
1
}
{
2
,
6
,
9
,
1
}
6
{
5
,
9
}
4
9
{
2
,
6
,
9
,
1
,
5
}
9
{
2
,
10
}
5
{
2
,
6
,
9
,
1
,
5
,
10
}
5
{
2
}
{
2
,
6
,
9
,
1
,
5
,
10
}
10
{
1
}
6
0
{
0
,
1
,
7
}
7
Figure 14.36: The Schwartz-Sharir intervals of Figure 14.32.
