adjacency list modeling
class Tree | |
attr_accessor :nodes | |
def initialize | |
@nodes = {} | |
end | |
def node(id) | |
@nodes[id] | |
end | |
# helper for hash-like access | |
def [](id) | |
node(id) | |
end | |
def add_node(node) | |
raise "#{node.class} != Node" if node.class != Node | |
if !node.parent.nil? | |
# check if the parent is part of the tree | |
existing_parent = self.node(node.parent.id) | |
if existing_parent.nil? | |
raise "Unable to add node #{node.id} to the tree. It specifies a parent #{node.parent.id} That has not been added to the tree" | |
end | |
node.parent = existing_parent | |
existing_parent.children.push(node.id).uniq | |
end | |
@nodes[node.id] = node | |
end | |
def ancestors(node, ancestor_list = []) | |
# traverse up the tree to get all parents | |
# return the list if the parent of the current node is already in the list | |
if node.parent && !ancestor_list.include?(node.parent) | |
ancestor_list.push node.parent | |
self.ancestors(node.parent, ancestor_list) | |
else | |
ancestor_list.empty? ? nil : ancestor_list.reverse | |
end | |
end | |
def path(node) | |
if node.parent.nil? | |
path = node.id.to_s | |
else | |
path = ancestors(node).push(node).map{ |n| n.id.to_s }.join ':' | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment