resgraph/acts-as-dag

Directed Acyclic Graph hierarchy for Rail's ActiveRecord models

acts-as-dag's Issues

shortest_path_between is slow, generating a lot of database queries

anyone else ever attempted to make shortest_path_between fast?

https://github.com/payrollhero/acts-as-dag/blob/master/lib/dag/edges.rb#L88-L108

    #Finds the shortest path between ancestor and descendant returning as an array
    def shortest_path_between(ancestor, descendant, path=[])
      shortest = []
      ancestor.children.each do |child|
        if child == descendant
          temp = path.clone
          temp << child
          if shortest.blank? || temp.length < shortest.length
            shortest = temp
          end
        elsif self.find_link(child, descendant)
          temp = path.clone
          temp << child
          temp = self.shortest_path_between(child, descendant, temp)
          if shortest.blank? || temp.length < shortest.length
            shortest = temp
          end
        end
      end
      return shortest
    end

STI for the node models?

So the links/edge tables support STI. How can I make it so that it supports STI node models as well?

I have STI models. The gem inserts entries correctly when I use the create_edge method but when I call the .children it queries the base class and not the STI class name.

Saving a new node after adding a parent fails validation

This issue is somewhat related to #11 which concerned the addition of an existing node as a parent to a new unsaved node. Commit #17 resolved this with some validation changes in the link class and additional options in some has_many calls on the node class.

However #11 did not address what happens when the new node is subsequently saved. While upgrading a Rails 3.2.x app to 4.x, I discovered that saving a node in this situation actually fails despite the fact that valid? returns true.

> a = Person.create
> b = Person.new
> b.parents << a
> b.valid?
=> true
> b.save
=> false

The problem manifests in slightly different ways depending on whether the parent is a terminal or has a parent itself. Although I have only tested on Rails 4.0, I believe the issue remains present in subsequent versions and occurs in part because of a change in Rails 4.x in the implementation of ActiveRecord::Associations::HasManyThroughAssociation#concat (see: rails/rails@610b632). This method calls concat_records which has a new implementation in the HasManyThroughAssociation class. One thing this new implementation does is to build a new through record, i.e. a link object. This object is instantiated when parents are added to the node record regardless of whether that record has been persisted. In Rails 3.x, in contrast, the through object is not built until the child is saved.

In the process of building the through object, the Rails 4 implementation also instantiates a 'through association' object, i.e. representing the has_many :links_as_child association. This change leads to two different problems for acts-as-dag...

