Acts As Dag, short for Acts As Directed Acyclic Graph, is a plugin which allows you to represent DAG hierarchy using your ActiveRecord models.
Say you have been using one of the many great plugins that allow for Tree hierarchy like: acts_as_tree or acts_as_nested_set, acts_as_better_nested_set, etc. Yet, you feel something is missing. Tree’s are just not good enough. You want to allow each record to have multiple parent objects within a hierarchy as well as multiple children. Then you are going to need a DAG instead of a tree, and thats were this plugin becomes useful.
en.wikipedia.org/wiki/Directed_acyclic_graph
Yes, but I think they aren’t as fast or feature filled. Flogic has a good simple acts_as_dag plugin on github which would be similar to acts_as_tree.
-
DAG graph functionality
-
STI support
-
Polymorphic graphs
-
Association injection for graph nodes
-
Instance method injections (root?,leaf?) for graph nodes
-
O(1) lookups, no breath or depth first searching
-
O(x*y) insert, update and delete, where x & y are the number of ancestors and descendants of a node.
This uses named_scope so your going to need Rails 2.1 or above.
script/plugin install git://github.com/mleventi/acts-as-dag.git
-
Node: A source or destination of a link or edge in the graph.
-
Edge: A direct connection between two nodes. These can only be created by your application.
-
Link: A indirect connection between two nodes. Denotes the existence of a path. These can only be created by the plugin internally.
This section outlines the two methods that need to be included in your ActiveRecord models. In general this whole plugin can be thought of as one big has_many association.
This singleton class method needs to be called in your ActiveRecord model that represents the links for the DAG graph. For non-polymorphic graphs it has a required parameter:
acts_as_dag_links :node_class_name => ‘Class Name of the node model’
If the graph is polymorphic :node_class_name is unnecessary. A polymorphic call would be:
acts_as_dag_links :polymorphic => true
-
:ancestor_id_column. By default, ‘ancestor_id’, column to use for the ancestor reference
-
:descendant_id_column. By default, ‘descendant_id’, column to use for the descendant reference
-
:direct_column. By default, ‘direct’, boolean column that represents whether the link is an edge (direct)
-
:count_column. By default, ‘count’, represents the number of ways to get from A to B.
-
:polymorphic. By default, false, If you want polymorphic graphs see below.
With polymorphic graphs we also have…
-
:ancestor_type_column. By default, ‘ancestor_type’, column to use for the ancestor type reference
-
:descendant_type_column. By default, ‘descendant_type’, column to use for the descendant type reference
Each of the optional column parameters needs a field in the link table. Hence for non-polymorphic graphs a migration would look like…
create_table :links, do |t| t.integer :ancestor_id t.integer :descendant_id t.boolean :direct t.integer :count end And for polymorphic graphs…
create_table :links, do |t| t.integer :ancestor_id t.string :ancestor_type t.integer :descendant_id t.string :descendant_type t.boolean :direct t.integer :count end
Calling acts_as_dag_links method in the class definition injects the following associations.
belongs_to :ancestor belongs_to :descendant
The recieves the following named scopes. The following two scopes narrows a query to only links with a certain ancestor or descendant
named_scope :with_ancestor(ancestor_instance) named_scope :with_descendant(descendant_instance) The scopes below narrow queries to direct or indirect links
named_scope :direct named_scope :indirect The scopes below attach the actual ancestor or descendant nodes
named_scope :ancestor_nodes, :joins => :ancestor named_scope :descendant_nodes, :joins => :descendant
Several class methods get added to the link model to make it easier to find and create edges, and find links.
#Finds an edge of returns nil self.find_edge(ancestor,descendant) #Returns true if an edge exists self.edge?(ancestor,descendant) self.direct?(ancestor,descendant) #Finds a link or returns nil self.find_link(ancestor,descendant) #Returns true if a link exists self.connected?(ancestor,descendant) #Creates an edge between an ancestor and descendant self.create_edge(ancestor,descendant) self.connect(ancestor,descendant) #Creates an edge using save! between an ancestor and descendant self.create_edge!(ancestor,descendant) self.connect!(ancestor,descendant) #Builds an edge between an ancestor and descendant, returning an unsaved edge self.build_edge(ancestor,descendant) #Finds and returns the edge if it exists, or calls build_edge self.find_or_build_edge(ancestor,descendant)
Here is a sample of some of the important instance methods that get added to the link model.
#whether the current edge can be destroyed. If the edge also has a link, ie it can be made indirectly, then it cannot be destroyed. destroyable?() #Make the edge indirect. Removes the direct edge but keeps the indirect links make_indirect() #Makes the link direct. Adds a direct edge onto a link. make_direct() #Number of unique ways to get from the ancestor to the descendant count()
This singleton class method can be optionally called from the node ActiveRecord model. If you do not call it you don’t get all the nice associations within the node model, yet everything will still work fine. It takes the required parameter:
has_dag_links :link_class_name => ‘Class Name of the link model’
-
:prefix. By default, ”. Use a prefix if your model calls has_dag_links for multiple link classes.
If your link class holds a polymorphic graph you also have…
-
:ancestor_class_names. By default [], array of class names that are ancestors to this class.
-
:descendant_class_names. By default [], array of class names that are descendants to this class.
has_dag_links provides a number of has_many and has_many_through associations.
-
links_as_ancestor: Has many association that finds the links with the current instance as ancestor
-
links_as_descendant: Has many association that finds the links with the current instance as descendant
-
links_as_parent: Has many association that finds direct links (edges) with the current instance as ancestor
-
links_as_child: Has many association that finds direct links (edges) with the current instance as descendant
Note that if a record is in links_as_parent it will be in links_as_ancestor. Also note that adding records to either produces the same result as you can only add direct links (edges). Currently there is also an error if a record exists for links_as_ancestor and you try to add it to links_as_parent. The correct way is to use the make_direct method on the link instance.
For non-polymorphic graphs you also get the following associations. These find the actual ancestors as opposed to the link instances.
-
ancestors
-
descendants
-
parents
-
children
For polymorphic graphs where the ancestor_class_names or descendant_class_names includes the specified class names the following associations are also built. For each ancestor_class_name:
-links_as_descendant_for_#{ancestor_class_name.tableize} -links_as_child_for_#{ancestor_class_name.tableize} -ancestor_#{ancestor_class_name.tableize} -parent_#{ancestor_class_name.tableize}
For each descendant_class_name
-links_as_ancestor_for_#{ancestor_class_name.tableize} -links_as_parent_for_#{ancestor_class_name.tableize} -descendant_#{ancestor_class_name.tableize} -child_#{ancestor_class_name.tableize}
Along with the above associations a number of instance methods are defined.
-leaf? , Boolean value as to whether the current node is a leaf (no descendants) -root? , Boolean value as to whether the current node is a root (no ancestors)
With polymorphic graphs for each ancestor_class_name another method is defined.
-root_for_#{ancestor_class_name.tableize}? , Returns true if the node has no ancestors of the represented type.
Likewise for each descendant_class_name.
-leaf_for_#{descendent_class_name.tableize}? , Returns true if the node has no descendants of the represented type.
This section goes over some basic usage examples and presents some caveats.
class Node < ActiveRecord::Base has_dag_links :link_class_name => ‘Link’ end class Link < ActiveRecord::Base acts_as_dag_links :node_class_name => ‘Node’ end #Adding an edge parent_node = Node.create! child_node = Node.create! parent_node.children << child_node #Removing it link = Link.find_link(parent_node,child_node) if link.destroyable? link.destory else link.make_indirect link.save! end
Due to the algorithm used there are some caveats for modifying links. Don’t worry if you try to do something illegal because it will raise exceptions and not muck the graph up.
You can only create new edges where a link doesn’t already exist. If the link exists and you want to make it direct you need to promote it using make_direct instance method. Also you can only create direct links. This makes sense because indirect links are dependent on direct links. An indirect link by itself makes no sense to the algorithm. In reverse, you can only delete links which are direct and have no indirect nature. Hence the link only exists because it is direct and not through a sequence of other links. Instead of deleting these types of links you can downgrade them using make_indirect. This will remove the direct edge A -> C and leave the transitive edge from A -> B and B -> C. So just remember before you add, check if it exists, or use one of the link class method create_edge! which will always work.
This section briefly explains how the plugin works. For a really detailed understanding look at the perpetuate function which is used to fix up the graph when its changed.
To start there is some terminology:
-
Node is a point on the graph
-
Edge is a direct connection between two nodes.
-
Link is a connection using one or more edges.
This implementation works by storing every possible link as a record in the database. The links originate at the ancestor and end at the descendant. Hence checking if X is a descendant of Y can be accomplished in one SQL query. Likewise finding all descendants or ancestors of Y can also be done in a single query. There are simple queries that don’t use recursive stored procedures that you would need with a parent child model. Hence getting information out of the database is really fast. You can also find out the number of unique ways X is connected to Y and whether it has a direct connection. This allows the finding of all parents or children of a node with one query.
The downside to this implementation, besides the large storage requirements, is that updating the graph by adding or removing nodes or edges is not trivial. When edges are added a sort of cross product between the parent and child nodes ancestors and descendants is done that updates the counts and creates new links as necessary. Hence the complexity of an update, add, or deletion, matters heavily on how your graph is arranged and what nodes you are connecting.
Whoever did the awesome_nested_set plugin. This is my first plugin and I used that as a base. The Rails Way was also a great book that essentially taught me Rails.
- Authors
-
Matthew Leventi
Algorithm and plugin designed by Matthew Leventi Email:(first letter of my first name followed by my last name @gmail.com). Im open to questions, very open to bugs, and even more receptive of bug fixes. I am also currently (August 2008) looking for a job just having graduated University of Rochester.