Building a tree from the leaves down

Ruby
1

Have a algorithmic problem, I can’t quite get a clear idea of how to
handle it.

I have a list of objects that respond to #case that will return nil
or a case object. Each case object also responds to #case and may
return nil or a case object, and so on. Basically I have to build a
tree from the bottom up (top down?) out of this list keyed on cases.

Basic example, let’s use this class:

class CaseObject
attr :case
def initialize(parent_case)
@case = parent_case
end
end

And this has been defined:

c1 = CaseObject.new(nil)
c11 = CaseObject.new(c1)
c12 = CaseObject.new(c1)
c121 = CaseObject.new(c12)
c122 = CaseObject.new(c12)
d1 = CaseObject.new(nil)
d11 = CaseObject.new(d1)
d12 = CaseObject.new(d1)

Then I am given all the leaf nodes in a list:

[c11, c121, c122, d11, d12]

I need to reconstruct the hierarchy into a tree (ie. a Hash):

{
c1 => {
c11 => nil,
c12 => {
c121 => nil,
c122 => nil
}
},
d1 => {
d11 => nil,
d12 => nil
}
}

There’s probably some simple way to do this that I am overlooking, but
it’s alluding me at the moment.

2

Thomas S. wrote in post #1012175:

Have a algorithmic problem, I can’t quite get a clear idea of how to
handle it.

I have a list of objects that respond to #case that will return nil
or a case object. Each case object also responds to #case and may
return nil or a case object, and so on. Basically I have to build a
tree from the bottom up (top down?) out of this list keyed on cases.

Basic example, let’s use this class:

class CaseObject
attr :case
def initialize(parent_case)
@case = parent_case
end
end

And this has been defined:

c1 = CaseObject.new(nil)
c11 = CaseObject.new(c1)
c12 = CaseObject.new(c1)
c121 = CaseObject.new(c12)
c122 = CaseObject.new(c12)
d1 = CaseObject.new(nil)
d11 = CaseObject.new(d1)
d12 = CaseObject.new(d1)

Then I am given all the leaf nodes in a list:

[c11, c121, c122, d11, d12]

I need to reconstruct the hierarchy into a tree (ie. a Hash):

A single Hash can never be a tree.

{
c1 => {
c11 => nil,
c12 => {
c121 => nil,
c122 => nil
}
},
d1 => {
d11 => nil,
d12 => nil
}
}

There’s probably some simple way to do this that I am overlooking, but
it’s alluding me at the moment.

Hmm…

cache = Hash.new {|h,k| h[k] = {}}

[c11, c121, c122, d11, d12].each do |x|
cache[x.case][x] = cache[x]
end

Now you only need to find the roots. :slight_smile:

tree = Hash[*all_nodes.select {|x| x.case.nil?}.map {|root|
[root, cache[root]]}]

Roughly and untested.

I’d rather create a specific data structure though.

Kind regards

robert

3

On Thu, Jul 21, 2011 at 9:49 AM, Robert K.
[email protected]wrote:

c11 = CaseObject.new(c1)

  }

Hmm…
cache[root]}]

Roughly and untested.

Kind regards

robert

For fun, here’s my OO-oriented approach with inspiration (though
different)
from Robert’s solution:

class CaseObject
attr_reader :case
attr_reader :name
def initialize(parent, name)
@case = parent
@name = name
end
def inspect
@name
end
end

class Hash
INDENT = " " * 2
def inspect(indent = “”)
result = “{\n”
processed = 0
total = count()
each do |k, v|
total += 1
v = v.is_a?(Hash) ? v.inspect(indent + INDENT) : v.inspect
result << indent + INDENT + “#{k.inspect} => #{v}”
result << “,” if processed < total
result << “\n”
end
“#{result}#{indent}}”
end
end

class Tree
attr_reader :registry
def initialize(parent = :parent)
@parent = parent
@registry = {}
end
def register(node)
parent = node.send(@parent)
if parent
@registry[parent] ||= {}
@registry[parent][node] = @registry[node]
register(parent)
end
end
def to_hash
@registry.select { |k, v| k.send(@parent_method).nil? }
end
end

all_nodes = [
c1 = CaseObject.new(nil, :c1),
c11 = CaseObject.new(c1, :c11),
c12 = CaseObject.new(c1, :c12),
c121 = CaseObject.new(c12, :c121),
c122 = CaseObject.new(c12, :c122),
d1 = CaseObject.new(nil, :d1),
d11 = CaseObject.new(d1, :d11),
d12 = CaseObject.new(d1, :d12)
]
leaves = [c11, c121, c122, d11, d12]

puts “All Nodes: #{all_nodes.inspect}”
puts “Leaves: #{leaves.inspect}”

tree = Tree.new(:case)
leaves.each { |x| tree.register(x) }
hash = tree.to_hash

puts “\nCache Hash:\n#{tree.registry.inspect}”
puts “\nTree Hash:\n#{hash.inspect}”

4

On Thu, Jul 21, 2011 at 10:21 AM, Intransition [email protected]
wrote:

class CaseObject
c12 = CaseObject.new(c1)
I need to reconstruct the hierarchy into a tree (ie. a Hash):
d11 => nil,
d12 => nil
}
}

There’s probably some simple way to do this that I am overlooking, but
it’s alluding me at the moment.

This seems to work:

class CaseObject

private
def merge_in(hash, ancestry_chain)
if 1 == ancestry_chain.size
hash[ancestry_chain.pop] = nil
else
crnt = ancestry_chain.pop
hash[crnt] ||= Hash.new
merge_in hash[crnt], ancestry_chain
end
hash
end
public

def self.as_hash(leaves)
leaves.each.with_object(Hash.new) { |leaf, hash| merge_in hash,
leaf.ancestors }
end

attr :case

def initialize(parent_case)
@case = parent_case
end

def ancestors
return [self] unless self.case
[self] + self.case.ancestors
end

end

…

CaseObject.as_hash [c11, c121, c122, d11, d12]

5

Eric H. wrote in post #1012291:

Also, there’s no relationship between the d nodes and the c nodes.

So it’s a forest and not a tree. :slight_smile:

Cheers

robert

6

On Jul 21, 2011, at 8:21 AM, Intransition wrote:

c1 = CaseObject.new(nil)
c11 = CaseObject.new(c1)
c12 = CaseObject.new(c1)
c121 = CaseObject.new(c12)
c122 = CaseObject.new(c12)
d1 = CaseObject.new(nil)
d11 = CaseObject.new(d1)
d12 = CaseObject.new(d1)

This is already a tree.

Then I am given all the leaf nodes in a list:

[c11, c121, c122, d11, d12]

You won’t need to rebuild the original tree if you have bidirectional
links.

class CaseObject
def initialize parent
@case = parent
@children = []
parent.add self if parent
end

def add child
@children << child
end
end

Walking the tree up or down is simple when you can walk both up and down
so the exercise is left to the reader.

Also, there’s no relationship between the d nodes and the c nodes.

7

On Jul 21, 4:30pm, Kendall G. [email protected] wrote:

total += 1
v = v.is_a?(Hash) ? v.inspect(indent + INDENT) : v.inspect
result << indent + INDENT + “#{k.inspect} => #{v}”
result << “,” if processed < total
result << “\n”
end
“#{result}#{indent}}”
end
end

Always a good idea to make it easier to see what the hell is going
on :slight_smile:

@registry[parent][node] = @registry[node]
register(parent)
end
end
def to_hash
@registry.select { |k, v| k.send(@parent_method).nil? }
end
end

Nice, that’s pretty easy to understand. Thanks.

FYI, @parent_method, should be @parent.