Class: Lrama::Digraph

Inherits:
Object
  • Object
show all
Defined in:
lib/lrama/digraph.rb

Overview

Digraph Algorithm of dl.acm.org/doi/pdf/10.1145/69622.357187 (P. 625)

Digraph is an algorithm for graph data structure. The algorithm efficiently traverses SCC (Strongly Connected Component) of graph and merges nodes attributes within the same SCC.

compute_read_sets and compute_follow_sets have the same structure. Graph of gotos and attributes of gotos are given then compute propagated attributes for each node.

In the case of compute_read_sets:

  • Set of gotos is nodes of graph

  • reads_relation is edges of graph

  • direct_read_sets is nodes attributes

In the case of compute_follow_sets:

  • Set of gotos is nodes of graph

  • includes_relation is edges of graph

  • read_sets is nodes attributes

Instance Method Summary collapse

Constructor Details

#initialize(sets, relation, base_function) ⇒ Digraph 



49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/lrama/digraph.rb', line 49

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

Instance Method Details

#compute ⇒ Object 



71
72
73
74
75
76
77
78
 
# File 'lib/lrama/digraph.rb', line 71

def compute
  @sets.each do |x|
    next if @h[x] != 0
    traverse(x)
  end

  return @result
end