Class: Wads::Node

Inherits:
Object
  • Object
show all
Defined in:
lib/wads/data_structures.rb

Overview

A node in a graph data structure. Nodes can be used independently, and you connect them to other nodes, or you can use an overarching Graph instance to help manage them. Nodes can carry arbitrary metadata in the tags map. The children are either other nodes, or an Edge instance which can be used to add information about the connection. For example, in a map graph use case, the edge may contain information about the distance between the two nodes. In other applications, metadata about the edges, or connections, may not be necessary. This class, and the Graph data structure, support children in either form. Each child connection is a one-directional connection. The backlinks are stored and managed internally so that we can easily navigate between nodes of the graph. Nodes themselves have a name an an optional value.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(name, value = nil, tags = {}) ⇒ Node

Returns a new instance of Node.



299
300
301
302
303
304
305
306
307
 
# File 'lib/wads/data_structures.rb', line 299

def initialize(name, value = nil, tags = {})
    @name = name 
    @value = value
    @backlinks = [] 
    @outputs = []
    @visited = false
    @tags = tags
    @depth = 1
end

Instance Attribute Details

Returns the value of attribute backlinks.



288
289
290
 
# File 'lib/wads/data_structures.rb', line 288

def backlinks
  @backlinks
end

#depth ⇒ Object

Returns the value of attribute depth.



292
293
294
 
# File 'lib/wads/data_structures.rb', line 292

def depth
  @depth
end

#name ⇒ Object

Returns the value of attribute name.



286
287
288
 
# File 'lib/wads/data_structures.rb', line 286

def name
  @name
end

#outputs ⇒ Object

Returns the value of attribute outputs.



289
290
291
 
# File 'lib/wads/data_structures.rb', line 289

def outputs
  @outputs
end

#tags ⇒ Object

Returns the value of attribute tags.



291
292
293
 
# File 'lib/wads/data_structures.rb', line 291

def tags
  @tags
end

#value ⇒ Object

Returns the value of attribute value.



287
288
289
 
# File 'lib/wads/data_structures.rb', line 287

def value
  @value
end

#visited ⇒ Object

Returns the value of attribute visited.



290
291
292
 
# File 'lib/wads/data_structures.rb', line 290

def visited
  @visited
end

Instance Method Details

#add(name, value = nil, tags = {}) ⇒ Object 



309
310
311
 
# File 'lib/wads/data_structures.rb', line 309

def add(name, value = nil, tags = {})
    add_output_node(Node.new(name, value, tags))
end

#add_child(name, value) ⇒ Object 



321
322
323
 
# File 'lib/wads/data_structures.rb', line 321

def add_child(name, value)
    add_output(name, value)
end

#add_output(name, value) ⇒ Object 



325
326
327
328
 
# File 'lib/wads/data_structures.rb', line 325

def add_output(name, value)
    child_node = Node.new(name, value)
    add_output_node(child_node) 
end

#add_output_edge(destination, tags = {}) ⇒ Object 



336
337
338
339
340
341
 
# File 'lib/wads/data_structures.rb', line 336

def add_output_edge(destination, tags = {})
    edge = Edge.new(destination, tags)
    destination.backlinks << self
    @outputs << edge
    edge
end

#add_output_node(child_node) ⇒ Object 



330
331
332
333
334
 
# File 'lib/wads/data_structures.rb', line 330

def add_output_node(child_node)
    child_node.backlinks << self
    @outputs << child_node
    child_node
end

#add_tag(key, value) ⇒ Object 



372
373
374
 
# File 'lib/wads/data_structures.rb', line 372

def add_tag(key, value)
    @tags[key] = value 
end

#bfs(max_depth, &block) ⇒ Object 



412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
 
# File 'lib/wads/data_structures.rb', line 412

def bfs(max_depth, &block)
    node_queue = [self]
    @depth = 1
    until node_queue.empty?
        node = node_queue.shift
        yield node
        node.visited = true
        if node.depth < max_depth
            # Get the set of all outputs and backlinks
            h = {}
            node.outputs.each do |n|
                if n.is_a? Edge 
                    n = n.destination 
                end 
                h[n.name] = n 
            end 
            node.backlinks.each do |n|
                h[n.name] = n 
            end 

            h.values.each do |n|
                if n.visited 
                    # ignore, don't process again
                else
                    n.visited = true
                    n.depth = node.depth + 1
                    node_queue << n
                end
            end
        end
    end
end

#children ⇒ Object 



313
314
315
 
# File 'lib/wads/data_structures.rb', line 313

def children 
    @outputs 
end

#find_node(search_name) ⇒ Object 



380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
 
# File 'lib/wads/data_structures.rb', line 380

def find_node(search_name)
    if @name == search_name
        return self
    end
    found_node_in_child = nil
    
    @outputs.each do |child|
        if child.is_a? Edge 
            child = child.destination 
        end
        found_node_in_child = child.find_node(search_name)
        if found_node_in_child
            return found_node_in_child
        end 
    end
    nil
end

#get_tag(key) ⇒ Object 



376
377
378
 
# File 'lib/wads/data_structures.rb', line 376

def get_tag(key) 
    @tags[key] 
end

#id ⇒ Object 



294
295
296
297
 
# File 'lib/wads/data_structures.rb', line 294

def id 
    # id is an alias for name
    @name 
end

#number_of_links ⇒ Object 



317
318
319
 
# File 'lib/wads/data_structures.rb', line 317

def number_of_links 
    @outputs.size + @backlinks.size
end

#remove_backlink(name) ⇒ Object 



360
361
362
363
364
365
366
367
368
369
370
 
# File 'lib/wads/data_structures.rb', line 360

def remove_backlink(name)
    backlink_to_delete = nil
    @backlinks.each do |backlink|
        if backlink.id == name
            backlink_to_delete = backlink
        end 
    end 
    if backlink_to_delete
        @backlinks.delete(backlink_to_delete)
    end
end

#remove_output(name) ⇒ Object 



343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
 
# File 'lib/wads/data_structures.rb', line 343

def remove_output(name)
    output_to_delete = nil
    @outputs.each do |output|
        if output.is_a? Edge 
            output_node = output.destination 
            if output_node.id == name 
                output_to_delete = output
            end 
        elsif output.id == name
            output_to_delete = output
        end 
    end 
    if output_to_delete
        @outputs.delete(output_to_delete)
    end
end

#to_display ⇒ Object 



445
446
447
 
# File 'lib/wads/data_structures.rb', line 445

def to_display 
    "Node #{@name}: #{value}   inputs: #{@backlinks.size}  outputs: #{@outputs.size}"
end

#visit(&block) ⇒ Object 



398
399
400
401
402
403
404
405
406
407
408
409
410
 
# File 'lib/wads/data_structures.rb', line 398

def visit(&block)
    node_queue = [self]
    until node_queue.empty?
        node = node_queue.shift
        yield node
        node.outputs.each do |c|
            if c.is_a? Edge 
                c = c.destination 
            end 
            node_queue << c
        end
    end
end