AbstractSearchStrategy

abstract class AbstractSearchStrategy<T, W, S>(val initialState: S) : SearchStrategy<T, W, S>

A base SearchStrategy taking care of the common bookkeeping of a graph traversal (the "fringe" of edges still to explore, and driving search as a lazy Sequence), so that concrete strategies (see BreadthFirst and DepthFirst) only need to implement selectNextVisit, deciding, at each step, which edge in the fringe to visit next and how to grow the fringe from there.

The traversal starts from a synthetic Traversal whose source is an internal placeholder node (see isInitial), so that selectNextVisit is invoked uniformly for the very first node too.

Parameters

initialState

the SearchStrategy.initialState the traversal starts from

Type Parameters

T

is the type of the payload carried by the traversed graph's nodes

W

is the type of the traversed graph's edge weights

S

is the type of the traversal-specific state threaded through the search (e.g. depth)

Inheritors

Constructors

Link copied to clipboard
constructor(initialState: S)

Properties

Link copied to clipboard
open override val initialState: S

Functions

Link copied to clipboard
override fun search(graph: Graph<T, W>, source: Node<T>): Sequence<Visit<T, S>>

Lazily traverses graph from source, repeatedly delegating to selectNextVisit to pick which fringe entry to explore next, until the fringe is empty.