How do I implement a tree shaker operation? [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

I need an operation which I call shake_tree. I have implemented it using a recursive algorithm, using only basic ruby-Fortran (referencing the old quote "You can write Fortran code in any language."), but I suspect there is a much more concise and idiomatic ruby way.

Since I'm unaware of a common name for this operation, let me describe it briefly. I have a hash of hashes like this example:

{
  "-cutoff:" =>
  {
    :flag => {:set_ie1 => [:useCutoff, true]},
    :arg => {:vector_ie1 => :double}
  },
  "-depth:" =>
  {
    :flag => {:set_ie2 => [:useInconsistent, true]},
    :arg => :double,
    :default => 2.0
  },
  "-maxclust:" =>
  {
    :flag => {:set_ie3 => [:useCutoff, false]},
    :arg => {:vector_ie2 => :index}
  },
  :fn => "arrayTypeOptions"
}

There are unique symbols like :vector_ie1 and :set_ie3 embedded within the structure of the tree. I need to remove all branches of the tree other than the path from the root to the leave with the symbol. Given the example above:

shake_tree(specs, :vector_ie1)

would return:

{
  "-cutoff:" =>
  {
    :flag => {:set_ie1 => [:useCutoff, true]},
    :arg => {:vector_ie1 => :double}
  }
}

and

shake_tree(specs, :set_ie2)

would return:

{
  "-depth:" =>
  {
    :flag => {:set_ie2 => [:useInconsistent, true]},
    :arg => :double,
    :default => 2.0
  }
}

How would a more experienced ruby coder approach this task?

Answer 1

Here is my recursive implementation. I decided to call it shake_tree to keep RubyMine's spell-checker happy (and because I liked the sound of shake_tree specs key):

def shake_tree(specs, key)
  parent = find_parent(specs, key)
  parent ? { parent => specs[parent] } : nil
end

def find_parent(specs, key, keypath = [])
  specs.each do |k, v|
    if k == key
      return (keypath + [k])[0]
    elsif v.is_a?(Hash)
      branch = find_parent(v, key, keypath + [k])
      if !branch.nil?
        return branch
      end
    end
  end
  nil
end

This returns exactly the output specified above.

I'm still curious to know if there's a common name for this.