Class: Wads::Graph

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

Overview

A Graph helps manage nodes by providing high level methods to add or connect nodes to the graph. It also maintains a list of nodes and supports having multiple root nodes, i.e. nodes with no incoming connections. This class also supports constructing the graph from data stored in a file.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root_node = nil) ⇒ Graph

Returns a new instance of Graph.



484
485
486
487
488
489
490
491
492
493
494
495
496
 
# File 'lib/wads/data_structures.rb', line 484

def initialize(root_node = nil)
    @node_list = []
    @node_map = {}
    if root_node 
        if root_node.is_a? Node
            root_node.visit do |n|
                add_node(n)
            end
        elsif root_node.is_a? String 
            read_graph_from_file(root_node)
        end
    end
end

Instance Attribute Details

#node_list ⇒ Object

Returns the value of attribute node_list.



481
482
483
 
# File 'lib/wads/data_structures.rb', line 481

def node_list
  @node_list
end

#node_map ⇒ Object

Returns the value of attribute node_map.



482
483
484
 
# File 'lib/wads/data_structures.rb', line 482

def node_map
  @node_map
end

Instance Method Details

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



498
499
500
 
# File 'lib/wads/data_structures.rb', line 498

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

#add_edge(source, target, tags = {}) ⇒ Object 



533
534
535
536
537
538
539
540
541
 
# File 'lib/wads/data_structures.rb', line 533

def add_edge(source, target, tags = {})
    if source.is_a? String 
        source = find_node(source)
    end 
    if target.is_a? String 
        target = find_node(target)
    end 
    source.add_output_edge(target, tags)
end

#add_node(node) ⇒ Object 



528
529
530
531
 
# File 'lib/wads/data_structures.rb', line 528

def add_node(node) 
    @node_list << node 
    @node_map[node.name] = node 
end

#connect(source, destination, tags = {}) ⇒ Object 



502
503
504
 
# File 'lib/wads/data_structures.rb', line 502

def connect(source, destination, tags = {})
    add_edge(source, destination)
end

#delete(node) ⇒ Object 



506
507
508
509
510
511
512
513
514
515
 
# File 'lib/wads/data_structures.rb', line 506

def delete(node) 
    if node.is_a? String 
        node = find_node(node)
    end 
    node.backlinks.each do |backlink| 
        backlink.remove_output(node.name)
    end
    @node_list.delete(node)
    @node_map.delete(node.name)
end

#disconnect(source, target) ⇒ Object 



517
518
519
520
521
522
523
524
525
526
 
# File 'lib/wads/data_structures.rb', line 517

def disconnect(source, target)
    if source.is_a? String 
        source = find_node(source)
    end 
    if target.is_a? String 
        target = find_node(target)
    end 
    source.remove_output(target.name)
    target.remove_backlink(source.name)
end

#find_node(name) ⇒ Object 



574
575
576
 
# File 'lib/wads/data_structures.rb', line 574

def find_node(name) 
    @node_map[name]
end

#get_number_of_connections_range ⇒ Object 



556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
 
# File 'lib/wads/data_structures.rb', line 556

def get_number_of_connections_range 
    # Find the min and max
    min = 1000
    max = 0
    @node_list.each do |node|
        num_links = node.number_of_links
        if num_links < min 
            min = num_links 
        end 
        if num_links > max 
            max = num_links 
        end
    end 
    
    # Then create the scale
    DataRange.new(min - 0.1, max + 0.1)
end

#is_cycle(node) ⇒ Object 



609
610
611
612
613
614
615
616
617
618
619
 
# File 'lib/wads/data_structures.rb', line 609

def is_cycle(node)
    reset_visited
    node.visit do |n|
        if n.visited 
            return true
        else 
            n.visited = true
        end
    end
    false
end

#leaf_nodes ⇒ Object 



599
600
601
602
603
604
605
606
607
 
# File 'lib/wads/data_structures.rb', line 599

def leaf_nodes 
    list = []
    @node_list.each do |node|
        if node.outputs.empty? 
            list << node 
        end  
    end 
    list 
end

#node_by_index(index) ⇒ Object 



