Class: Amp::Graphs::AncestorCalculator

Inherits:
Object
  • Object
show all
Defined in:
lib/amp/graphs/ancestor.rb

Class Method Summary collapse

Class Method Details

.ancestors(a, b, parent_func) ⇒ Object

Returns the closest common ancestor between A and B, given a method that says how to find the parent of a node.

Parameters:

  • a —

    the first node

  • b —

    the second node (order doesn’t matter)

  • parent_func —

    a way to determine the parents of a node. Should eventually be made to a block, perhaps.

Returns:

  • the node_id of the least-common ancestor.



102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/amp/graphs/ancestor.rb', line 102

def self.ancestors(a, b, parent_func)
  return a if a == b
  to_visit = [a, b]
  depth = {}
  until to_visit.empty?
    vertex = to_visit.last
    parent_list = parent_func.call(vertex)
    if parent_list.empty?
      depth[vertex] = 0
      to_visit.pop
    else
      parent_list.each do |parent|
        return parent if parent == a || parent == b
        to_visit << parent unless depth[parent]
      end
      if to_visit.last == vertex
        depth[vertex] = parent_list.map {|p| depth[p]}.min - 1
        to_visit.pop
      end
    end
  end
  
  x = AncestorGenerator.new(a, depth, parent_func)
  y = AncestorGenerator.new(b, depth, parent_func)
  
  gx = x.next
  gy = y.next
  
  while gx && gy
    if gx[0] == gy[0]
      gx[1].each do |k,v|
        return k if gy[1].include? k
      end
      gx = x.next
      gy = y.next
    elsif gx[0] > gy[0]
      gy = y.next
    else
      gx = x.next
    end
  end
  return nil
end