Talk:Topological sort: Difference between revisions
no edit summary
No edit summary |
|||
Line 1:
==J implementation==
===first implementation===
These are brief notes, and do not attempt to document the language itself.
Line 26 ⟶ 28:
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.
For the example data, the temporary variable <code>names</code> gets the value:
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▼
┌──────────────┬────┬────┬────┬────┬────┬────┬────┬─────┬─────┬──────┬────────────┬────────┐
│des_system_lib│dw01│dw02│dw03│dw04│dw05│dw06│dw07│dware│gtech│ramlib│std_cell_lib│synopsys│
└──────────────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴──────┴────────────┴────────┘
(Note: this is meant to be viewed in a fixed width font, and the non-alphabetic decorating characters are meant to be line drawing characters. If you are not seeing this, and you want to, you might try using a different browser.)
The result of <code>names e.S:1 parsed</code> is then:
1 1 1 0 0 0 0 0 0 0 1 1 1
0 1 0 0 0 0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0
0 1 1 1 0 0 0 0 1 1 0 0 1
0 1 0 0 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1
In other words, rows and columns both correspond to names, and a value is 1 if the name for that row depends on the name for that column. We next clean up the diagonal, using the phrase <code>(> =@i.@#)</code>, yielding:
0 1 1 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 1 1 0 0 1
0 1 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
And, we then perform a transitive closure (if a name1 depends on name2 and name2 depends on name3, then name1 depends on name3), using the phrase <code>(+. +./ .*.~)^:_</code>, which yields:
0 1 1 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 1 1 0 0 1
0 1 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
Finally, we sum each row, and sort the names in order by their dependency count.
===alternate implementation===
▲
: I look forward to when you distill this into the J solution. (Maybe provide it twice, once in expanded form with annotations?) —[[User:Dkf|Donal Fellows]] 22:18, 1 September 2009 (UTC)
Here's that alternate implementation. The algorithm remains unchanged -- I have just represented the dependencies using a different data structure.
<lang J>depSort=: monad define
parsed=. <@;:;._2 y
names=. {.&>parsed
depends=. (-.L:0"_1 #,.i.@#) names i.L:1 parsed
depends=. (~.@,&.> ;@:{L:0 1~)^:_ depends
assert.-.1 e. (i.@# e.S:0"0 ])depends
(-.&names ~.;parsed),names /: #@> depends
)</lang>
In other words, instead of using a connection matrix, we use lists of name indices. In other words, the result of <code>names i.L:1 parsed</code> is
┌──────────────────────┬──────────┬────────┬────────────────────┬────────────┬────────┬────────┬──────┬──────┬──────┬────────┬────────┬──┐
│0 13 12 11 0 2 1 10 13│1 13 1 8 9│2 13 2 8│3 13 12 8 3 2 1 13 9│4 4 13 1 8 9│5 5 13 8│6 6 13 8│7 13 8│8 13 8│9 13 9│10 13 13│11 13 11│12│
└──────────────────────┴──────────┴────────┴────────────────────┴────────────┴────────┴────────┴──────┴──────┴──────┴────────┴────────┴──┘
(and, once again, my apologies if your browser does not render this properly.)
As before, we need to remove cases where a name depends on itself. But, here, we also need to remove dependencies on names which are not in our names list. After we use the phrase <code>(-.L:0"_1 #,.i.@#)</code> our cleaned up dependency list looks like this:
┌────────────┬───┬─┬──────────┬─────┬─┬─┬─┬┬┬┬┬┐
│12 11 2 1 10│8 9│8│12 8 2 1 9│1 8 9│8│8│8││││││
└────────────┴───┴─┴──────────┴─────┴─┴─┴─┴┴┴┴┴┘
We then use the phrase <code>(~.@,&.> ;@:{L:0 1~)^:_</code> to get our transitive closure:
┌────────────────┬───┬─┬──────────┬─────┬─┬─┬─┬┬┬┬┬┐
│12 11 2 1 10 8 9│8 9│8│12 8 2 1 9│1 8 9│8│8│8││││││
└────────────────┴───┴─┴──────────┴─────┴─┴─┴─┴┴┴┴┴┘
If I have been too brief on some subject, please feel free to ask questions. (I could, hypothetically, expand this discussion out into a tutorial on the J language, but I have already done something like that on a few rosetta code pages and that sort of thing gets tiring after a while -- especially when I do not get any feedback from the audience about their interests. Also I do not want to be spending too much time boring people who do not care at all about J.)
| |||