Class: Amp::Graphs::AncestorGenerator

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

Overview

AncestorGenerator

A generator class that will allow us to only calculate one ancestor of a node at a time, so we don’t have to process the full list of ancestors for each node twice. Our old, lazy way was, if you have two nodes A and B, and need to find the common ancestor, we would generate all nodes in both A, and B’s history. If the two have a very close common ancestor (usually the case when doing a branch merge in a rapid development environment), then this is a huge amount of wasted processing. Generators aren’t a familiar construct for most ruby developers, and they work via continuations, which are also typically avoided like the plague. Check out ‘lib/support/generator.rb’ to see how it works.

A   B
|   |
|   |
|   |
|___| <-- target ancestor
    |
    | <-- don't need to generate this node, so we take one at a time

Instance Method Summary collapse

Methods inherited from Generator

#next, #reset

Constructor Details

#initialize(vertex, depth, parent_func) ⇒ AncestorGenerator

Returns a new instance of AncestorGenerator.



27
28
29
 
# File 'lib/amp/graphs/ancestor.rb', line 27

def initialize(vertex, depth, parent_func)
  @vertex, @depth_hash, @parent_func = vertex, depth, parent_func
end

Instance Method Details

#generator_loop {|depth, generation| ... } ⇒ Object

Yields each depth in succession from lowest depth to highest depth, with each node in that depth as a hash.

Parameters:

  • vertex —

    the base vertex to start from

  • depth —

    a hash assigning each node to its depth from the vertex

  • parent_func (Proc) —

    a proc that gives the parents of a node

Yields:

  • each generation - a set of vertices that are a given depth from the node

Yield Parameters:

  • depth —

    the depth that this generation is from the head vertex provided

  • generation —

    the generation, as a hash assigning entries in that generation to true.



75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/amp/graphs/ancestor.rb', line 75

def generator_loop
  sg, s = nil, {}
  traverse_ancestors do |hash|
    g, v = hash[:depth], hash[:node]
    if g != sg
      yield_gen [sg, s] if sg
      sg, s = g, {v => true}
    else
      s[v] = true
    end
  end
  yield_gen [sg, s]
  nil
end

#traverse_ancestors {|a| ... } ⇒ Object

Internal method that, given a vertex, a depth-hash, and a way to find parents, will yield all the ancestors of a node, in order of depth.

Parameters:

  • vertex —

    the vertex ID of a node in the graph

  • depth_hash (Hash) —

    associates a node_id to its depth in the graph

  • parent_func (Proc) —

    a function that calcualtes the parents of a node

Yields:

  • every single ancestor in a row, from lowest depth to the highest

Yield Parameters:

  • a (Hash) —

    hash, with :node pointing to the ID, and :depth giving the depth of the node



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/amp/graphs/ancestor.rb', line 45

def traverse_ancestors
  h = PriorityQueue.new
  h[@vertex] = @depth_hash[@vertex]
  seen = {}
  until h.empty?
    node, depth = h.delete_min
    unless seen[node]
      seen[node] = true
      yield({:node => node, :depth => depth})
      @parent_func.call(node).each do |parent|
        h[parent] = @depth_hash[parent]
      end
    end
  end
end