Module: HG

Defined in:
lib/zipf/hypergraph.rb

Defined Under Namespace

Classes: Hyperedge, Hypergraph, Node

Class Method Summary collapse

Class Method Details

.all_paths(hypergraph, root, semiring = ViterbiSemiring.new) ⇒ Object 



152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/zipf/hypergraph.rb', line 152

def HG::all_paths hypergraph, root, semiring=ViterbiSemiring.new
  toposorted = topological_sort hypergraph.nodes
  paths = [[]]
  toposorted.each { |n|
    next if n.incoming.empty?
    new_paths = []
    while !paths.empty?
      p = paths.pop
      n.incoming.each { |e|
        new_paths << p+[e]
      }
    end
    paths = new_paths
  }
  return paths
end

.init(nodes, semiring, root) ⇒ Object 



79
80
81
82
 
# File 'lib/zipf/hypergraph.rb', line 79

def HG::init nodes, semiring, root
  nodes.each { |n| n.score=semiring.null }
  root.score = semiring.one
end

.read_hypergraph_from_json(fn, semiring = RealSemiring.new, log_weights = false) ⇒ Object 



119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/zipf/hypergraph.rb', line 119

def HG::read_hypergraph_from_json fn, semiring=RealSemiring.new, log_weights=false
  nodes = []
  edges = []
  nodes_by_label = {}
  nodes_by_index = []
  h = JSON.parse File.new(fn).read
  w = SparseVector.from_h h['weights']
  h['nodes'].each { |i|
    n = Node.new i['label'], i['cat']
    nodes << n
    nodes_by_label[n.label] = n
    nodes_by_index << n
  }
  h['edges'].each { |i|
    e = Hyperedge.new(nodes_by_label[i['head']], \
                      i['tails'].map{|j| nodes_by_label[j]}.to_a, \
                      semiring.convert.call(i['weight'].to_f), \
                      {})
    e.f = SparseVector.from_h i['f']
    if log_weights
      e.weight = Math.exp(w.dot(e.f))
    else
      e.weight = w.dot(e.f)
    end
    e.tails.each { |m|
      m.outgoing << e
    }
    e.head.incoming << e
    edges << e
  }
  return Hypergraph.new(nodes, edges), nodes_by_label, nodes_by_index
end

.topological_sort(nodes) ⇒ Object 



65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/zipf/hypergraph.rb', line 65

def HG::topological_sort nodes
  sorted = []
  s = nodes.reject { |n| !n.incoming.empty? }
  while !s.empty?
    sorted << s.shift
    sorted.last.outgoing.each { |e|
      next if e.marked?
      e.mark += 1
      s << e.head if e.head.incoming.reject{ |f| f.mark==f.arity }.empty?
    }
  end
  return sorted
end

.viterbi(hypergraph, root, semiring = ViterbiSemiring.new) ⇒ Object 



84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/zipf/hypergraph.rb', line 84

def HG::viterbi hypergraph, root, semiring=ViterbiSemiring.new
  toposorted = topological_sort hypergraph.nodes
  init toposorted, semiring, root
  toposorted.each { |n|
    n.incoming.each { |e|
      s = semiring.one
      e.tails.each { |m|
        s = semiring.multiply.call(s, m.score)
      }
      n.score = semiring.add.call(n.score, semiring.multiply.call(s, e.weight))
    }
  }
end

.viterbi_path(hypergraph, root, semiring = ViterbiSemiring.new) ⇒ Object 



98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/zipf/hypergraph.rb', line 98

def HG::viterbi_path hypergraph, root, semiring=ViterbiSemiring.new
  toposorted = topological_sort hypergraph.nodes
  init toposorted, semiring, root
  best_path = []
  toposorted.each { |n|
    best_edge = nil
    n.incoming.each { |e|
      s = semiring.one
      e.tails.each { |m|
        s = semiring.multiply.call(s, m.score)
      }
      if n.score < semiring.multiply.call(s, e.weight) # ViterbiSemiring add
        best_edge = e
      end
      n.score = semiring.add.call(n.score, semiring.multiply.call(s, e.weight))
    }
    best_path << best_edge
  }
  return best_path, toposorted.last.score
end