Class: PageRank::Base

Inherits:
Object
  • Object
show all
Defined in:
lib/page_rank/base.rb

Overview

A base class for PageRank implementations. This class provides the basic framework for adding (optionall weighted) nodes to the graph and then performing iterations of PageRank to within the desired tolerance (or maximum allowed number of iterations).

Direct Known Subclasses

Dense, Sparse

Instance Method Summary collapse

Constructor Details

#initialize(damping: nil, tolerance: nil, **_) ⇒ Base

Returns a new instance of Base.

Parameters:

  • damping (Float) (defaults to: nil) —

    The probability of following the graph vs. randomly choosing a new node

  • tolerance (Float) (defaults to: nil) —

    The desired accuracy of the results



12
13
14
15
 
# File 'lib/page_rank/base.rb', line 12

def initialize(damping: nil, tolerance: nil, **_)
  self.damping = damping
  self.tolerance = tolerance
end

Instance Method Details

#add(_source, _dest, **_options) ⇒ nil

Adds a directed (and optionally weighted) edge to the graph

Parameters:

  • _source (Object) —

    The source node

  • _dest (Object) —

    The destination node

Returns:

  • (nil)

Raises:

  • (NotImplementedError) 


37
38
39
 
# File 'lib/page_rank/base.rb', line 37

def add(_source, _dest, **_options)
  raise NotImplementedError
end

#calculate(max_iterations: -1,, **_) ⇒ Hash<Object, Float>

Perform the PageRank calculation

Parameters:

  • max_iterations (Fixnum) (defaults to: -1,) —

    Maximum number of PageRank iterations to perform (or -1 for no max)

Returns:

  • (Hash<Object, Float>) —

    of nodes with rank



44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/page_rank/base.rb', line 44

def calculate(max_iterations: -1, **_)
  ranks = initial_ranks
  loop do
    break if max_iterations.zero?

    prev_ranks = ranks
    ranks = calculate_step(ranks)
    break if distance(ranks, prev_ranks) < @tolerance

    max_iterations -= 1
  end
  sort_ranks(ranks)
end

#damping=(damping) ⇒ Float

Set the damping probability

Parameters:

  • damping (Float) —

    The probability of following the graph vs. randomly choosing a new node

Returns:

  • (Float)

Raises:

  • (ArgumentError) 


20
21
22
23
 
# File 'lib/page_rank/base.rb', line 20

def damping=(damping)
  @damping = damping || 0.85
  raise ArgumentError, 'Invalid damping factor' if @damping <= 0 || @damping > 1
end

#tolerance=(tolerance) ⇒ Float

Set the tolerance value

Parameters:

  • tolerance (Float) —

    The desired accuracy of the results

Returns:

  • (Float)

Raises:

  • (ArgumentError) 


28
29
30
31
 
# File 'lib/page_rank/base.rb', line 28

def tolerance=(tolerance)
  @tolerance = tolerance || 0.0001
  raise ArgumentError, 'Invalid tolerance factor' if @tolerance.negative? || @tolerance > 1
end