StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
16437893
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-05-08T10:05:57.570
FavoriteCount
0
LastActivityDate
2013-05-08T11:16:13.020
LastEditDate
2013-05-08T11:16:13.020
LastEditorUserId
1711796
OwnerUserId
1711796
ParentId
16436165
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
text
Body
This approach uses DFS, but is very efficient, because we don't repeat nodes in subsequent DFS's. High-level approach: Initialize the values of all the nodes to <code>-1</code>. Do a DFS from each unexplored node, setting that node's value to that of an auto-incremented value starting from <code>0</code>. For these DFS's, update each node's value with <code>previous node's value + i/n^k</code> where that node is the <code>i</code>th child of the previous node and <code>k</code> is the depth explored, skipping already explored nodes (except for checking for a bigger value). So, an example for <code>n = 10</code>: <pre><code> 0.1 0.11 0.111 j - k - p 0 / \ 0.12 i \ 0.2 l m 1 1.1 q - o ... </code></pre> You can also use <code>i/branching factor+1</code> for each node to reduce the significant digits of the numbers, but that requires additional calculation to determine. So above we did a DFS from <code>i</code>, which had 2 children <code>j</code> and <code>m</code>. <code>m</code> had no children, <code>j</code> had 2 children, .... Then we finished with <code>i</code> and started another DFS from the next unexplored node <code>q</code>. Whenever you encounter a bigger value, you know that a cycle occurred. Complexity: You check every node at most once, and at every node you do n checks, so complexity is <code>O(n^2)</code>, which is the same as looking at every entry in the matrix once (which you can't do much better than). Note: I'll also just note that an <a href="http://en.wikipedia.org/wiki/Adjacency_list" rel="nofollow">adjacency list</a> will probably be faster than an adjacency matrix unless it's a very dense graph.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. PODetecting cycles in an adjacency matrix
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USDukeling
UserOwnerUserId
1. USDukeling
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. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 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.