Looking for a simple test for circular reference in a recursive model

Question

I have a model that represents an assembly that is made up of components, components may (in their own right) also be assemblies. It looks a little like this:

class Component < ActiveRecord::Base
  belongs_to :assembly, :class_name => "Component", :foreign_key => :assembly_id
  has_many :pieces, :class_name => "Component", :foreign_key => :assembly_id
end

I want to be certain that when I add a component to the assembly that what's being added isn't the assembly itself, or another assembly up the chain. Effectively, an assembly can't contain itself, regardless of how many levels down you go.

My thought is to traverse the tree going up when a component is saved to look for the component itself as a parent, grandparent, etc. I'm trying to avoid circular references.

Is there an "easy, Rails-ish" way to do this? Any other suggestions?

Answer 1

I don't know rails at all. However, it sounds like you've nearly answered your own question.

The question at hand naturally lends itself to a recursive solution.

You say that you already think of these assembly references as being a tree.

You have a single assembly as the root of the tree, and a list of branches as it's components.

You could have a function contains(Node, ListOfAssemblies) that returns true if and only if no node beneath Node contains any assembly in ListOfAssemblies. This function could recursively call itself until it gets to a leaf and returns.

You just need to work out (1) the logic of how this works and (2) how your components and assemblies will be represented in code.

Good luck!