utils/it.unibo.tuprolog.utils.graphs/BreadthFirst

BreadthFirst

class BreadthFirst<T, W>(maxDepth: Int = -1) : AbstractSearchStrategy<T, W, Int>

A SearchStrategy visiting a Graph breadth-first, i.e. level by level: all nodes at depth 0 (the source), then all nodes at depth 1, and so on. Each yielded Visit.state is the depth (an Int, starting at 0) at which the corresponding node was reached.

graph.asSequence(BreadthFirst(), sourceNode).forEach { (depth, node) -> println("$node at depth $depth") }

Parameters

maxDepth

caps the traversal to nodes at depth at most maxDepth; a non-positive value (the default, -1) means "unbounded"

Constructors

BreadthFirst

constructor(maxDepth: Int = -1)

Properties

initialState

open override val initialState: Int

Functions

override fun search(graph: Graph<T, W>, source: Node<T>): Sequence<Visit<T, Int>>

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