Class: PageRank

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Enumerable
Defined in:
lib/page_rank.rb,
lib/page_rank/version.rb

Defined Under Namespace

Modules: Version

Constant Summary collapse

DEFAULT_CONVERGENCE = 
1e-8
DEFAULT_MAX_ITERATIONS = 
1000
DEFAULT_DAMPING_FACTOR = 
0.85
VERSION = 
Version.to_s

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size, options = {}) ⇒ PageRank

Returns a new instance of PageRank.



66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/page_rank.rb', line 66

def initialize(size, options = {})
  @size, @idmap, @matrix, @iterations, @ranking, @divergence =
    size, Hash.idmap(-1), GSL::Matrix.zeros(size), 0, [], []

  @dangling_nodes, @initialization_vector =
    GSL::Vector::Col.alloc(size).set_all(1),
    GSL::Vector::Col.alloc(size).set_all(Rational(1, size))

  @convergence    = options.fetch(:convergence,    DEFAULT_CONVERGENCE)
  @max_iterations = options.fetch(:max_iterations, DEFAULT_MAX_ITERATIONS)
  @damping_factor = options.fetch(:damping_factor, DEFAULT_DAMPING_FACTOR)
end

Instance Attribute Details

#convergence ⇒ Object

Returns the value of attribute convergence.



83
84
85
 
# File 'lib/page_rank.rb', line 83

def convergence
  @convergence
end

#damping_factor ⇒ Object

Returns the value of attribute damping_factor.



83
84
85
 
# File 'lib/page_rank.rb', line 83

def damping_factor
  @damping_factor
end

#dangling_nodes ⇒ Object (readonly)

Returns the value of attribute dangling_nodes.



81
82
83
 
# File 'lib/page_rank.rb', line 81

def dangling_nodes
  @dangling_nodes
end

#divergence ⇒ Object (readonly)

Returns the value of attribute divergence.



79
80
81
 
# File 'lib/page_rank.rb', line 79

def divergence
  @divergence
end

#initialization_vector ⇒ Object (readonly)

Returns the value of attribute initialization_vector.



81
82
83
 
# File 'lib/page_rank.rb', line 81

def initialization_vector
  @initialization_vector
end

#iterations ⇒ Object (readonly)

Returns the value of attribute iterations.



79
80
81
 
# File 'lib/page_rank.rb', line 79

def iterations
  @iterations
end

#matrix ⇒ Object (readonly)

Returns the value of attribute matrix.



81
82
83
 
# File 'lib/page_rank.rb', line 81

def matrix
  @matrix
end

#max_iterations ⇒ Object

Returns the value of attribute max_iterations.



83
84
85
 
# File 'lib/page_rank.rb', line 83

def max_iterations
  @max_iterations
end

#ranking ⇒ Object (readonly)

Returns the value of attribute ranking.



79
80
81
 
# File 'lib/page_rank.rb', line 79

def ranking
  @ranking
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



79
80
81
 
# File 'lib/page_rank.rb', line 79

def size
  @size
end

Class Method Details

.from_hash(hash, *args) ⇒ Object 



47
48
49
50
 
# File 'lib/page_rank.rb', line 47

def from_hash(hash, *args)
  s = hash.to_a.flatten.uniq
  new(s.size, *args).seed(s.sort_by { |k| sortkey(k) }) << hash
end

.from_json(path, *args) ⇒ Object 



52
53
54
 
# File 'lib/page_rank.rb', line 52

def from_json(path, *args)
  from_hash(JSON.parse(File.read(path)), *args)
end

Instance Method Details

#<<(hash) ⇒ Object 



110
111
112
113
 
# File 'lib/page_rank.rb', line 110

def <<(hash)
  hash.each { |k, v| self[k] = v }
  self
end

#[]=(k, v) ⇒ Object 



115
116
117
118
119
 
# File 'lib/page_rank.rb', line 115

def []=(k, v)
  w = Rational(1, v.size)
  dangling_nodes[i = id(k)] = 0
  v.each { |l| matrix[i, id(l)] = w }
end

#each ⇒ Object 



133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/page_rank.rb', line 133

def each
  return enum_for(__method__) unless block_given?

  index = -1

  matrix.each_row { |r|
    k, v = index += 1, r.where.to_a
    yield key(k), v.map! { |l| key(l) }.sort! unless v.empty?
  }

  self
end

#inspect ⇒ Object 



95
96
97
98
99
100
101
102
103
 
# File 'lib/page_rank.rb', line 95

def inspect
  s = '#<%s:0x%x>' % [self.class, object_id]

  %w[size count convergence max_iterations damping_factor].each { |v|
    s.insert(-2, " @#{v}=#{send(v).inspect}")
  }

  s
end

#rank(personalization = true) ⇒ Object 



121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/page_rank.rb', line 121

def rank(personalization = true)
  iv, v = initialization_vector.dup, personalization

  order(iterate(case v
    when true    then iv
    when 0       then iv.set_zero
    when Float   then iv.set_all(v)
    when Integer then iv.set_all(Rational(1, v))
    else              v
  end)) unless empty?
end

#seed(list) ⇒ Object 



105
106
107
108
 
# File 'lib/page_rank.rb', line 105

def seed(list)
  list.each { |k| id(k) }
  self
end

#to_json ⇒ Object 



146
147
148
 
# File 'lib/page_rank.rb', line 146

def to_json
  JSON.fast_generate(to_h)
end

#to_table ⇒ Object 



150
151
152
153
 
# File 'lib/page_rank.rb', line 150

def to_table
  matrix.to_a.map.with_index { |r, i| [key(i) || i + 1,
    r.map.with_index { |v, j| [key(j) || j + 1, v] }] }
end