pagerank

Documentation

Index

• type Calculator
  • func NewCalculator(cfg Config) (*Calculator, error)
  • func (c *Calculator) AddEdge(src, dst string) error
  • func (c *Calculator) AddVertex(id string)
  • func (c *Calculator) Close() error
  • func (c *Calculator) Executor() *bsp.Executor
  • func (c *Calculator) Graph() *bsp.Graph
  • func (c *Calculator) Scores(visitFn func(id string, score float64) error) error
  • func (c *Calculator) SetExecutorFactory(factory bsp.ExecutorFactory)
• type Config
• type GraphAPI
• type IncomingScoreMessage
  • func (pr IncomingScoreMessage) Type() string
• type IndexAPI
• type Service
  • func NewService(cfg ServiceConfig) (*Service, error)
  • func (svc *Service) Name() string
  • func (svc *Service) Run(ctx context.Context) error
• type ServiceConfig

Types

type Calculator

type Calculator struct {
	// contains filtered or unexported fields
}

Calculator executes the iterative version of the PageRank algorithm on a graph until the desired level of convergence is reached.

func NewCalculator

func NewCalculator(cfg Config) (*Calculator, error)

NewCalculator returns a new Calculator instance using the provided config options.

func (*Calculator) AddEdge

func (c *Calculator) AddEdge(src, dst string) error

AddEdge inserts a directed edge from src to dst. If both src and dst refer to the same vertex then this is a no-op.

func (*Calculator) AddVertex

func (c *Calculator) AddVertex(id string)

AddVertex inserts a new vertex to the graph with the given id.

func (*Calculator) Close

func (c *Calculator) Close() error

Close releases any resources allocated by this PageRank calculator instance.

func (*Calculator) Executor

func (c *Calculator) Executor() *bsp.Executor

Executor creates and return a bsp.Executor for running the PageRank algorithm once the graph layout has been properly set up.

func (*Calculator) Graph

func (c *Calculator) Graph() *bsp.Graph

Graph returns the underlying bsp.Graph instance.

func (*Calculator) Scores

func (c *Calculator) Scores(visitFn func(id string, score float64) error) error

Scores invokes the provided visitor function for each vertex in the graph.

func (*Calculator) SetExecutorFactory

func (c *Calculator) SetExecutorFactory(factory bsp.ExecutorFactory)

SetExecutorFactory configures the calculator to use the a custom executor factory when the Executor method is invoked.

type Config

type Config struct {
	// DampingFactor is the probability that a random surfer will click on
	// one of the outgoing links on the page they are currently visiting
	// instead of visiting (teleporting to) a random page in the graph.
	//
	// If not specified, a default value of 0.85 will be used instead.
	DampingFactor float64

	// At each step of the iterative PageRank algorithm, an accumulator
	// tracks the sum of absolute differences (SAD) of the PageRank
	// scores for each vertex in the graph.
	//
	// The algorithm will keep executing until the aggregated SAD for all
	// vertices becomes less than MinSADForConvergence.
	//
	// If not specified, a default value of 0.001 will be used instead.
	MinSADForConvergence float64

	// The number of workers to spin up for computing PageRank scores. If
	// not specified, a default value of 1 will be used instead.
	ComputeWorkers int
}

Config encapsulates the required parameters for creating a new PageRank calculator instance.

type GraphAPI

type GraphAPI interface {
	Links(fromID, toID uuid.UUID, retrievedBefore time.Time) (graph.LinkIterator, error)
	Edges(fromID, toID uuid.UUID, updatedBefore time.Time) (graph.EdgeIterator, error)
}

GraphAPI defines as set of API methods for fetching the links and edges from the link graph.

type IncomingScoreMessage

type IncomingScoreMessage struct {
	Score float64
}

IncomingScoreMessage is used for distributing PageRank scores to neighbors.

func (IncomingScoreMessage) Type

func (pr IncomingScoreMessage) Type() string

Type returns the type of this message

type IndexAPI

type IndexAPI interface {
	UpdateScore(linkID uuid.UUID, score float64) error
}

IndexAPI defines a set of API methods for updating PageRank scores for indexed documents.

type Service

type Service struct {
	// contains filtered or unexported fields
}

Service implements the PageRank calculator component for the Links 'R' Us project.

func NewService

func NewService(cfg ServiceConfig) (*Service, error)

NewService creates a new PageRank calculator service instance with the specified config.

func (*Service) Name

func (svc *Service) Name() string

Name implements service.Service

func (*Service) Run

func (svc *Service) Run(ctx context.Context) error

Run implements service.Service

type ServiceConfig

type ServiceConfig struct {
	// An API for interating links and edges from the link graph.
	GraphAPI GraphAPI

	// An API for updating the PageRank score for indexed documents.
	IndexAPI IndexAPI

	// An API for detecting the partition assignments for this service.
	PartitionDetector partition.Detector

	// A clock instance for generating time-related events. If not specified,
	// the default wall-clock will be used instead.
	Clock clock.Clock

	// The number of workers to spin up for computing PageRank scores. If
	// not specified, a default value of 1 will be used instead.
	ComputeWorkers int

	// The time between subsequent crawler passes.
	UpdateInterval time.Duration

	// The logger to use. If not defined an output-discarding logger will
	// be used instead.
	Logger *logrus.Entry
}

ServiceConfig encapsulates the settings for configuring the PageRank calculator service.