class ActiveFacts::DependencyAnalyser

Public Class Methods

new(enumerable, &block) click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 3
def initialize enumerable, &block
  @enumerable = enumerable
  analyse_precursors &block
end

Public Instance Methods

analyse_chasers() click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 40
def analyse_chasers
  analyse_precursors_transitive unless @precursors_transitive
  analyse_followers unless @followers

  # A follower is an object with us as a precursor, that has no new precursors of its own
  @chasers = {}
  @enumerable.each do |item|
    @chasers[item] =
      @enumerable.select do |follower|
        @precursors[follower].include?(item) and
        (@precursors_transitive[follower] - @precursors_transitive[item] - [item]).size == 0
      end
  end
end
analyse_followers() click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 31
def analyse_followers
  @followers = Hash.new{|h, k| h[k] = [] }
  @enumerable.each do |item|
    @precursors[item].each do |precursor|
      @followers[precursor] << item
    end
  end
end
analyse_precursors(&block) click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 8
def analyse_precursors &block
  @precursors = {}
  @enumerable.each do |item|
    @precursors[item] = block.call(item)
  end
end
analyse_precursors_transitive() click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 15
def analyse_precursors_transitive
  all_precursors = proc do |item|
      p = @precursors[item]
      all =
        p + p.map do |precursor|
          p.include?(precursor) ? [] : all_precursors.call(precursor)
        end.flatten
      all.uniq
    end

  @precursors_transitive = {}
  @enumerable.each do |item|
    @precursors_transitive[item] = all_precursors.call(item)
  end
end
chasers(item) { |follower, item| ... } click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 135
def chasers item, &b
  analyse_chasers unless @chasers
  if item
    if block_given?
      Array(@chasers[item]).each { |follower| yield follower, item }
    else
      Array(@chasers[item])
    end
  else
    @enumerable.each do |item|
      follower(item, &b)
    end
  end
end
each() { |item| ... } click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 82
def each &b
  if block_given?
    @enumerable.each { |item| yield item}
  else
    @enumerable
  end
end
followers(item = nil) { |follower, item| ... } click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 120
def followers item = nil, &b
  analyse_followers unless @followers
  if item
    if block_given?
      Array(@followers[item]).each { |follower| yield follower, item }
    else
      Array(@followers[item])
    end
  else
    @enumerable.each do |item|
      followers(item, &b)
    end
  end
end
page_rank(damping = 0.85, &weight) click to toggle source

Compute the page rank of the objects If used, the block shold return the starting weight

# File lib/activefacts/dependency_analyser.rb, line 152
def page_rank damping = 0.85, &weight
  weight ||= proc {|item| 1.0}

  @total = 0
  @rank = {}
  @enumerable.each do |item|
    @total += 
      (@rank[item] = weight.call(item) * 1.0)
  end
  # Normalize:
  @enumerable.each do |item|
    @rank[item] /= @total
  end

  50.times do |iteration|
    @enumerable.each do |item|
      links = (precursors(item) + followers(item)).uniq
      linked_rank = links.map do |l|
          onward_links = (precursors(l) + followers(l)).uniq || @enumerable.size
          @rank[l] / onward_links.size
        end.inject(&:+) || 0
      @rank[item] = (1.0-damping) + damping*linked_rank
    end
  end

  @rank
end
precursors(item = nil) { |precursor, item| ... } click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 90
def precursors item = nil, &b
  analyse_precursors unless @precursors
  if item
    if block_given?
      Array(@precursors[item]).each { |precursor| yield precursor, item }
    else
      Array(@precursors[item])
    end
  else
    @enumerable.each do |item|
      precursors(item, &b)
    end
  end
end
precursors_transitive(item) { |precursor, item| ... } click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 105
def precursors_transitive item, &b
  analyse_precursors_transitive unless @precursors_transitive
  if item
    if block_given?
      Array(@precursors_transitive[item]).each { |precursor| yield precursor, item }
    else
      Array(@precursors_transitive[item])
    end
  else
    @enumerable.each do |item|
      precursors_transitive(item, &b)
    end
  end
end
tsort(&block) click to toggle source
# File lib/activefacts/dependency_analyser.rb, line 55
def tsort &block
  analyse_precursors unless @precursors
  emitted = {}
  pass = 0
  until emitted.size == @enumerable.size
    next_items = []
    blocked =
      @enumerable.inject({}) do |hash, item|
        next hash if emitted[item]
        blockers = item.precursors.select{|precursor| !emitted[precursor]}
        if blockers.size > 0
          hash[item] = blockers
        else
          next_items << item
        end
        hash
      end
    return blocked if next_items.size == 0  # Cannot make progress
    # puts "PASS #{pass += 1}"
    next_items.each do |item|
      block.call(item)
      emitted[item] = true
    end
  end
  nil
end