shortestpath

Documentation

Index

• type Calculator
  • func NewCalculator(numWorkers int) (*Calculator, error)
  • func (c *Calculator) AddEdge(srcID, dstID string, cost int) error
  • func (c *Calculator) AddVertex(id string)
  • func (c *Calculator) CalculateShortestPaths(ctx context.Context, srcID string) error
  • func (c *Calculator) Close() error
  • func (c *Calculator) SetExecutorFactory(factory bspgraph.ExecutorFactory)
  • func (c *Calculator) ShortestPathTo(dstID string) ([]string, int, error)
• type PathCostMessage
  • func (pc PathCostMessage) Type() string

Types

type Calculator

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

Calculator implements a shortest path calculator from a single vertex to all other vertices in a connected graph.

func NewCalculator

func NewCalculator(numWorkers int) (*Calculator, error)

NewCalculator returns a new shortest path calculator instance.

func (*Calculator) AddEdge

func (c *Calculator) AddEdge(srcID, dstID string, cost int) error

AddEdge creates a directed edge from srcID to dstID with the specified cost. An error will be returned if a negative cost value is specified.

func (*Calculator) AddVertex

func (c *Calculator) AddVertex(id string)

AddVertex inserts a new vertex with the specified ID into the graph.

func (*Calculator) CalculateShortestPaths

func (c *Calculator) CalculateShortestPaths(ctx context.Context, srcID string) error

CalculateShortestPaths finds the shortest path costs from srcID to all other vertices in the graph.

func (*Calculator) Close

func (c *Calculator) Close() error

Close cleans up any allocated graph resources.

func (*Calculator) SetExecutorFactory

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

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

func (*Calculator) ShortestPathTo

func (c *Calculator) ShortestPathTo(dstID string) ([]string, int, error)

ShortestPathTo returns the shortest path from the source vertex to the specified destination together with its cost.

type PathCostMessage

type PathCostMessage struct {
	// The ID of the vertex this cost announcement originates from.
	FromID string

	// The cost of the path from this vertex to the source vertex via FromID.
	Cost int
}

PathCostMessage is used to advertise the cost of a path through a vertex.

func (PathCostMessage) Type

func (pc PathCostMessage) Type() string

Type returns the type of this message.