Module: OQGraph::Node

Defined in:
lib/oqgraph/node.rb

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.included(base) ⇒ Object 



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/oqgraph/node.rb', line 3

def self.included base
  base.instance_eval do
    def self.edge_class_name
      "#{self.name}Edge"
    end
    
    def self.edge_class
      edge_class_name.constantize
    end
    
    def self.rebuild_graph
      edge_class.create_graph_table
    end
    
    def oqgraph_table_name
      "#{table_name.singularize}_oqgraph"
    end
    
    has_many :outgoing_edges, {
       :class_name => edge_class_name,
       :foreign_key => :from_id,
       :include => :to,
       :dependent => :destroy
     }
  
    has_many :incoming_edges, {
       :class_name => edge_class_name,
       :foreign_key => :to_id,
       :include => :from,
       :dependent => :destroy
     }
  
    has_many :outgoing_nodes, :through => :outgoing_edges, :source => :to
    has_many :incoming_nodes, :through => :incoming_edges, :source => :from
    
    # Joins the oqgraph edge table. The select * ensures we get the weights.
    scope :join_oqgraph, select('*').joins("JOIN #{oqgraph_table_name} ON #{oqgraph_table_name}.linkid=id")
    scope :order_oqgraph, order("#{oqgraph_table_name}.seq")
    # Latch: 0 = only find direct connections, 1 = use Djikstra algorithm, 2 = use Breadth first algorithm
    scope :originating,   lambda{|latch, destid|         join_oqgraph.where("#{oqgraph_table_name}.latch = ? AND #{oqgraph_table_name}.destid = ?", latch, destid).order_oqgraph}
    scope :reachable,     lambda{|latch, origid|         join_oqgraph.where("#{oqgraph_table_name}.latch = ? AND #{oqgraph_table_name}.origid = ?", latch, origid).order_oqgraph}
    scope :shortest_path, lambda{|latch, origid, destid| join_oqgraph.where("#{oqgraph_table_name}.latch = ? AND #{oqgraph_table_name}.origid = ? AND #{oqgraph_table_name}.destid = ?", latch, origid, destid).order_oqgraph}
  end
end

Instance Method Details

#create_edge_to(other, weight = 1.0) ⇒ Object

Creates a one way edge from this node to another with a weight.



49
50
51
 
# File 'lib/oqgraph/node.rb', line 49

def create_edge_to(other, weight = 1.0)
  self.class.edge_class.create!(:from_id => id, :to_id => other.id, :weight => weight)
end

#create_edge_to_and_from(other, weight = 1.0) ⇒ Object

other graph node to edge to weight positive float denoting edge weight Creates a two way edge between this node and another.



56
57
58
59
 
# File 'lib/oqgraph/node.rb', line 56

def create_edge_to_and_from(other, weight = 1.0)
  self.class.edge_class.create!(:from_id => id, :to_id => other.id, :weight => weight)
  self.class.edge_class.create!(:from_id => other.id, :to_id => id, :weight => weight)
end

#originating ⇒ Object

Returns an array of all nodes which can trace to this node



79
80
81
 
# File 'lib/oqgraph/node.rb', line 79

def originating
  self.class.originating(2, id)
end

#originating?(other) ⇒ Boolean

true if the other node can reach this node.

Returns:

  • (Boolean) 


88
89
90
 
# File 'lib/oqgraph/node.rb', line 88

def originating? other
  originating.include? other
end

#originating_neighbours ⇒ Object 



83
84
85
 
# File 'lib/oqgraph/node.rb', line 83

def originating_neighbours
  self.class.originating(0, id)
end

#path_weight_to(other) ⇒ Object

other The target node to find a route to Gives the path weight as a float of the shortest path to the other



74
75
76
 
# File 'lib/oqgraph/node.rb', line 74

def path_weight_to(other)
  shortest_path_to(other,:method => :djikstra).map{|edge| edge.weight.to_f}.sum
end

#reachable ⇒ Object

Returns all nodes reachable from this node.



93
94
95
 
# File 'lib/oqgraph/node.rb', line 93

def reachable
  self.class.reachable(2, id)
end

#reachable?(other) ⇒ Boolean

Returns all nodes reachable from this node.

Returns:

  • (Boolean) 


98
99
100
 
# File 'lib/oqgraph/node.rb', line 98

def reachable? other
  reachable.include? other
end

#shortest_path_to(other, options = {:method => :djikstra}) ⇒ Object

other The target node to find a route to options A hash of options: Currently the only option is

:method => :djiskstra or :breadth_first

Returns an array of nodes in order starting with this node and ending in the target This will be the shortest path from this node to the other. The :djikstra method takes edge weights into account, the :breadth_first does not.



67
68
69
70
 
# File 'lib/oqgraph/node.rb', line 67

def shortest_path_to(other, options = {:method => :djikstra})
  latch = options[:method] == :breadth_first ? 2 : 1
  self.class.shortest_path(latch, id, other.id)
end