StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFind all subtrees of size N in an undirected graph
text
Body
copied!<p>Given an undirected graph, I want to generate all subgraphs which are trees of size N, where <em>size</em> refers to the number of edges in the tree.</p> <p>I am aware that there are a lot of them (exponentially many at least for graphs with constant connectivity) - but that's fine, as I believe the number of nodes and edges makes this tractable for at least smallish values of N (say 10 or less).</p> <p>The algorithm should be memory-efficient - that is, it shouldn't need to have all graphs or some large subset of them in memory at once, since this is likely to exceed available memory even for relatively small graphs. So something like DFS is desirable.</p> <p>Here's what I'm thinking, in pseudo-code, given the starting graph <code>graph</code> and desired length <code>N</code>:</p> <p>Pick any arbitrary node, <code>root</code> as a starting point and call <code>alltrees(graph, N, root)</code></p> <pre><code>alltrees(graph, N, root) given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think) for each tuple (X1, X2, ... XM) above create a subgraph "current" initially empty for each integer Xi in X1...XM (the current tuple) if Xi is nonzero add edge i incident on root to the current tree add alltrees(graph with root removed, N-1, node adjacent to root along edge i) add the current tree to the set of all trees return the set of all trees </code></pre> <p>This finds only trees containing the chosen initial root, so now remove this node and call alltrees(graph with root removed, N, new arbitrarily chosen root), and repeat until the size of the remaining graph < N (since no trees of the required size will exist).</p> <p>I forgot also that each visited node (each root for some call of alltrees) needs to be marked, and the set of children considered above should only be the adjacent unmarked children. I guess we need to account for the case where no unmarked children exist, yet depth > 0, this means that this "branch" failed to reach the required depth, and cannot form part of the solution set (so the whole inner loop associated with that tuple can be aborted).</p> <p>So will this work? Any major flaws? Any simpler/known/canonical way to do this?</p> <p>One issue with the algorithm outlined above is that it doesn't satisfy the memory-efficient requirement, as the recursion will hold large sets of trees in memory.</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