StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POPartial order sorting?
primarykey
Id
4620100
data
AcceptedAnswerId
4620227
AnswerCount
1
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2011-01-06T21:32:18.603
FavoriteCount
1
LastActivityDate
2011-01-08T04:29:50.133
LastEditDate
2011-01-08T04:29:50.133
LastEditorUserId
134904
OwnerUserId
134904
ParentId
0
PostTypeId
1
Score
13
ViewCount
3704
LastEditorDisplayName
text
Body
Say, we have some items, and each defines some partial sorting rules, like this: <blockquote> I'm <code>A</code> and I want to be before <code>B</code> I'm <code>C</code> and I want to be after <code>A</code> but before <code>D</code> </blockquote> So we have items <code>A,B,C,D</code> with these rules: <ul> <li><code>A>B</code></li> <li><code>C<A</code>, <code>C>D</code></li> <li>nothing else! So, <code>B</code> and <code>D</code> have no 'preferences' in ordering and are considered equal.</li> </ul> As you see, transitive relation rules are not working here. However, if <code>A>B</code> it still means that <code>B<A</code>. So, there can be multiple possible results of sorting: <ol> <li>A B C D</li> <li>A C D B</li> <li>A C B D</li> <li>A B C D</li> </ol> How can I implement a sorting algorithm that handles such a situation? <hr> The reason: there're multiple loadable modules, and some of them 'depend' on others in a way. Each module can declare simple rules, relative to other modules: <blockquote> Load me before module A Load me after module B Load me before module A but after module B </blockquote> now I need to implement this ordering somehow.. :) <hr> Answer: <a href="http://code.activestate.com/recipes/577413-topological-sort/" rel="noreferrer">code</a> by Paddy McCarthy (MIT) <pre><code>## {{{ http://code.activestate.com/recipes/577413/ (r1) try: from functools import reduce except: pass data = { 'des_system_lib': set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()), 'dw01': set('ieee dw01 dware gtech'.split()), 'dw02': set('ieee dw02 dware'.split()), 'dw03': set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()), 'dw04': set('dw04 ieee dw01 dware gtech'.split()), 'dw05': set('dw05 ieee dware'.split()), 'dw06': set('dw06 ieee dware'.split()), 'dw07': set('ieee dware'.split()), 'dware': set('ieee dware'.split()), 'gtech': set('ieee gtech'.split()), 'ramlib': set('std ieee'.split()), 'std_cell_lib': set('ieee std_cell_lib'.split()), 'synopsys': set(), } def toposort2(data): for k, v in data.items(): v.discard(k) # Ignore self dependencies extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys()) data.update({item:set() for item in extra_items_in_deps}) while True: ordered = set(item for item,dep in data.items() if not dep) if not ordered: break yield ' '.join(sorted(ordered)) data = {item: (dep - ordered) for item,dep in data.items() if item not in ordered} assert not data, "A cyclic dependency exists amongst %r" % data print ('\n'.join( toposort2(data) )) ## end of http://code.activestate.com/recipes/577413/ }}} </code></pre>
Tags
<python><algorithm><topological-sort>
Title
Partial order sorting?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USkolypto
UserOwnerUserId
1. USkolypto
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POPartial order sorting?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POPartial order sorting?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 POPartial order sorting?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.