Module: DAG
- Defined in:
- lib/zipf/dag.rb
Defined Under Namespace
Class Method Summary collapse
-
.bellman_ford(graph, semiring = RealSemiring.new, source_node) ⇒ Object
Bellman-Ford algorithm.
-
.bfs(n, target_label) ⇒ Object
breadth-first search w/o markings as we do not have cycles.
-
.dfs(n, target_label) ⇒ Object
depth-first search w/o markings as we do not have cycles.
-
.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.
-
.floyd(graph, semiring = nil) ⇒ Object
Floyd algorithm.
-
.init(graph, semiring, source_node) ⇒ Object
initialize graph scores with semiring One.
-
.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!).
-
.topological_sort(graph) ⇒ Object
topological sort.
-
.viterbi(graph, semiring = ViterbiSemiring, source_node) ⇒ Object
viterbi.
-
.viterbi_forward(graph, semiring = ViterbiSemiring, source_node) ⇒ Object
forward viterbi.
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 |