StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
18793266
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-09-13T18:52:22.993
FavoriteCount
0
LastActivityDate
2013-09-13T18:52:22.993
LastEditDate
LastEditorUserId
0
OwnerUserId
1377097
ParentId
18743919
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
If you represent your graph as an adjacency list (rather than an adjacency matrix), you can make use of the fact that your graph has only 600,000 edges to hopefully reduce the computation time. Let's take a node <code>V[j]</code> with neighbors <code>V[i]</code> and <code>V[k]</code>: <pre><code>V[i] ---- V[j] ---- V[k] </code></pre> To find all such pairs of neighbors you can take the list of nodes adjacent to <code>V[j]</code> and find all combinations of those nodes. To avoid duplicates you will have to generate the combinations rather than the permutations of the end nodes <code>V[i]</code> and <code>V[k]</code> by requiring that <code>i < k</code>. Alternatively, you can start with node <code>V[i]</code> and find all of the nodes that have a distance of 2 from <code>V[i]</code>. Let <code>S</code> be the set of all the nodes adjacent to <code>V[i]</code>. For each node <code>V[j]</code> in <code>S</code>, create a path <code>V[i]-V[j]-V[k]</code> where: <ol> <li><code>V[k]</code> is adjacent to <code>V[j]</code></li> <li><code>V[k]</code> is not an element of <code>S</code> (to avoid directly connected nodes)</li> <li><code>k != i</code> (to avoid cycles)</li> <li><code>k > i</code> (to avoid duplications)</li> </ol> I personally like this approach better because it completes the adjacency list for one node before moving on to the next. Given that you have ~600,000 edges in a graph with ~100,000 nodes, assuming an even distribution of edges across all of the nodes each node would have an average degree of 12. The number of possible paths for each node is then on the order of 102. Over 105 nodes that gives on the order of 107 total paths rather than the theoretical limit of 1010 for a complete graph. Still a large number, but a thousand times faster than before.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POBest algorthm to get all combination pair of nodes in an undirected graph (need to improve time complexity)
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USbeaker
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POBest algorthm to get all combination pair of nodes in an undirected graph (need to improve time complexity)
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
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.