StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem is exactly the computation of the connected components of an hypergraph: the integers are the vertices, and the sets are the hyperedges. A usual way of computing the connected components is by flooding them one after the other:</p> <ul> <li>for all i = 1 to N, do:</li> <li>if i has been tagged by some j < i, then continue (I mean skip to the next i)</li> <li>else flood_from(i,i)</li> </ul> <p>where flood_from(i,j) would be defined as</p> <ul> <li>for each set S containing i, if it is not already tagged by j then:</li> <li>tag S by j and for each element k of S, if k is not already tagged by j, then tag it by j, and call flood_from(k,j)</li> </ul> <p>The tags of the sets then give you the connected components you are looking for. </p> <hr> <p>In terms of databases, the algorithm can be expressed as follows: you add a TAG column to your database, and you compute the connected component of set i by doing</p> <ul> <li>S = select all rows where set_id == i</li> <li>set TAG to i for the rows in S </li> <li>S' = select all rows where TAG is not set and where element is in element(S)</li> <li>while S' is not empty, do</li> <li>---- set TAG to i for the rows in S'</li> <li>---- S'' = select all rows where TAG is not set and where element is in element(S')</li> <li>---- S = S union S'</li> <li>---- S' = S''</li> <li>return set_id(S)</li> </ul> <hr> <p>Another (theoretical) way of presenting this algorithm would be to say that you are looking for the fixed points of a mapping:</p> <ul> <li>if A = {A<sub>1</sub>, ..., A<sub>n</sub>} is a set of sets, define union(A) = A<sub>1</sub> union ... union A<sub>n</sub></li> <li>if K = {k<sub>1</sub>, ..., k<sub>p</sub>} is a set of integers, define incidences(K) = the set of sets which intersect K</li> </ul> <p>Then if S is a set, the connected component of S is obtained by iterating (incidences)o(union) on S until a fixed point is reached:</p> <ol> <li>K = S</li> <li>K' = incidences(union(K)). </li> <li>if K == K', then return K, else K = K' and go to 2.</li> </ol>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload