Added GTOP SSSP algorithm for computing epsilon-closure with POSIX disambiguation.
GTOP SSSP meand "Global Topsort Single Source Shortes Path".
It is well known that SSSP can be solved in linear time on DAGs (directed
acyclic graphs) by exploring graph nodes in topological order. In our case
TNFA is not a DAG (it may have cycles), but it is possible to compute fake
topologcal order by ignoring back edges.
The algorithm works by having a priority queue of nodes, where priorities
are indices of nodes in fake topological ordering. At each step, the node
with the minimal priority is popped from queue and explored. All nodes
reachable from it on admissible arcs are enqueued, unless they are already
on queue.
The resulting algorithm is of course not optimal: it can get stuck on
graphs with loops, because it will give priority to some of the loop nodes
compared to others for no good reason.
However the algorithm is simple and optimal for DAGs, therefore we keep it.
projects / re2c / commit