A partitioning is minimal provided each vertex appears in the level immediately after the one with its last appearing component.
Every directed acyclic graph (DAG) has a set of vertices with VertexInDegree
equal to zero, called "sources"; the sources of the DAG are listed in the base level (or stratum) of the minimal stratification.
Subsequent vertices are listed in the next stratum as soon as all of their inputs are included in preceding strata. Consequently, directed edges always point from an earlier stratum to a later one.
There is an equally minimal reverse stratification obtained by applying time reversal to the input graph. Vertices with VertexOutDegree
equal zero (called “sinks”) then form the base stratum. Subsequent strata membership is determined treating sinks as sources and moving reversely along directed edges.
If the forward and reverse stratifications are identical, the graph is said to be stratification-rigid.
Every graph contains a stratification-rigid subgraph, which determines a stratification axis and a minimal length thereof.
If the graph is not entirely stratification-rigid, alternative stratifications can be obtained by perturbing "loose" vertices forward along the stratification axis.
Since the stratification axis has a fixed length, the number of possible stratifications must be finite.
The optional parameter n effectively lengthens the stratification axis, thus allowing enumeration of additional "extra-loose" stratifications.
Depending how large the non-stratification-rigid subgraph is, it may be necessary to introduce a cutoff max to force halting in reasonable time.