blob: 28f26781b151b7e2e05cee57e24b0c6e2329c8ac (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
module Lrama
# Algorithm Digraph of https://dl.acm.org/doi/pdf/10.1145/69622.357187 (P. 625)
class Digraph
def initialize(sets, relation, base_function)
# X in the paper
@sets = sets
# R in the paper
@relation = relation
# F' in the paper
@base_function = base_function
# S in the paper
@stack = []
# N in the paper
@h = Hash.new(0)
# F in the paper
@result = {}
end
def compute
@sets.each do |x|
next if @h[x] != 0
traverse(x)
end
return @result
end
private
def traverse(x)
@stack.push(x)
d = @stack.count
@h[x] = d
@result[x] = @base_function[x] # F x = F' x
@relation[x] && @relation[x].each do |y|
traverse(y) if @h[y] == 0
@h[x] = [@h[x], @h[y]].min
@result[x] |= @result[y] # F x = F x + F y
end
if @h[x] == d
while true do
z = @stack.pop
@h[z] = Float::INFINITY
@result[z] = @result[x] # F (Top of S) = F x
break if z == x
end
end
end
end
end
|
