Class: ActiveFacts::DependencyAnalyser
- Inherits:
-
Object
- Object
- ActiveFacts::DependencyAnalyser
- Defined in:
- lib/activefacts/dependency_analyser.rb
Instance Method Summary collapse
- #analyse_chasers ⇒ Object
- #analyse_followers ⇒ Object
- #analyse_precursors(&block) ⇒ Object
- #analyse_precursors_transitive ⇒ Object
- #chasers(item, &b) ⇒ Object
- #each(&b) ⇒ Object
- #followers(item = nil, &b) ⇒ Object
-
#initialize(enumerable, &block) ⇒ DependencyAnalyser
constructor
A new instance of DependencyAnalyser.
-
#page_rank(damping = 0.85, &weight) ⇒ Object
Compute the page rank of the objects If used, the block shold return the starting weight.
- #precursors(item = nil, &b) ⇒ Object
- #precursors_transitive(item, &b) ⇒ Object
- #tsort(&block) ⇒ Object
Constructor Details
#initialize(enumerable, &block) ⇒ DependencyAnalyser
Returns a new instance of DependencyAnalyser.
3 4 5 6 |
# File 'lib/activefacts/dependency_analyser.rb', line 3 def initialize enumerable, &block @enumerable = enumerable analyse_precursors &block end |
Instance Method Details
#analyse_chasers ⇒ Object
40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# 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 ⇒ Object
31 32 33 34 35 36 37 38 |
# 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) ⇒ Object
8 9 10 11 12 13 |
# 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 ⇒ Object
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# 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, &b) ⇒ Object
135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
# 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(&b) ⇒ Object
82 83 84 85 86 87 88 |
# 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, &b) ⇒ Object
120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
# 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) ⇒ Object
Compute the page rank of the objects If used, the block shold return the starting weight
152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
# 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, &b) ⇒ Object
90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
# 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, &b) ⇒ Object
105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
# 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) ⇒ Object
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
# 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 |