[LRUG] Pruning a tree

[Viktor Tron]

def prune_and_sum(node,ids_to_preserve,result,counts)
   found = ids_to_preserve.delete(node.id)
   subtree_results = []
   subtree_pruned = node.children.all? do |child|
     prune_and_sum(child,ids_to_preserve,subtree_results,counts)
   end
   counts << node.count if found
   results << subtree_results.empty? node : { node => subtree_results }
   subtree_pruned && !found && node.destroy
end

# ids_to_preserve is a hash of id => true
counts = []
results = []
result prune_and_sum(root,ids_to_preserve,results,counts)
sum = counts.inject(&:+)


just quietly: are you sure your return value structure makes sense?




On Mon, 27 Jun 2011 17:32:46 +0100, Andrew Stewart  
<boss at airbladesoftware.com> wrote:

> Hola El Rug,
>
> I have a tree about 10 levels deep with ~600k nodes in all.  An offline  
> process identifies about ~100 different nodes in the tree.
>
> I would like to prune the tree such that the only nodes left are the  
> identified ones and the ones connecting them back to the root.  We  
> ignore any children of identified nodes.  Ideally the result would be a  
> hash of nested hashes/arrays.
>
> For example, given the following tree (only relevant parts shown) with  
> identified nodes a, b, d, z:
>
> root -> x -> a
> root -> x -> y -> b
> root -> x -> y -> c -> d
> root -> z
>
> I would like this result:
>
> root => [
>           {x => [
>                    a,
>                    y => [
>                           b,
>                           {c => d}
>                         ]
>                  ]
>           },
>           z
>         ]
>
> As a bonus, each identified node has a count associated with it.  I  
> would like to sum the counts along the way from the node to the root.   
> So, in the example, y's calculated count = b's + d's.
>
> My attempts have revolved around recursively merging hashes but I can't  
> seem to get it quite right...
>
> Yours,
> Andy Stewart
>
> -------
> http://airbladesoftware.com
> _______________________________________________
> Chat mailing list
> Chat at lists.lrug.org
> http://lists.lrug.org/listinfo.cgi/chat-lrug.org