package atd

  1. Overview
  2. Docs

Topological sort that doesn't give up on cycles.

     A --> B
     C --> D
     B --> C
     C --> B
     D --> E
     E --> E

gives the following ordering:

     [A] [B C]* [D] [E]*

where a group marked with a star is cyclic, i.e any member of the group can be reached from any other member of that group.

This is used by atdgen to sort type definitions by dependency order, creating recursive groups only when needed. This makes ocamlopt significantly faster in certain pathological situations. Also it improves the clarity of the generated code and can be used to report cycles in a context where they are not allowed.

Feel free to reuse outside of atdgen. The algorithm is outlined in the ml file. The interface of this module may change without notice.

module type Param = sig ... end
module Make (P : Param) : sig ... end