Talk:Topological sort: Difference between revisions
Content deleted Content added
Created page with '==J implementation== These are brief notes, and do not attempt to document the language itself. <lang J>dependencySort=: monad define parsed=. <@;:;._2 y names=. {.&>parsed…' |
|||
Line 18:
<code>depends</code> is a connection matrix -- rows and columns correspond to names, and the values are bits -- 1 for names which depend on other names, and 0 for names which do not depend on other names.
The phrase <code>(> =@i.@#)</code> means that names are not allowed to depend on themselves (since the specification said self dependencies should be ignored, and this makes detecting circular dependencies trivial).
The phrase <code>(+. +./ .*.~)^:_</code> performs transitive closure on a connection matrix.
The assert statement checks for names which depend on themselves. Since we no know names depended on themselves before we did our transitive closure, we know we have a problem if we have any such dependencies.
|