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, SparseNative

Instance Attribute Summary collapse

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



14
15
16
17
# File 'lib/page_rank/base.rb', line 14

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

Instance Attribute Details

#dampingObject

Returns the value of attribute damping.



10
11
12
# File 'lib/page_rank/base.rb', line 10

def damping
  @damping
end

#toleranceObject

Returns the value of attribute tolerance.



10
11
12
# File 'lib/page_rank/base.rb', line 10

def 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
56
57
58
# File 'lib/page_rank/base.rb', line 46

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