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.
Partition the nodes of a directed graph into groups and sort these
groups such that all edges going from one group to another
point to the right, and such that each group
has a single element or is a cycle. A cyclic group is marked
as true
while non-cyclic singletons are marked as false
.
A cycle is a set of nodes such that any node of the set can be reached from any other node of that set.
All groups of more than one node are cyclic. Groups of one node may or may not be cyclic.