Class: GRATR::Graph::Search::LexicographicQueue

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

Overview

An inner class used for greater efficiency in lexicograph_bfs

Original desgn 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 (array)



139
140
141
142
143
144
145
146
 
# File 'lib/gratr/search.rb', line 139

def initialize(values)
  @node = Struct.new(:back, :forward, :data)
  @node.class_eval { def hash() @hash; end; @@cnt=0 }
  @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 lexical value of given values (array)



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

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 ⇒ Object

Pop an entry with maximum lexical value from queue



149
150
151
152
153
154
 
# File 'lib/gratr/search.rb', line 149

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