package ocamlgraph

  1. Overview
  2. Docs
package ocamlgraph
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Traverse.DfsSource

Depth-first search

Parameters

module G : G

Signature

Classical big-step iterators

Sourceval iter : ?pre:(G.V.t -> unit) -> ?post:(G.V.t -> unit) -> 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.

Sourceval prefix : (G.V.t -> unit) -> G.t -> unit

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

Sourceval postfix : (G.V.t -> unit) -> 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)

Sourceval iter_component : ?pre:(G.V.t -> unit) -> ?post:(G.V.t -> unit) -> G.t -> G.V.t -> unit
Sourceval prefix_component : (G.V.t -> unit) -> G.t -> G.V.t -> unit
Sourceval postfix_component : (G.V.t -> unit) -> G.t -> G.V.t -> unit

Classical folds

Sourceval fold : (G.V.t -> 'a -> 'a) -> 'a -> G.t -> 'a

The function is applied each time a node is reached for the first time, before iterating over its successors. Tail-recursive.

Sourceval fold_component : (G.V.t -> 'a -> 'a) -> 'a -> G.t -> G.V.t -> 'a

Idem, but limited to a single root vertex.

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.

Sourcetype iterator
Sourceval start : G.t -> iterator
Sourceval step : iterator -> iterator
Sourceval get : iterator -> G.V.t

Cycle detection

Sourceval has_cycle : G.t -> bool

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

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct