[LRUG] Pruning a tree

[Andrew Stewart]

On 27 Jun 2011, at 17:52, Paul Robinson wrote:
> Before you start the merging of hashes, what tree/graph traversal algorithm are you using in the first place?

I start with an array of the identified nodes: [n0, n1, n2, ...], each of which comes from anywhere in the tree.

I map each node into an array holding its path to the root.  E.g. n0 maps to [n0, n42, n153, root].

I then try to combine my array of arrays to get the result I want.

Each node is a record in a database with a parent_id column pointing to its parent.  I use ActiveRecord like this:

    class Node < ActiveRecord::Base
      has_many :children, :class_name => 'Node', :foreign_key => 'parent_id'
      belongs_to :parent, :class_name => 'Node'

      def ancestors
        n = self
        out = [n]
        until n.id == 1  # root
          n = n.parent
          out << n
        end
        out
      end
    end

I'm not using ancestry or other tree gems.

Yours,
Andy

-------
http://airbladesoftware.com