# Functor Traverse.Dfs

    module Dfs: functor (G : G) -> sig .. end

Depth-first search

Parameters:

`G` | : | `G`

## Classical big-step iterators

    val iter : ?pre:(G.V.t -> unit) -> ?post:(G.V.t -> unit) -> Traverse.G.t -> unit

`iter pre post g` visits all nodes of `g` in depth-first search, applying `pre` to each visited node before its successors, and `post` after them. Each node is visited exactly once. Not tail-recursive.

    val prefix : (G.V.t -> unit) -> Traverse.G.t -> unit

applies only a prefix function; note that this function is more efficient than `iter` and is tail-recursive.

    val postfix : (G.V.t -> unit) -> Traverse.G.t -> unit

applies only a postfix function. Not tail-recursive.
Same thing, but for a single connected component (only `prefix_component` is tail-recursive)

    val iter_component : ?pre:(G.V.t -> unit) ->
           ?post:(G.V.t -> unit) -> Traverse.G.t -> G.V.t -> unit

    val prefix_component : (G.V.t -> unit) -> Traverse.G.t -> G.V.t -> unit

    val postfix_component : (G.V.t -> unit) -> Traverse.G.t -> G.V.t -> unit

## Step-by-step iterator

This is a variant of the iterators above where you can move on step by step. The abstract type `iterator` represents the current state of the iteration. The `step` function returns the next state. In each state, function `get` returns the currently visited vertex. On the final state both `get` and `step` raises exception `Exit`.

Note: the iterator type is persistent (i.e. is not modified by the `step` function) and thus can be used in backtracking algorithms.

    type iterator

(h, st, g) where h is the set of marked vertices and st the stack invariant: the first element of st is not in h i.e. to be visited

    val start : Traverse.G.t -> iterator

    val step : iterator -> iterator

    val get : iterator -> G.V.t

## Cycle detection

    val has_cycle : Traverse.G.t -> bool

`has_cycle g` checks for a cycle in `g`. Linear in time and space.