StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can reduce this problem to <strong>finding all connected components</strong> of an undirected graph. The vertices are your matrix rows, and edges are non-zero overlap. The <a href="http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/connected_components.html" rel="nofollow">Boost.Graph</a> library can compute this in <code>O(V+E)</code> complexity where <code>V</code> is the number vertices (matrix rows) and <code>E</code> the number of edges (number of overlapping rows). If you don't like the dependency on Boost, you can use any of the <a href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" rel="nofollow">available algorithms</a> for computing strongly connected components.</p> <p>What remains is to compute the edge-list representation of this graph, which depends on whether you are able to sort your matrix rows. If cannot sort your matrix rows, you can use <a href="http://en.cppreference.com/w/cpp/algorithm/find_first_of" rel="nofollow"><code>std::find_first_of</code></a> to detect non-zero overlap (which has <code>O(N * M)</code> complexity for 2 vectors of <code>N</code> and <code>M</code> elements). If you can sort them (in <code>O(N lg N)</code> complexity), you can use <a href="http://en.cppreference.com/w/cpp/algorithm/set_intersection" rel="nofollow"><code>std::set_intersection</code></a> to test for overlap (only <code>O(N + M)</code> complexity). </p> <p>The output of the Boost.Graph or your algorithm is a set of connected components, and you then loop over each component and append or merge the various overlapping rows of your matrix together (using <code>std::copy</code>, or <code>std::merge</code> if you need them sorted).</p>

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