Class: Plexus::Search::LexicographicQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/plexus/search.rb

Overview

An inner class used for greater efficiency in #lexicograph_bfs.

Original design taken from Golumbic's, *Algorithmic Graph Theory and Perfect Graphs* pg. 87-89.

Instance Method Summary collapse

Constructor Details

#initialize(values) ⇒ LexicographicQueue

Called with the initial values.


156
157
158
159
160
161
162
163
164
165
166
167
168
# File 'lib/plexus/search.rb', line 156

def initialize(values)
  @node = Struct.new(:back, :forward, :data)
  @node.class_eval do
    def hash
      @hash
    end
    @@cnt = 0
  end
  @set  = {}
  @tail = @node.new(nil, nil, Array.new(values))
  @tail.instance_eval { @hash = (@@cnt += 1) }
  values.each { |a| @set[a] = @tail }
end

Instance Method Details

#add_lexeme(values) ⇒ Object

Increase the lexical value of the given values.


184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
# File 'lib/plexus/search.rb', line 184

def add_lexeme(values)
  fix = {}

  values.select { |v| @set[v] }.each do |w|
    sw = @set[w]
    if fix[sw]
      s_prime = sw[:back]
    else
      s_prime = @node.new(sw[:back], sw, [])
      s_prime.instance_eval { @hash = (@@cnt += 1) }
      @tail = s_prime if @tail == sw
      sw[:back][:forward] = s_prime if sw[:back]
      sw[:back]           = s_prime
      fix[sw]             = true
    end

    s_prime[:data] << w
    sw[:data].delete(w)
    @set[w] = s_prime
  end

  fix.keys.select { |n| n[:data].size == 0 }.each do |e|
    e[:forward][:back] = e[:back]    if e[:forward]
    e[:back][:forward] = e[:forward] if e[:back]
  end
end

#popvertex

Pops an entry with the maximum lexical value from the queue.


173
174
175
176
177
178
179
# File 'lib/plexus/search.rb', line 173

def pop
  return nil unless @tail
  value = @tail[:data].pop
  @tail = @tail[:forward] while @tail and @tail[:data].size == 0
  @set.delete(value)
  value
end