package colibri2

  1. Overview
  2. Docs

Weak topological orderings (WTOs) are a hierarchical decomposition of the a graph where each layer is topologically ordered and strongly connected components are aggregated and ordered recursively. This is a very convenient representation to describe an evaluation order to reach a fixpoint.

type 'n component =
  1. | Component of 'n * 'n partition
    (*

    A strongly connected component, described by its head node and the remaining sub-components topologically ordered

    *)
  2. | Node of 'n
    (*

    A single node without self loop

    *)

Each component of the graph is either an individual node of the graph (without) self loop, or a strongly connected component where a node is designed as the head of the component and the remaining nodes are given by a list of components topologically ordered.

and 'n partition = 'n component list

A list of strongly connected components, sorted topologically

val pp_partition : 'n Fmt.t -> 'n partition Fmt.t
val pp_component : 'n Fmt.t -> 'n component Fmt.t
val flatten : 'n partition -> 'n list
val fold_heads : ('a -> 'n -> 'a) -> 'a -> 'n partition -> 'a
module Make (Node : sig ... end) : sig ... end

This functor provides the partitioning algorithm constructing a WTO.

OCaml

Innovation. Community. Security.