visitor
API
Generated with
visitor/com.phasmidsoftware.visitor/com.phasmidsoftware.visitor.core/CostUpdate

CostUpdate

com.phasmidsoftware.visitor.core.CostUpdate
trait CostUpdate[W, F[_]]

Typeclass: after a node is settled (dequeued and marked visited) and its neighbours have been offered to the frontier, optionally update the priorities of frontier entries that have improved.

This typeclass exists to support decreaseKey in Dijkstra- and Prim-style traversals. It keeps all domain knowledge (cost maps, edge weights, the notion of "improvement") out of Traversal itself.

For DFS and BFS the default no-op given is resolved automatically. For Dijkstra and Prim, the GraphTraversal implementation supplies a concrete given CostUpdate[W, IndexedPrioQueue] (where W = (E, V)) that closes over a secondary vertex→cost map and calls IndexedPrioQueue.decreaseKey for any neighbour whose cost has improved since it was first offered.

Type parameters

F

the frontier container type (e.g. PrioQueue, Stack, Queue)

W

the frontier element type (e.g. (E, V) for weighted traversals, or plain V for DFS / BFS)

Attributes

Graph
Supertypes
class Object
trait Matchable
class Any

Members list

Value members

Abstract methods

def update(frontier: F[W], w: W): F[W]

Given the current frontier and the node w that was just settled, return an updated frontier with any improved priorities applied.

Given the current frontier and the node w that was just settled, return an updated frontier with any improved priorities applied.

Value parameters

frontier

the frontier after w's neighbours have been offered

w

the element that was just settled

Attributes

Returns

the frontier with any decreaseKey updates applied

Generated with