utils/it.unibo.tuprolog.utils.graphs/DepthFirst

DepthFirst

class DepthFirst<T, W>(maxDepth: Int = -1, postOrder: Boolean = false) : AbstractSearchStrategy<T, W, Int>

A SearchStrategy visiting a Graph depth-first: from the source, it follows one outgoing edge as deep as possible before backtracking to explore the next one. Each yielded Visit.state is the depth (an Int, starting at 0) at which the corresponding node was reached.

graph.asSequence(DepthFirst(), 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"

postOrder

if true (false by default), a node is yielded only after all the nodes reachable from it have been (post-order traversal), rather than as soon as it is first reached (pre-order traversal)

Constructors

DepthFirst

constructor(maxDepth: Int = -1, postOrder: Boolean = false)

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.