# Directed Acyclic graph implementation in Ruby on Rails

I have an implementation for a graph node class that I'd like to have function as a directed acyclic graph.

The associations are roughly as follows

class Node
has_many :parents,
class_name: 'Edge',
foreign_key: :child_id

has_many :children,
class_name: 'Edge',
foreign_key: :parent_id
end

class Edge
belongs_to :parent, class_name: 'Node'
belongs_to :child, class_name: 'Node'

has_many :edge_properties
end


Me and a co-worker of mine had a discussion about the proper way to do this has_many relationship. The rails paradigm seems to dictate that node.parents should return a Node::ActiveRecord_Relation. However, in this case, node.parents returns a list of edges, which results the ask for the node's parents into something of the sort:

Node.where(id: Edge.where(child: node))


The question is; is this a code smell? Can we do this relationship better where node.parents would return Node::ActiveRecord? If so, how would one access edge.edge_properties?

• The rails paradigm seems to dictate that node.parents should return a Node::ActiveRecord_Relation. This has nothing to do with the Rails paradigm, a has_many can return whatever you need. node.parents should of course return nodes, not edges. For that, create node.incoming_edges, node.outgoing_edges or similar. – tokland Oct 28 '16 at 8:41
• Isn't what you said contradiction? Stating that it has nothing to do with the rails paradigm but then going on and saying that should of course return nodes, not edges?. I think we both can agree rails prefers a particular solution and that in itself is it's paradigm. – David Zhang Oct 28 '16 at 19:59
• I meant that it's graph terminology. A parent/child of a node is another node, not an edge. At least, AFAIK, I may be wrong. – tokland Oct 28 '16 at 20:53

You should take a look at the through: option of has_many:

class Node
has_many :parent_edges, class_name: "Edge", foreign_key: :child_id
has_many :parents, through: :parent_edges

# ditto for children
end


Getting at edge_properties depends on the version of Rails you are using.

• It seems that rails does not recognize the correct id on the edge class.  SELECT nodes.* FROM nodes INNER JOIN edges ON nodes.id = edges.parent_id WHERE edges.node_id = 16 ORDER BY node.name ASC  – David Zhang Oct 28 '16 at 0:54
• @DavidZhang You almost certainly need to specify additional options. I don't know them off the top of my head but there is plenty of documentation out there. – benzado Oct 28 '16 at 17:16