Weak topological ordering is an extension of topological ordering for potentially cyclic graphs.
A hierarchical ordering of a set is a well-parenthesized
permutation of its elements with no consecutive
(. The elements
between two parentheses are called a component, and the first
elements of a component is called the head. A weak topological
ordering of a graph is a hierarchical ordering of its vertices
such that for every edge
u -> v of the graph, either
v is the head of a component
One may notice that :
v1, ..., vN, the following trivial weak topological ordering is valid :
(v1 (v2 (... (vN))...)).
ChaoticIteration). This module aims at computing weak topological orderings which improve the precision and the convergence speed of these analyses.
module type G =
Vertex vrepresents a single vertex.
Component (head, cs)is a component of the wto, that is a sequence of elements between two parentheses.
headis the head of the component, that is the first element, which is guaranteed to be a vertex by definition.
csis the rest of the component.
val fold_left :
('a -> 'b element -> 'a) -> 'a -> 'b t -> 'a
Note that as
elements present in an ordering of type
contain values of type
t itself due to the
this function should be used by defining a recursive function
which will call
f used to define the first