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) 


39
40
41
 
# File 'lib/page_rank/base.rb', line 39

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



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

def calculate(max_iterations: -1, **_)
  ranks = initial_ranks
  loop do
    break if max_iterations == 0
    ranks, prev_ranks = calculate_step(ranks), 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
24
 
# File 'lib/page_rank/base.rb', line 20

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

#tolerance=(tolerance) ⇒ Float

Set the tolerance value

Parameters:

  • tolerance (Float) —

    The desired accuracy of the results

Returns:

  • (Float)

Raises:

  • (ArgumentError) 


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

def tolerance=(tolerance)
  @tolerance = tolerance || 0.0001
  raise ArgumentError.new('Invalid tolerance factor') if @tolerance < 0 || @tolerance > 1
  @tolerance
end