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.

Parameters:

  • initial (Array) —

    vertices 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.

Parameters:

  • vertices (Array) —

    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

#pop ⇒ vertex

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

Returns:

  • (vertex) 


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