Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A variation of closure_tree with support for multiple parents
class CreateNodes < ActiveRecord::Migration[6.0]
def change
create_table :nodes do |t|
end
create_table :node_edges do |t|
t.integer :parent_id, null: false
t.integer :child_id, null: false
end
create_table :node_edge_hierarchies, id: false do |t|
t.integer :ancestor_id, null: false
t.integer :descendant_id, null: false
t.index [:ancestor_id, :descendant_id], unique: true
t.index :descendant_id
end
end
end
class Node < ApplicationRecord
has_many :child_edges, class_name: "NodeEdge", foreign_key: "parent_id"
has_many :children, class_name: "Node", through: :child_edges, source: :child
has_many :parent_edges, class_name: "NodeEdge", foreign_key: "child_id"
has_many :parents, class_name: "Node", through: :parent_edges, source: :parent
def self.roots
where.not(id: NodeEdge.select(:parent_id))
end
def self.ancestors
where(id: parent_edges.and_ancestors.select(:parent_id))
end
def self.descendants
where(id: child_edges.and_descendants.select(:child_id))
end
end
class NodeEdge < ApplicationRecord
belongs_to :parent, class_name: "Node", touch: true
belongs_to :child, class_name: "Node"
has_many :ancestor_hierarchies, class_name: "NodeEdgeHierarchy", foreign_key: "descendant_id"
has_many :self_and_ancestors, through: :ancestor_hierarchies, source: :ancestor
has_many :descendant_hierarchies, class_name: "NodeEdgeHierarchy", foreign_key: "ancestor_id"
has_many :self_and_descendants, through: :descendant_hierarchies, source: :descendant
validates :parent, :child, presence: true
validate :validate_no_circular_reference
after_create :create_hierarchies
after_destroy :destroy_hierarchies
def self.rebuild_hierarchies
transaction do
NodeEdgeHierarchy.delete_all
find_each(&:create_hierarchies)
end
end
def self.hash_tree
NodeEdgeHierarchy.node_edges_hash_tree(all)
end
def self.and_descendants
unscoped.where(id: NodeEdgeHierarchy.where(ancestor_id: select(:id)).select(:descendant_id))
end
def self.and_ancestors
unscoped.where(id: NodeEdgeHierarchy.where(descendant_id: select(:id)).select(:ancestor_id))
end
def create_hierarchies
NodeEdgeHierarchy.create_for_node_edge(self)
end
private
def validate_no_circular_reference
if circular_reference?
errors.add(:parent_id, I18n.t("activerecord.node_edge.must_not_be_descendant"))
end
end
def circular_reference?
return false if parent_id.nil? || child_id.nil?
return true if parent_id == child_id
NodeEdgeHierarchy.where(
ancestor_id: NodeEdge.where(parent_id: child_id).select(:id),
descendant_id: NodeEdge.where(child_id: parent_id).select(:id)
).any?
end
# Delete any hierarchies associated with this record and its descendants
def destroy_hierarchies
NodeEdgeHierarchy.delete_for_node_edge(self)
end
end
class NodeEdgeHierarchy < ApplicationRecord
belongs_to :ancestor, class_name: "NodeEdge"
belongs_to :descendant, class_name: "NodeEdge"
def self.node_edges_hash_tree(roots)
build_node_edges_hash_tree(roots, roots.and_descendants.includes(:child))
end
def self.build_node_edges_hash_tree(node_edges, descendants)
node_edges.each_with_object({}) do |node_edge, hash_tree|
children = descendants.find_all do |descendant|
descendant.parent_id == node_edge.child_id
end
hash_tree[node_edge] = build_node_edges_hash_tree(children, descendants)
end
end
def self.delete_for_node_edge(node_edge)
# Delete all ancestor hierarchy records for the descendant ids
ancestor_edges = node_edge.self_and_ancestors.to_a
NodeEdgeHierarchy.where(
ancestor_id: node_edge.ancestor_hierarchies.select(:ancestor_id),
descendant_id: node_edge.descendant_hierarchies.select(:descendant_id)
).delete_all
# Recreate ancestor hierarchies in case we deleted a shared hierarchy
ancestor_edges.each do |ancestor_edge|
create_for_node_edge(ancestor_edge)
end
end
def self.create_for_node_edge(node_edge)
create_ancestors_for_node_edge(node_edge)
create_descendants_for_node_edge(node_edge)
end
def self.create_ancestors_for_node_edge(node_edge)
parent_edges = NodeEdge.where(child_id: node_edge.parent_id)
ancestor_hierarchies = where(descendant_id: parent_edges.select(:id)).group(:ancestor_id).
select(:ancestor_id, connection.quote(node_edge.id))
# Add this node edge to itself and its ancestors
# NOTE: ON CONFLICT is PostgreSQL specific, you can use INSERT IGNORE on MySQL
connection.execute <<~SQL
INSERT INTO node_edge_hierarchies (ancestor_id, descendant_id)
SELECT #{connection.quote(node_edge.id)}, #{connection.quote(node_edge.id)}
UNION ALL
#{ancestor_hierarchies.to_sql}
ON CONFLICT (ancestor_id, descendant_id) DO NOTHING
SQL
end
def self.create_descendants_for_node_edge(node_edge)
child_edges = NodeEdge.where(parent_id: node_edge.child_id)
child_hierarchies = where(ancestor_id: child_edges.select(:id))
# Add all descendents to this node edge and its ancestors
# NOTE: ON CONFLICT is PostgreSQL specific, you can use INSERT IGNORE on MySQL
connection.execute <<~SQL
INSERT INTO node_edge_hierarchies (ancestor_id, descendant_id)
SELECT node_edge_hierarchies.ancestor_id, child_hierarchies.descendant_id
FROM node_edge_hierarchies,
(#{child_hierarchies.select(:descendant_id).to_sql}) AS child_hierarchies
WHERE node_edge_hierarchies.descendant_id = #{connection.quote(node_edge.id)}
GROUP BY node_edge_hierarchies.ancestor_id, child_hierarchies.descendant_id
ON CONFLICT (ancestor_id, descendant_id) DO NOTHING
SQL
end
end
@Alexspriet

This comment has been minimized.

Copy link

@Alexspriet Alexspriet commented Feb 23, 2021

Hi,

Very interesting GIST, how can I implement your solution?
Do you still need closure_tree gem?

Cheers

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment