Class: Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/usearchtree/graph.rb

Overview

Represents any weighted, directed graph.

Author: Johnny Lee Othon

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



6
7
8
9
 
# File 'lib/usearchtree/graph.rb', line 6

def initialize
    @nodes = Array.new
    @next_id = 0
end

Instance Method Details

#add_edge(i, j, cost) ⇒ Object

Adds an edge from node i to node j. Where i and j can be an index or a name.



40
41
42
 
# File 'lib/usearchtree/graph.rb', line 40

def add_edge i, j, cost
    self.node(i).add_edge self.node(j), cost
end

#add_node(name = nil) ⇒ Object

Adds a node to the graph and optionally sets a name.



34
35
36
 
# File 'lib/usearchtree/graph.rb', line 34

def add_node name=nil
    @nodes << Node.new(self.next_id, name)
end

#cost(i, j) ⇒ Object

Gets the cost from node at i to node at j.



55
56
57
58
59
 
# File 'lib/usearchtree/graph.rb', line 55

def cost i, j
    nodeI = (i.kind_of? Node) ? i : self.node(i)
    nodeJ = (j.kind_of? Node) ? j : self.node(j)
    nodeI.cost(nodeJ)
end

#label_node(i, name) ⇒ Object

Labels a single node with index i. Fails if the node does not exist.



45
46
47
 
# File 'lib/usearchtree/graph.rb', line 45

def label_node i, name
    @nodes[i].name = name
end

#length ⇒ Object

Gets the number of nodes in the graph



50
51
52
 
# File 'lib/usearchtree/graph.rb', line 50

def length
    @nodes.length
end

#next_id ⇒ Object

Gets and increases the next id.



62
63
64
65
66
 
# File 'lib/usearchtree/graph.rb', line 62

def next_id
    id = @next_id
    @next_id += 1
    id
end

#node(key) ⇒ Object 



25
26
27
28
29
30
31
 
# File 'lib/usearchtree/graph.rb', line 25

def node key
    if key.kind_of? Integer
        @nodes[key]
    else
        @nodes.find{|n| n.name == key}
    end
end

#to_adjacency_lists ⇒ Object

Returns the graph as a list of adjacencies



17
18
19
20
21
22
23
 
# File 'lib/usearchtree/graph.rb', line 17

def to_adjacency_lists
    if @nodes.empty?
        "Empty graph"
    else
        @nodes.collect{|node| node.to_adjacency_list}.join("\n")
    end
end

#to_s ⇒ Object

Returns the list of nodes



12
13
14
 
# File 'lib/usearchtree/graph.rb', line 12

def to_s
    @nodes.to_s
end