Validate cyclic organization unit

Question

I have a object Organization Unit and I have a self reference to it in the same object

public class OrganizationUnit: IOrganizationUnit  {

        private string fName;

        public string Name {
            get { return fName; }
            set { SetPropertyValue("Name", ref fName, (string) value); }
        }



        private OrganizationUnit fManagedBy;

        public IOrganizationUnit ManagedBy {
            get { return fManagedBy; }
            set {

                SetPropertyValue("ManagedBy", ref fManagedBy, (OrganizationUnit)value);
            }
        }


}

I need a method that will throw an exception if it finds a child organization unit in the third level is referencing a parent Organization unit, or to say cyclic parent organization.

• A is main B managed by A C cannot be managed by A

Answer 1

Walk the graph and keep a history of visited nodes. If you visit a node again, you've detected a cycle:

void CheckCycles(IOrganizationUnit unit)
{
    var visited = new HashSet<IOrganizationUnit>();

    for (var current = unit; current != null; current = current.ManagedBy)
    {
        if (!visited.Add(current))
        {
            throw new Exception(); // cycle detected
        }
    }
}