Module: ActsAsDAG::HelperMethods

Defined in:
lib/acts_as_dag/acts_as_dag.rb

Class Method Summary collapse

Class Method Details

creates a single link in the given link_class's link table between parent and child object ids and creates the appropriate entries in the descendant table


238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
# File 'lib/acts_as_dag/acts_as_dag.rb', line 238

def self.link(parent, child)
  # Sanity check
  raise "Parent has no ID" if parent.id.nil?
  raise "Child has no ID" if child.id.nil?
  raise "Parent and child must be the same class" if parent.class != child.class

  klass = child.class

  # Return if the link already exists because we can assume that the proper descendants already exist too
  return if klass.link_table_entries.where(:parent_id => parent.id, :child_id => child.id).exists?

  # Create a new parent-child link
  klass.link_table_entries.create!(:parent_id => parent.id, :child_id => child.id)

  # If we have been passed a parent, find and destroy any existing links from nil (root) to the child as it can no longer be a top-level node
  unlink(nil, child) if parent
end

Create a descendant link to iteself, then iterate through all children We add this node to the ancestor array we received Then we create a descendant link between it and all nodes in the array we were passed (nodes traversed between it and all its ancestors affected by the unlinking). Then iterate to all children of the current node passing the ancestor array along


323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
# File 'lib/acts_as_dag/acts_as_dag.rb', line 323

def self.rebuild_subtree_links(current, path = [])
  indent = Array.new(path.size, "  ").join
  klass = current.class

  # Add current to the list of traversed nodes that we will pass to the children we decide to recurse to
  path << current

  # Create descendant links to each ancestor in the array (including itself)
  path.reverse.each_with_index do |record, index|
    klass.descendant_table_entries.find_or_create_by!(:ancestor_id => record.id, :descendant_id => current.id, :distance => index)
  end

  # Now check each child to see if it is a descendant, or if we need to recurse
  for child in current.children
    rebuild_subtree_links(child, path.dup)
  end
end

breaks a single link in the given hierarchy_link_table between parent and child object id. Updates the appropriate Descendants table entries


280
281
282
283
284
285
286
287
288
# File 'lib/acts_as_dag/acts_as_dag.rb', line 280

def self.unlink(parent, child)
  # Raise an exception if there is no child
  raise "Child cannot be nil when deleting a category_link" unless child

  klass = child.class

  # delete the link if it exists
  klass.link_table_entries.where(:parent_id => parent.try(:id), :child_id => child.id).destroy_all
end

290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
# File 'lib/acts_as_dag/acts_as_dag.rb', line 290

def self.update_transitive_closure_for_destroyed_link(destroyed_link)
  # We have unlinked C and D
  #                 A   F
  #                / \ /
  #               B   C
  #               |
  #               |   D
  #                \ /
  #                 E
  #
  klass = destroyed_link.node_class
  parent = destroyed_link.parent
  child = destroyed_link.child

  # If the parent was nil, we don't need to update descendants because there are no descendants of nil
  return unless parent

  # Now destroy all affected subtree_links (ancestors of parent (C), descendants of child (D))
  klass.descendant_table_entries.where(:ancestor_id => parent.path_ids, :descendant_id => child.subtree_ids).delete_all

  # Now iterate through all ancestors of the subtree_links that were deleted and pick only those that have no parents, namely (A, D)
  # These will be the starting points for the recreation of descendant links
  starting_points = klass.find(parent.path_ids + child.subtree_ids).select{|node| node.parents.empty? || node.parents == [nil] }

  # POSSIBLE OPTIMIZATION: The two starting points may share descendants. We only need to process each node once, so if we could skip dups, that would be good
  starting_points.each{|node| rebuild_subtree_links(node)}
end

256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
# File 'lib/acts_as_dag/acts_as_dag.rb', line 256

def self.update_transitive_closure_for_new_link(new_link)
  klass = new_link.node_class

  # If we're passing :parents or :children to a new record as part of #create, transitive closure on the nested records will
  # be updated before the new record's after save calls :initialize_dag. We ensure it's been initalized before we start querying
  # its descendant_table or it won't appear as an ancestor or descendant until too late.
  new_link.parent.send(:initialize_dag) if new_link.parent && new_link.parent.id_changed?
  new_link.child.send(:initialize_dag) if new_link.child && new_link.child.id_changed?


  # The parent and all its ancestors need to be added as ancestors of the child
  # The child and all its descendants need to be added as descendants of the parent
  ancestor_ids_and_distance = klass.descendant_table_entries.where(:descendant_id => new_link.parent_id).pluck(:ancestor_id, :distance) # (totem => totem pole), (totem_pole => totem_pole)
  descendant_ids_and_distance = klass.descendant_table_entries.where(:ancestor_id => new_link.child_id).pluck(:descendant_id, :distance) # (totem pole model => totem pole model)

  ancestor_ids_and_distance.each do |ancestor_id, ancestor_distance|
    descendant_ids_and_distance.each do |descendant_id, descendant_distance|
      klass.descendant_table_entries.find_or_create_by!(:ancestor_id => ancestor_id, :descendant_id => descendant_id, :distance => ancestor_distance + descendant_distance + 1)
    end
  end
end