Module: DAG

Defined in:
lib/zipf/dag.rb

Defined Under Namespace

Classes: Edge, Node

Class Method Summary collapse

Class Method Details

.bellman_ford(graph, semiring = RealSemiring.new, source_node) ⇒ Object

Bellman-Ford algorithm



139
140
141
142
143
144
145
146
147
148
149
150
151
152
# File 'lib/zipf/dag.rb', line 139

def DAG::bellman_ford(graph, semiring=RealSemiring.new, source_node)
  DAG::init(graph, semiring, source_node)
  edges = []
  graph.each { |n| edges |= n.outgoing }
  # relax edges
  (graph.size-1).times{ |i|
    edges.each { |e|
      e.head.score = \
        semiring.add.call(e.head.score, \
                          semiring.multiply.call(e.tail.score, e.weight))
    }
  }
  # we do not allow cycles (negative or positive)
end

.bfs(n, target_label) ⇒ Object

breadth-first search

w/o markings as we do not have cycles


62
63
64
65
66
67
68
69
70
# File 'lib/zipf/dag.rb', line 62

def DAG::bfs n, target_label
  queue = [n]
  while !queue.empty?
    m = queue.shift
    return m if m.label==target_label
    m.outgoing.each { |e| queue << e.head }
  end
  return nil
end

.dfs(n, target_label) ⇒ Object

depth-first search

w/o markings as we do not have cycles


50
51
52
53
54
55
56
57
58
# File 'lib/zipf/dag.rb', line 50

def DAG::dfs n, target_label
  return n if n.label==target_label # assumes uniq labels!
  stack = n.outgoing.map { |i| i.head }
  while !stack.empty?
    m = stack.pop
    return DAG::dfs m, target_label
  end
  return nil
end

.dijkstra(graph, semiring = RealSemiring.new, source_node) ⇒ Object

Dijkstra algorithm

for A*-search we would need an optimistic estimate of
future cost at each node


124
125
126
127
128
129
130
131
132
133
134
135
136
# File 'lib/zipf/dag.rb', line 124

def DAG::dijkstra graph, semiring=RealSemiring.new, source_node
  DAG::init(graph, semiring, source_node)
  q = PriorityQueue.new graph
  while !q.empty?
    n = q.pop
    n.outgoing.each { |e|
      e.head.score = \
        semiring.add.call(e.head.score, \
                          semiring.multiply.call(n.score, e.weight))
      q.sort!
    }
  end
end

.floyd(graph, semiring = nil) ⇒ Object

Floyd algorithm



155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
# File 'lib/zipf/dag.rb', line 155

def DAG::floyd(graph, semiring=nil)
  dist_matrix = []
  graph.each_index { |i|
    dist_matrix << []
    graph.each_index { |j|
      val = 1.0/0.0
      val = 0.0 if i==j
      dist_matrix.last << val
    }
  }
  edges = []
  graph.each { |n| edges |= n.outgoing }
  edges.each { |e|
    dist_matrix[graph.index(e.tail)][graph.index(e.head)] = e.weight
  }
  0.upto(graph.size-1) { |k|
    0.upto(graph.size-1) { |i|
      0.upto(graph.size-1) { |j|
        if dist_matrix[i][k] + dist_matrix[k][j] < dist_matrix[i][j]
          dist_matrix  [i][j] = dist_matrix[i][k] + dist_matrix[k][j]
        end
      }
    }
  }
  return dist_matrix
end

.init(graph, semiring, source_node) ⇒ Object

initialize graph scores with semiring One



87
88
89
90
# File 'lib/zipf/dag.rb', line 87

def DAG::init graph, semiring, source_node
  graph.each {|n| n.score=semiring.null}
  source_node.score = semiring.one
end

.read_graph_from_json(fn, semiring = RealSemiring.new) ⇒ Object

returns a list of nodes (graph) and a hash for finding nodes by their label (these need to be unique!)



185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
# File 'lib/zipf/dag.rb', line 185

def DAG::read_graph_from_json fn, semiring=RealSemiring.new
  graph = []
  nodes_by_label = {}
  h = JSON.parse File.new(fn).read
  h['nodes'].each { |i|
    n = DAG::Node.new i['label']
    graph << n
    nodes_by_label[n.label] = n
  }
  h['edges'].each { |i|
    n = nodes_by_label[i['tail']]
    a = n.add_edge(nodes_by_label[i['head']], semiring.convert.call(i['weight'].to_f))
    nodes_by_label[i['head']].incoming << a
  }
  return graph, nodes_by_label
end

.topological_sort(graph) ⇒ Object

topological sort



73
74
75
76
77
78
79
80
81
82
83
84
# File 'lib/zipf/dag.rb', line 73

def DAG::topological_sort graph
  sorted = []
  s = graph.reject { |n| !n.incoming.empty? }
  while !s.empty?
    sorted << s.shift
    sorted.last.outgoing.each { |e|
      e.mark = true
      s << e.head if e.head.incoming.reject{|f| f.mark}.empty?
    }
  end
  return sorted
end

.viterbi(graph, semiring = ViterbiSemiring, source_node) ⇒ Object

viterbi



93
94
95
96
97
98
99
100
101
102
103
104
105
# File 'lib/zipf/dag.rb', line 93

def DAG::viterbi graph, semiring=ViterbiSemiring, source_node
  toposorted = DAG::topological_sort(graph)
  DAG::init(graph, semiring, source_node)
  toposorted.each { |n|
    n.incoming.each { |e|
      # update
      n.score = \
        semiring.add.call(n.score, \
                          semiring.multiply.call(e.tail.score, e.weight)
        )
    }
  }
end

.viterbi_forward(graph, semiring = ViterbiSemiring, source_node) ⇒ Object

forward viterbi



108
109
110
111
112
113
114
115
116
117
118
119
# File 'lib/zipf/dag.rb', line 108

def DAG::viterbi_forward graph, semiring=ViterbiSemiring, source_node
  toposorted = DAG::topological_sort(graph)
  DAG::init(graph, semiring, source_node)
  toposorted.each { |n|
    n.outgoing.each { |e|
      e.head.score = \
        semiring.add.call(e.head.score, \
                          semiring.multiply.call(n.score, e.weight)
        )
    }
  }
end