class HierarchicalGraph
Constants
- VERSION
Attributes
ancestors_cache[R]
child_to_parents[R]
descendants_cache[R]
nodes[R]
parent_to_children[R]
Public Class Methods
new()
click to toggle source
# File lib/hierarchical_graph.rb, line 9 def initialize @nodes = {} @parent_to_children = {} @child_to_parents = {} @ancestors_cache = {} @descendants_cache = {} end
Public Instance Methods
[](id)
click to toggle source
# File lib/hierarchical_graph.rb, line 17 def [](id) nodes[id] end
add_node(id, attributes={})
click to toggle source
# File lib/hierarchical_graph.rb, line 33 def add_node(id, attributes={}) validate_not_present! id clear_cache parent_to_children[id] = Set.new child_to_parents[id] = Set.new nodes[id] = Node.new self, id, attributes end
add_relation(parent_id:, child_id:)
click to toggle source
# File lib/hierarchical_graph.rb, line 57 def add_relation(parent_id:, child_id:) validate_present! parent_id, child_id clear_cache parent_to_children[parent_id] << child_id child_to_parents[child_id] << parent_id nil end
ancestors_of(id)
click to toggle source
# File lib/hierarchical_graph.rb, line 89 def ancestors_of(id) validate_present! id ancestors_cache[id] ||= parents_of(id).flat_map do |parent| ancestors_of(parent.id) + [parent] end.uniq(&:id) end
children_of(id)
click to toggle source
# File lib/hierarchical_graph.rb, line 83 def children_of(id) validate_present! id parent_to_children[id].map { |node_id| nodes[node_id] } end
descendants_of(id)
click to toggle source
# File lib/hierarchical_graph.rb, line 97 def descendants_of(id) validate_present! id children_of(id).flat_map do |child| [child] + descendants_of(child.id) end.uniq(&:id) end
descendants_subgraph_from(id)
click to toggle source
# File lib/hierarchical_graph.rb, line 121 def descendants_subgraph_from(id) subgraph_of [id] + descendants_of(id).map(&:id) end
each(&block)
click to toggle source
# File lib/hierarchical_graph.rb, line 21 def each(&block) nodes.each_value(&block) end
empty?()
click to toggle source
# File lib/hierarchical_graph.rb, line 25 def empty? nodes.empty? end
parents_of(id)
click to toggle source
# File lib/hierarchical_graph.rb, line 77 def parents_of(id) validate_present! id child_to_parents[id].map { |node_id| nodes[node_id] } end
remove_node(id)
click to toggle source
# File lib/hierarchical_graph.rb, line 42 def remove_node(id) validate_present! id parent_to_children[id].each { |child_id| child_to_parents[child_id].delete id } child_to_parents[id].each { |parent_id| parent_to_children[parent_id].delete id } parent_to_children.delete id child_to_parents.delete id nodes.delete id clear_cache nil end
remove_relation(parent_id:, child_id:)
click to toggle source
# File lib/hierarchical_graph.rb, line 67 def remove_relation(parent_id:, child_id:) validate_present! parent_id, child_id clear_cache parent_to_children[parent_id].delete child_id child_to_parents[child_id].delete parent_id nil end
roots()
click to toggle source
# File lib/hierarchical_graph.rb, line 29 def roots select(&:root?) end
subgraph_of(ids)
click to toggle source
# File lib/hierarchical_graph.rb, line 105 def subgraph_of(ids) ids.each { |id| validate_present! id } HierarchicalGraph.new.tap do |subgraph| ids.each do |id| subgraph.add_node id, nodes[id].data end subgraph.each do |node| children_of(node.id).each do |child| subgraph.add_relation parent_id: node.id, child_id: child.id unless subgraph[child.id].nil? end end end end
to_s()
click to toggle source
# File lib/hierarchical_graph.rb, line 125 def to_s "<#{self.class.name} nodes:[#{map(&:to_s).join(', ')}]>" end
Also aliased as: inspect
Private Instance Methods
clear_cache()
click to toggle source
# File lib/hierarchical_graph.rb, line 144 def clear_cache descendants_cache.clear ancestors_cache.clear end
tsort_each_child(node, &block)
click to toggle source
# File lib/hierarchical_graph.rb, line 149 def tsort_each_child(node, &block) children_of(node.id).each(&block) end
tsort_each_node(&block)
click to toggle source
# File lib/hierarchical_graph.rb, line 153 def tsort_each_node(&block) each(&block) end
validate_not_present!(*ids)
click to toggle source
# File lib/hierarchical_graph.rb, line 139 def validate_not_present!(*ids) invalid_ids = ids.select { |id| nodes.key? id } raise "Nodes already exist: #{invalid_ids.join(', ')}" if invalid_ids.any? end
validate_present!(*ids)
click to toggle source
# File lib/hierarchical_graph.rb, line 134 def validate_present!(*ids) invalid_ids = ids.reject { |id| nodes.key? id } raise "Nodes not found: #{invalid_ids.join(', ')}" if invalid_ids.any? end