Skip to content

Instantly share code, notes, and snippets.

@leklund
Created April 29, 2015 15:03
Show Gist options
  • Save leklund/f1fb60ea820720463938 to your computer and use it in GitHub Desktop.
Save leklund/f1fb60ea820720463938 to your computer and use it in GitHub Desktop.
adjacency list modeling
class Node
attr_accessor :id, :name, :parent, :children
def initialize(opts = {})
@id = opts[:id]
@name = opts[:name]
@parent = opts[:parent]
# add children if passed an array or initialize as an empty array
@children = opts[:children].is_a?(Array) ? opts[:children] : []
end
end
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