id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	revision
421	Better DAG test and topological ordering implementation	Alpar Juttner	Alpar Juttner	"Currently all these functions use Dfs with a custom visitor. I have a feeling that a direct algorithm might be faster and/or more memory efficient. The algorithm I propose is the following:

 - Compute the in-degree of all nodes and store them in a `NodeMap` `deg`.
 - Put all node `n` with `deg[n]==0` into a queue (or a stack) `q`.
 - While `q` is not empty:
   - Get a node `n` from `q`. This is the next node in the topological order.
   - For each out-arc `a` of `n`:
     - Decrease `deg[target(a)]` by 1
     - If `deg[target(a)]==0` then put `target(a)` into `q`
"	enhancement	new	major	LEMON 1.4 release	core	hg main