Add PageRank computation for vertices in Digraph.

Introduced classes

class PRMap[V: nullable Object]

graph :: PRMap

Map each Vertice of a Digraph to it's PageRank.

Redefined classes

redef interface Digraph[V: Object]

graph :: pagerank $ Digraph

Interface for digraphs

All class definitions

redef interface Digraph[V: Object]

graph :: pagerank $ Digraph

Interface for digraphs
class PRMap[V: nullable Object]

graph $ PRMap

Map each Vertice of a Digraph to it's PageRank.
package_diagram graph::pagerank pagerank graph::digraph digraph graph::pagerank->graph::digraph core core graph::digraph->core ...core ... ...core->core a_star-m a_star-m a_star-m->graph::pagerank

Ancestors

module abstract_collection

core :: abstract_collection

Abstract collection classes and services.
module abstract_text

core :: abstract_text

Abstract class for manipulation of sequences of characters
module array

core :: array

This module introduces the standard array structure.
module bitset

core :: bitset

Services to handle BitSet
module bytes

core :: bytes

Services for byte streams and arrays
module circular_array

core :: circular_array

Efficient data structure to access both end of the sequence.
module codec_base

core :: codec_base

Base for codecs to use with streams
module codecs

core :: codecs

Group module for all codec-related manipulations
module collection

core :: collection

This module define several collection classes.
module core

core :: core

Standard classes and methods used by default by Nit programs and libraries.
module environ

core :: environ

Access to the environment variables of the process
module error

core :: error

Standard error-management infrastructure.
module exec

core :: exec

Invocation and management of operating system sub-processes.
module file

core :: file

File manipulations (create, read, write, etc.)
module fixed_ints

core :: fixed_ints

Basic integers of fixed-precision
module fixed_ints_text

core :: fixed_ints_text

Text services to complement fixed_ints
module flat

core :: flat

All the array-based text representations
module gc

core :: gc

Access to the Nit internal garbage collection mechanism
module hash_collection

core :: hash_collection

Introduce HashMap and HashSet.
module iso8859_1

core :: iso8859_1

Codec for ISO8859-1 I/O
module kernel

core :: kernel

Most basic classes and methods.
module list

core :: list

This module handle double linked lists
module math

core :: math

Mathematical operations
module native

core :: native

Native structures for text and bytes
module numeric

core :: numeric

Advanced services for Numeric types
module protocol

core :: protocol

module queue

core :: queue

Queuing data structures and wrappers
module range

core :: range

Module for range of discrete objects.
module re

core :: re

Regular expression support for all services based on Pattern
module ropes

core :: ropes

Tree-based representation of a String.
module sorter

core :: sorter

This module contains classes used to compare things and sorts arrays.
module stream

core :: stream

Input and output streams of characters
module text

core :: text

All the classes and methods related to the manipulation of text entities
module time

core :: time

Management of time and dates
module union_find

core :: union_find

union–find algorithm using an efficient disjoint-set data structure
module utf8

core :: utf8

Codec for UTF-8 I/O

Parents

module digraph

graph :: digraph

Implementation of directed graphs, also called digraphs.

Children

module a_star-m

a_star-m

# Add PageRank computation for vertices in Digraph.
module pagerank

import digraph

redef class Digraph[V]

	# Compute PageRank for each vertex
	#
	# Details of the algorithm can be found in:
	# > L. Page, S. Brin, R. Motwani, and T.Winograd.
	# > **The pagerank citation ranking: Bringing order to the web.**
	# > *Technical report, Stanford Digital Library Technologies Project, 1998*
	#
	# Example:
	# ~~~
	# var g = new HashDigraph[String]
	# g.add_arc("A", "B")
	# g.add_arc("A", "C")
	# g.add_arc("B", "C")
	# g.add_arc("C", "A")
	# g.add_arc("D", "C")
	#
	# assert g.pagerank.join(", ", ":") == "A:1.488, B:0.782, C:1.575, D:0.15"
	# ~~~
	fun pagerank: PRMap[V] do
		# `d` constant such as `initial_pagerank(node) == (1 - d) != 0`
		var d = 0.85 # commonly-choosen value
		# Init each node page rank with an initial_value
		var values = new PRMap[V]
		var vertices = self.vertices
		for v in vertices do values[v] = 1.0 - d
		# Compute page rank until convergence
		var prev = new PRMap[V]
		while not values.is_approx(prev, 0.001) do
			prev = new PRMap[V].from(values)
			for v in vertices do
				var in_pr = 0.0
				for o in predecessors(v) do
					in_pr += values[o] / out_degree(o).to_f
				end
				values[v] = (1.0 - d) + d * in_pr
			end
		end
		return values
	end
end

# Map each Vertice of a Digraph to it's PageRank.
#
# See: `Digraph::pagerank`.
class PRMap[V]
	super HashMap[V, Float]

	# Init `self` by copying `other` values.
	init from(other: PRMap[V]) do
		init
		for k, v in other do self[k] = v
	end

	# Is `self` approximately equal to another PRMap?
	#
	# `self` is approximately equal to `o` if `o` contains all the key from `self`
	# with the same values.
	#
	# Values equality is based on `Float::is_approx` with `precision`.
	fun is_approx(o: SELF, precision: Float): Bool do
		for k1, v1 in self do
			if not o.has_key(k1) then return false
			if not v1.is_approx(o[k1], precision) then return false
		end
		return true
	end
end
lib/graph/pagerank.nit:15,1--88,3