Talk:Topological sort: Difference between revisions
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: | 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. |
<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 (> =@i.@#) 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>(> =@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 (+. +./ .*.~)^:_ performs transitive closure on a connection matrix. |
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. |
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. |
Revision as of 20:09, 1 September 2009
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 depends=. (> =@i.@#) names e.S:1 parsed depends=. (+. +./ .*.~)^:_ depends assert.-.1 e. (<0 1)|:depends (-.&names ~.;parsed),names /: +/"1 depends
)</lang>
parsed
is a list of lines. Each line is a list of words. Each word is a list of characters.
names
is the first word extracted from each line.
depends
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 (> =@i.@#)
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 (+. +./ .*.~)^:_
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.
Finally, we sort the names so that names with fewer dependencies are followed by names with more dependencies. And, we prepend any names which we depend on which would otherwise have no dependencies.
This implementation is a bit naive, since a connection matrix is O(n^2) in space and O(n^3) in time for n dependencies. If this matters, I should probably rewrite the code (and these comments) to use the tree structure mentioned at http://www.jsoftware.com/jwiki/Essays/Tree%20Sum#Descendants