Class: GraphEdge

Inherits:
ActiveRecord::Base
  • Object
show all
Defined in:
lib/graph_edge.rb

Overview

This is the non-volatile store for the graph data.

Class Method Summary collapse

Class Method Details

.create_graph_table ⇒ Object

Creates the OQgraph table if it does not exist and populate with edges.



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/graph_edge.rb', line 10

def self.create_graph_table     
  connection.execute <<-EOS
  CREATE TABLE IF NOT EXISTS #{oqgraph_table_name} (
      latch   SMALLINT  UNSIGNED NULL,
      origid  BIGINT    UNSIGNED NULL,
      destid  BIGINT    UNSIGNED NULL,
      weight  DOUBLE    NULL,
      seq     BIGINT    UNSIGNED NULL,
      linkid  BIGINT    UNSIGNED NULL,
      KEY (latch, origid, destid) USING HASH,
      KEY (latch, destid, origid) USING HASH
    ) ENGINE=OQGRAPH;
  EOS
  
  # if the DB server has restarted then there will be no records in the oqgraph table.
  if !up_to_date?
    connection.execute <<-EOS
      REPLACE INTO #{oqgraph_table_name} (origid, destid, weight) 
      SELECT #{from_key}, #{to_key}, #{weight_column} FROM #{table_name}
    EOS
  end                   
end

.in_edges(node) ⇒ Object

Finds the edges leading directly into the node FIXME: Note this currently does not work. I suspect a bug in OQGraph engine. Using the node classes incoming_nodes is equivalent to this.



78
79
80
81
82
83
84
 
# File 'lib/graph_edge.rb', line 78

def self.in_edges(node)
  sql = <<-EOS
   WHERE latch = 0 AND destid = #{node.id}
  EOS
  
  node_class.find_by_sql select_for_node << sql 
end

.originating_nodes(node) ⇒ Object

Finds all the nodes that lead to the node



55
56
57
58
59
60
61
62
 
# File 'lib/graph_edge.rb', line 55

def self.originating_nodes(node)    
  sql = <<-EOS
   WHERE latch = 1 AND destid = #{node.id}
   ORDER BY seq;
  EOS
  
  node_class.find_by_sql select_for_node << sql 
end

.out_edges(node) ⇒ Object

Finds the edges leading directly out of the node



87
88
89
90
91
92
93
 
# File 'lib/graph_edge.rb', line 87

def self.out_edges(node)    
  sql = <<-EOS
   WHERE latch = 0 AND origid = #{node.id}
  EOS

  node_class.find_by_sql select_for_node << sql 
end

.reachable_nodes(node) ⇒ Object

Finds all the nodes that are reachable from the node



65
66
67
68
69
70
71
72
 
# File 'lib/graph_edge.rb', line 65

def self.reachable_nodes(node)    
  sql = <<-EOS
   WHERE latch = 1 AND origid = #{node.id}
   ORDER BY seq;
  EOS
  
  node_class.find_by_sql select_for_node << sql 
end

.shortest_path(from, to, options) ⇒ Object

Returns the shortest path from node to node. options A hash containing options. The only option is :method which can be :breadth_first to do a breadth first search. It defaults to using Djikstra’s algorithm.



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/graph_edge.rb', line 38

def self.shortest_path(from, to, options)
  latch = case options[:method]
    when :breadth_first then 2
    else 1
  end  
  latch = 1
  latch = 2 if options[:method] == :breadth_first
  
  sql = <<-EOS
   WHERE latch = #{latch} AND origid = #{from.id} AND destid = #{to.id}
   ORDER BY seq;
  EOS
  
  node_class.find_by_sql select_for_node << sql
end