578
579
580
 
# File 'lib/wads/data_structures.rb', line 578

def node_by_index(index) 
    @node_list[index] 
end

#node_with_most_connections ⇒ Object 



543
544
545
546
547
548
549
550
551
552
553
554
 
# File 'lib/wads/data_structures.rb', line 543

def node_with_most_connections 
    max_node = nil
    max = -1
    @node_list.each do |node|
        num_links = node.number_of_links
        if num_links > max 
            max = num_links 
            max_node = node
        end
    end 
    max_node
end

#process_tag_string(tags, tag_string) ⇒ Object 



656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
 
# File 'lib/wads/data_structures.rb', line 656

def process_tag_string(tags, tag_string) 
    parts = tag_string.partition("=")
    tag_name = parts[0]
    tag_value = parts[2]
    if tag_name == COLOR_TAG
        begin
            value = eval(tag_value)
            puts "Adding tag #{tag_name} = #{value}"
            tags[tag_name] = value 
        rescue => e
            puts "Ignoring tag #{tag_name} = #{tag_value}"
        end
    else
        puts "Adding tag #{tag_name} = #{tag_value}"
        tags[tag_name] = tag_value 
    end
end

#read_graph_from_file(filename) ⇒ Object

The format is a csv file as follows: N,name,value –> nodes C,source,destination –> connections (also called edges)

Optionally, each line type can be followed by comma-separated tag=value



679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
 
# File 'lib/wads/data_structures.rb', line 679

def read_graph_from_file(filename)
    puts "Read graph data from file #{filename}"
    File.readlines(filename).each do |line|
        line = line.chomp  # remove the carriage return
        values = line.split(",")
        type = values[0]
        tags = {}
        if type == "N" or type == "n"
            name = values[1]
            if values.size > 2
                value = values[2]
                # The second position can be a tag or the node value
                if value.include? "="
                    process_tag_string(tags, value)
                    value = nil 
                end 
            else 
                value = nil 
            end
            if values.size > 3
                values[3..-1].each do |tag_string|
                    process_tag_string(tags, tag_string) 
                end
            end
            add(name, value, tags)
        elsif type == "E" or type == "e" or type == "L" or type == "l" or type == "C" or type == "c"
            source_name = values[1]
            destination_name = values[2]
            if values.size > 3
                values[3..-1].each do |tag_string|
                    process_tag_string(tags, tag_string) 
                end
            end
            connect(source_name, destination_name, tags)
        else 
            puts "Ignoring line: #{line}"
        end
    end
end

#reset_visited ⇒ Object 



582
583
584
585
586
587
 
# File 'lib/wads/data_structures.rb', line 582

def reset_visited 
    @node_list.each do |node|
        node.visited = false 
        node.depth = 0
    end 
end

#root_nodes ⇒ Object 



589
590
591
592
593
594
595
596
597
 
# File 'lib/wads/data_structures.rb', line 589

def root_nodes 
    list = []
    @node_list.each do |node|
        if node.backlinks.empty? 
            list << node 
        end  
    end 
    list 
end

#traverse_and_collect_nodes(node, max_depth = 0, current_depth = 1) ⇒ Object 



621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
 
# File 'lib/wads/data_structures.rb', line 621

def traverse_and_collect_nodes(node, max_depth = 0, current_depth = 1)
    if max_depth > 0
        if current_depth > max_depth 
            return {}
        end
    end
    map = {}
    if node.visited 
        if current_depth < node.depth 
            node.depth = current_depth 
        end
        return {} 
    else
        map[node.name] = node
        node.depth = current_depth
        node.visited = true
    end
    node.outputs.each do |child|
        if child.is_a? Edge 
            child = child.destination 
        end
        map_from_child = traverse_and_collect_nodes(child, max_depth, current_depth + 1)
        map_from_child.each do |key, value|
            map[key] = value 
        end
    end 
    node.backlinks.each do |child|
        map_from_child = traverse_and_collect_nodes(child, max_depth, current_depth + 1)
        map_from_child.each do |key, value|
            map[key] = value 
        end
    end 
    map
end