1. When the child is saved, the through object is saved twice, causing acts-as-dag's UpdateCorrectnessValidator to fail the 'no changes' test. This occurs as follows. Activerecord autosaves the record's associations (see AutosaveAssociation::ClassMethods.add_autosave_association_callbacks) including the has_many :links_as_child and has_many :parents, :through => :links_as_child associations:
   1. has_many :links_as_child is the through association that was instantiated when the parent was added to the child prior to saving. Because the association has been instantiated, saving it results in the through object, the link connecting the parent and child nodes, being persisted. This does not happen in Rails 3.x because at this point the association had not yet been instantiated.
   2. The has_many :parents, :through => :links_as_child association is saved after has_many :links_as_child, and this also causes the through record to be saved again (see HasManyThroughAssociation#insert_record). This in turn causes acts-as-dag's UpdateCorrectnessValidator validation to fail because the record has not changed since the last time it was saved.
2. A second, different problem arises if the parent itself has a parent, with the result that the bridging link between child and grandparent fails to validate. This occurs as follows. Prior to autosaving the child object's associations as described above, all of those associations are first validated (these validations are also added by AutosaveAssociation::ClassMethods.add_autosave_association_callbacks). In the case of the has_many :links_as_children association, acts-as-dag's CreateCorrectnessValidator checks whether the link has any duplicates by calling has_duplicates(record). This method calls source and sink on the record, which instantiates and memoizes a pair of EndPoint objects based on the record's current ancestor and descendant. However since the child has not yet been saved, the sink endpoint is memoized with a nil id. Once validations have completed the associations are autosaved. However saving the link association triggers the perpetuate before_save filter. If the parent itself has a parent, perpetuate will try to create a new indirect bridging link between the child and the grandparent. However it creates this object using the previously memoized sink from the link between the parent and child. As a result, the bridging link is instantiated with a nil descendant_id and therefore when it is saved it fails the validates :descendant, :presence => true check.

I have a PR coming that resolves both of these issues. The first problem requires simply removing the "No changes" test from UpdateCorrectnessValidator. I don't see a compelling reason to retain this test since it is really a concern of activerecord. The second problem can be resolved by circumventing memoization of the source and sink if they point to records that haven't yet been persisted.

Also, in the course of testing this I discovered a flaw in one of the existing tests:

  #Tests that we catch links that would be duplicated on creation
  def test_validation_on_create_duplication_catch
    a = Node.create!
    b = Node.create!
    e = Default.create_edge(a, b)
    e2 = Default.create_edge(a, b)
    assert !e2
    assert_raises(ActiveRecord::RecordInvalid) { e3 = Default.create_edge!(a, b) }
  end

This will never fail the create validation since create_edge itself finds the existing link and updates it. The solution is to replace it with build_edge(a,b).save.

API conflicts with activerecord

There's a created? method in ActiveRecord that is also injected into acts_as_dag nodes.

I'm not sure what the sensible way of fixing this should be as fixing it by renaming the acts_as_dag version will break anything that relies on the existing behaviour.

In ActiveRecord 3.1.8 this conflict means it's impossible to create links, as primary_key= tries to call the ActiveRecord connected? method, and fails with ArgumentError: wrong number of arguments (0 for 2).

links migration

Quicker to tell you than send a pull request... there's an errant comma in the first line of the two :links migrations shown in your readme.

Using acts-as-dag with acts_as_list

Unfortunately it seems this excellent gem is no longer being actively maintained, but I mention the following here for the benefit of anyone else who happens to use it and may run into the same problem...

If using acts-as-dag with acts_as_list, e.g. to allow sibling links to be ordered, it is important that in the link model definition acts_as_dag_links be called before acts_as_list.

Explanation -
acts_as_list adds a before_destroy callback to the link model that causes a link record to be reloaded from the database before it is destroyed:

before_destroy :reload, unless: Proc.new { new_record? || destroyed_via_scope? || act_as_list_no_update? }

However acts-as-dag also has a destroy callback:

before_destroy :destroyable!, :perpetuate

perpetuate uses rewire_crossing to obtain other links affected by the destruction of a direct link and to manipulate the count attribute of each one in memory in order to act as a flag to determine what subsequently happens to it in push_associated_modification!. In the case where the direct link is being destroyed, associated indirect links will also be destroyed by push_associated_modification!. However the before_destroy callback above then causes destroyable! to be called on that indirect link, which also checks the count attribute that was modified by perpetuate to ensure that the link is in fact destroyable?.

Here is where the problem occurs - if acts-as-list is called before acts_as_dag_links, the reload callback will fire before destroyable! and the unsaved modification that perpetuate made to the count attribute will be lost. The result is that destroyable? will fail and destroyable! will throw an exception.

The solution is simply to ensure that acts_as_dag_links is called before acts_as_list.

Remove VERSION file

My pull request to clean up the jeweler/gemspec stuff left out removing the VERSION file. It is no longer needed and can be removed. It doesn't seem worth creating another pull request so I'm just opening an issue ticket.

Necessary to manipulate links when creating nodes/edges?

Will building the graph A->B, B-> C, A->C and not wanting to directly manipulate Links, I get an error when creating the A->C edge via the children association on Node A.

If I load the edge and call make direct, the error goes away. It doesn't seem like I should have to deal with Links unless I want to manipulate them directly.

Is this the expected behavior?

Trying to set parents as part of object creation triggers validation failure of [:links_as_child, "is invalid"]

Let's say you've got a Person model with has_dag_links and "attr_accessible :parents".

In the Rails console:

1.9.3p194 :001 > Person.create
=> #<Person id: 1, created_at: "2013-01-18 22:49:30", updated_at: "2013-01-18 22:49:30">
1.9.3p194 :002 > p=Person.new(parents: [Person.first])
1.9.3p194 :003 > p.valid?
1.9.3p194 :004 > p.errors.first
=> [:links_as_child, "is invalid"]

It works fine if you create a Person without parents, then add parents. E.g.

1.9.3p194 :001 > p=Person.create
=> #<Person id: 2, created_at: "2013-01-18 22:58:09", updated_at: "2013-01-18 22:58:09">
1.9.3p194 :002 > p.parents << Person.first
SQL (0.3ms) INSERT INTO "person_links" ("ancestor_id", "count", "descendant_id", "direct") VALUES (?, ?, ?, ?) [["ancestor_id", 1], ["count", 1], ["descendant_id", 2], ["direct", true]]

Is there a way to set parents as part of object creation? I'd like users to be able to pick the parents of an object in the standard Rails form for creating a new object.

[issue deleted]

[EDIT] was actually a duplicate of # 20

fix for acts-as-dag 1.x (Rails 2.3.x)

Hi! We're using acts-as-dag 1.x with Rails 2.3.x. Just fixed a bug that occurred when inserting child/parent nodes directly to the associations. Rails will do that in a create scope and then use the wrong attributes when instantiating bridging legs.

I cannot make a pull request as there's no 1.x branch in your repository. But see this diff to check my change.

If you create and push a 1.x branch at the v1.1.3 tag I'll be able to make a proper pull request to this branch.

How to recreate all indirect links as fail-safe?

Hello,

I was wondering if there is a kind of fail-safe method already to recreate all indirect links on the basis of the direct edges.

That is: If all indirect links in the dag link table were deleted and only the direct edges were left, how would I reconsruct all the indirect links?

Many thanks!
fiedl