Talk:Topological sort: Difference between revisions
→Task Name?: Rename lots of other pages too? |
→Task Name?: no need to change anything, it is different |
||
Line 148:
:I guess we could re-name all the 'Sorting algorithms/*' to 'Sort/Magnitude/Algorithms/*' then this could slot in as 'Sort/Topological' (as we don't specify any algorithms). See [[wp:Sorting]]. (I used the word magnitude rather than their use of the word intensity). Then again, we could just leave the 'Sorting algorithms/*' as they are. --[[User:Paddy3118|Paddy3118]] 17:46, 10 August 2011 (UTC)
: All other sorts require full ordering, that is for any two elements a and b, the comparison a < b or a <= b is meaningful. Topological sort has only partial ordering: if a depends on c and b depends on d, and there are no other dependencies, a < b or a < d doesn't have to be defined: dbca, dcba, cadb, etc are all valid result. It's really quite different. --[[User:Ledrug|Ledrug]] 18:55, 10 August 2011 (UTC)
|
Revision as of 18:55, 10 August 2011
J implementation
first 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 boxed list of words. Each word is a boxed 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.
For the example data, the temporary variable names
gets the value:
┌──────────────┬────┬────┬────┬────┬────┬────┬────┬─────┬─────┬──────┬────────────┬────────┐ │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. Or, if the text is fixed width but the line drawing characters are mis-aligned, you might try using a different fixed width font in your browser.)
- (There are other problems with using the box characters too, such as the extra space between lines. If it's just illustrative, try a mediawiki table instead. –Donal Fellows 22:45, 1 March 2010 (UTC))
The result of names e.S:1 parsed
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 (> =@i.@#)
, 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 (+. +./ .*.~)^:_
, 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
The above 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
- I look forward to when you distill this into the J solution. (Maybe provide it twice, once in expanded form with annotations?) —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 names i.L:1 parsed
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 (-.L:0"_1 #,.i.@#)
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 (~.@,&.> ;@:{L:0 1~)^:_
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.)
Rdm 15:48, 2 September 2009 (UTC)
- J for a Py Guy --Paddy3118 17:37, 2 September 2009 (UTC)
Note: Roger Hui has pointed out that, in the version of J I am using (version 6.02a), the expression ;@:{L:0 1~
is slow on large data sets (for example: trees with 2e5 nodes). For now, a faster (but more obscure) implementation of the same algorithm is 3 : '(*c) #^:_1 (I.c) <@;/. (;y){y [ c=. #&> y'
. In both cases, we are finding the grandchildren which correspond to the current children. Rdm 18:21, 2 September 2009 (UTC)
Clojure example
I don't know much about Clojure, but I did notice that most of its section's leader description describes the role of code in the example. Could someone migrate that description appropriately into comments within the code sample? --Michael Mol 18:02, 25 March 2010 (UTC)
Task Name?
As far as I see, all the Sorting tasks with the exception of the Topological Sort and Topological sort/Extracted top item start with "Sort ...". or "Sorting algorithm". Would it not be better for consistency to rename these two.--Dgamey 11:35, 10 August 2011 (UTC)
"Sort topologically"? Yeuch! I would hate to put the word topologically in a title. Maybe "Sort/Topological sort"? --Paddy3118 12:27, 10 August 2011 (UTC)
- Sort/Topological? --Michael Mol 14:08, 10 August 2011 (UTC)
- All of the "Sorting algorithms", like Sorting algorithms/Insertion sort, can sort a list of numbers. "Topological sort" cannot sort a list of numbers, therefore it belongs not with the "Sorting algorithms", and retains its page name "Topological sort". --Kernigh 15:20, 10 August 2011 (UTC)
- You can sort numbers using topological sort. A trivial example of course would be to sort them based on a "less than" or "greater than" relationship. However, you can use other relationships, such as "is a factor of" or "is a product of" or "is a hailstone predecessor of" or whatever else... That said, this task is not just about sorting, but also about putting things into buckets. And that, I think, is a good reason for keeping this task separate from the other Sorting algorithms tasks. --Rdm 15:32, 10 August 2011 (UTC)
- Also this doesn't seem to have an algorithm. It's more like a class of sorts (like comparison sorts). The class of items that it can sort shouldn't matter for including it under Sorting algorithms, but the fact that it's not an algorithm should. --Mwn3d 15:25, 10 August 2011 (UTC)
- I guess we could re-name all the 'Sorting algorithms/*' to 'Sort/Magnitude/Algorithms/*' then this could slot in as 'Sort/Topological' (as we don't specify any algorithms). See wp:Sorting. (I used the word magnitude rather than their use of the word intensity). Then again, we could just leave the 'Sorting algorithms/*' as they are. --Paddy3118 17:46, 10 August 2011 (UTC)
- All other sorts require full ordering, that is for any two elements a and b, the comparison a < b or a <= b is meaningful. Topological sort has only partial ordering: if a depends on c and b depends on d, and there are no other dependencies, a < b or a < d doesn't have to be defined: dbca, dcba, cadb, etc are all valid result. It's really quite different. --Ledrug 18:55, 10 August 2011 (UTC)