Class: MTree::Tree

Inherits:
Object
  • Object
show all
Defined in:
ext/lib/CompLearnLib/Tree.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Tree

Returns a new instance of Tree.



34
35
36
37
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 34

def initialize()
  @edges = [ ]
  @spm = nil
end

Instance Attribute Details

#edges ⇒ Object (readonly)

consists of 2n - 2 nodes: n species followed by n-2 kernel nodes



33
34
35
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 33

def edges
  @edges
end

Class Method Details

.randomTree(species) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 87

def Tree.randomTree(species)
  raise "Not enough species" unless (species >= 3)
  result = Tree.new
  k = species - 2
  nodes = species+k
  (k-1).times { |i|
    n = nil
    begin
      n = RunEnv.zrand(i+1) + species
    end until result.getNeighborCount(n) <= 2
    result.connect(i+species+1,n)
  }
  species.times { |i|
    n = nil
    begin
      n = RunEnv.zrand(k) + species
    end until result.getNeighborCount(n) <= 2
    result.connect(i,n)
  }
  result
end

Instance Method Details

#<=>(other) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 43

def <=>(other)
  res = @edges.size - other.edges.size
  return res unless res == 0
  @edges.each_index { |i|
    res = @edges[i].size - other.edges[i].size
    return res unless res == 0
    @edges[i].each_index { |j|
      res = @edges[i][j] - other.edges[i][j]
      return res unless res == 0
    }
  }
  0
end

#clone ⇒ Object 



38
39
40
41
42
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 38

def clone()
  t = Tree.new
  t.copyEdges(self)
  t
end

#connect(a, b) ⇒ Object 



178
179
180
181
182
183
184
185
186
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 178

def connect(a,b)
  @edges[a] = [ ] unless @edges[a]
  @edges[b] = [ ] unless @edges[b]
  @edges[a] << b
  @edges[b] << a
  @edges[a].sort!
  @edges[b].sort!
  @spm = nil
end

#connected?(a, b) ⇒ Boolean

Returns:

  • (Boolean) 


168
169
170
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 168

def connected?(a,b)
  @edges[a] && @edges[a].include?(b)
end

#copyEdges(t) ⇒ Object 



56
57
58
59
60
61
62
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 56

def copyEdges(t)
  @edges = [ ]
  t.edges.each_index { |i|
    @edges[i] = t.edges[i].clone
  }
  @spm = nil
end

#disconnect(a, b) ⇒ Object 



171
172
173
174
175
176
177
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 171

def disconnect(a,b)
  @edges[a].delete(b)
  @edges[b].delete(a)
  @edges[a] = nil if @edges[a].size == 0
  @edges[b] = nil if @edges[b].size == 0
  @spm = nil
end

#findPath(a, b) ⇒ Object 



131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 131

def findPath(a,b)
  calculateSPM() unless @spm
  path = [ ]
  curspm = @spm[b]
  cur = a
  while (cur != b)
    path << cur
    cur = curspm[cur]
  end
  path << cur
  path
end

#getKernelCount ⇒ Object 



149
150
151
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 149

def getKernelCount()
  getSpeciesCount() - 2
end

#getNeighborCount(node) ⇒ Object 



164
165
166
167
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 164

def getNeighborCount(node)
  return 0 unless @edges[node]
  @edges[node].size
end

#getNeighbors(node) ⇒ Object 



158
159
160
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 158

def getNeighbors(node)
  @edges[node]
end

#getNodeCount ⇒ Object 



143
144
145
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 143

def getNodeCount()
  @edges.size
end

#getSpeciesCount ⇒ Object 



146
147
148
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 146

def getSpeciesCount()
  (getNodeCount()+2) / 2
end

#isKernel?(node) ⇒ Boolean

Returns:

  • (Boolean) 


155
156
157
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 155

def isKernel?(node)
  getNeighborCount(node) == 3
end

#isSpecies?(node) ⇒ Boolean

Returns:

  • (Boolean) 


152
153
154
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 152

def isSpecies?(node)
  getNeighborCount(node) == 1
end

#makeName(i, names) ⇒ Object 



63
64
65
66
67
68
69
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 63

def makeName(i, names)
  if (i < names.size)
    return names[i].gsub(/[.].*/,'')
  else
    return CLConfig.getDefaultConfig.internalNodePrefix() + (i - names.size).to_s
  end
end

#mutateComplex ⇒ Object 



280
281
282
283
284
285
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 280

def mutateComplex()
  orig = clone()
  begin
    mutateRandom
  end while RunEnv.zrand(0) < 0.5 || (orig <=> self) == 0
end

#mutateRandom ⇒ Object 



269
270
271
272
273
274
275
276
277
278
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 269

def mutateRandom()
  begin
  c = RunEnv.zrand(3)
  end while c == 1 && getNodeCount <= 10
  case c
    when 0 then mutateSpecies
    when 1 then mutateSubtreeInterchange
    when 2 then mutateSubtreeTransfer
  end
end

#mutateSpecies ⇒ Object 



221
222
223
224
225
226
227
228
229
230
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 221

def mutateSpecies()
  begin
    a,b = randomSpeciesNodes(2)
    na,nb = getNeighbors(a)[0],getNeighbors(b)[0]
  end until na != nb
  disconnect(a,na)
  disconnect(b,nb)
  connect(a,nb)
  connect(b,na)
end

#mutateSubtreeInterchange ⇒ Object 



232
233
234
235
236
237
238
239
240
241
242
243
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 232

def mutateSubtreeInterchange()
  p = nil
  begin
    a,b = randomKernelNodes(2)
    p = findPath(a,b)
  end until (p.size > 3)
  na,nb = p[1],p[-2]
  disconnect(a,na)
  disconnect(b,nb)
  connect(a,nb)
  connect(b,na)
end

#mutateSubtreeTransfer ⇒ Object 



245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 245

def mutateSubtreeTransfer()
  begin
    k1, k2 = randomNode, randomKernelNode()
    p = findPath(k1,k2)
  end until p.size > 2
  i1 = p[1]
  disconnect(k1,i1)
  ms = getNeighbors(i1)
  m1,m2,m3 = ms[0],ms[1],nil
  begin
    m3 = randomNeighbor(k2)
  end until m3 != p[-2]
  [[m1,i1], [m2,i1], [m3,k2]].each { |a| disconnect(a[0],a[1]) }
  [[m1,m2], [k2,i1], [m3,i1], [k1,i1]].each { |a| connect(a[0],a[1]) }
end

#randomKernelNode ⇒ Object 



261
262
263
264
265
266
267
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 261

def randomKernelNode()
  n = nil
  begin
    n = randomNode()
  end until isKernel?(n)
  n
end

#randomKernelNodes(count) ⇒ Object 



213
214
215
216
217
218
219
220
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 213

def randomKernelNodes(count)
  raise "Not enough kernel nodes" unless getKernelCount() >= count
  res = { }
  begin
    res[randomKernelNode()] = true
  end until res.size == count
  res.keys
end

#randomNeighbor(node) ⇒ Object 



161
162
163
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 161

def randomNeighbor(node)
  @edges[node][RunEnv.zrand(@edges[node].size)]
end

#randomNode ⇒ Object 



202
203
204
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 202

def randomNode()
  RunEnv.zrand(getNodeCount())
end

#randomNodes(count) ⇒ Object 



205
206
207
208
209
210
211
212
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 205

def randomNodes(count)
  raise "Not enough nodes" unless getNodeCount() >= count
  res = { }
  begin
    res[randomNode()] = true
  end until res.size == count
  res.keys
end

#randomSpeciesNode ⇒ Object 



187
188
189
190
191
192
193
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 187

def randomSpeciesNode()
  n = nil
  begin
    n = randomNode()
  end until isSpecies?(n)
  n
end

#randomSpeciesNodes(count) ⇒ Object 



194
195
196
197
198
199
200
201
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 194

def randomSpeciesNodes(count)
  raise "Not enough species nodes" unless getSpeciesCount() >= count
  res = { }
  begin
    res[randomSpeciesNode()] = true
  end until res.size == count
  res.keys
end

#to_s ⇒ Object 



80
81
82
83
84
85
86
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 80

def to_s()
  result = ""
  @edges.each_index { |i|
    result += "#{i}->"+@edges[i].join(",")+"\n"
  }
  result
end

#toDotString(names, title, desc) ⇒ Object 



70
71
72
73
74
75
76
77
78
79
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 70

def toDotString(names, title, desc)
  result = "/* #{desc} */\ngraph #{title} {\n"
  @edges.each_index { |i|
    @edges[i].each { |j|
    result += "#{makeName(i,names)} -- #{makeName(j,names)}\n"
    }
  }
  result += "}\n"
  result
end

#verifyTree ⇒ Object 



287
288
289
290
291
292
293
294
295
296
 
# File 'ext/lib/CompLearnLib/Tree.rb', line 287

def verifyTree()
  oldNeighborCount = 0
  @edges.each_index { |i|
    s = @edges[i].size
    return false if s != 1 && s != 3
    oldNeighborCount = s if (s > oldNeighborCount)
    return false if s < oldNeighborCount
  }
  return true
end