Prevent a self-referencing table from becoming circular in c#

Question

Here @mellamokb explained how to create a constraint prevents circular dependency.

I will need to implement the same in C#. I believe this requires a sort of recursive function but I can't get my head around of it.

I have a table as below:

Managers UserId | ManagerId

An example:

UserId | ManagerId
1         2
2         1

This is allowed. Users can be manager of each other

However:

UserId | ManagerId
1         2
2         3
3         1

This is not allowed.

I tried the following:

 private Manager CheckCircularDependency(int userId)
    {
        var managers = Managers.GetByManagersId(userId);
        if(managers==null || managers.Count == 0)
        {
            return null;
        }

        foreach (Manager manager in managers)
        {
             var man= CheckCircularDependency(manager.UserId);
            if (man== null)
            {
                return manager;
            }
        }

        return null;
    }

here is the checking:

public boid  AddManager(int userId, int managerId){

 var manager= CheckCircularDependency(userId);
  if (manager!= null)
            {
                if (manager.ManagerId == userId && manager.UserId == managerId)
                {
                    //this is allowed
                }else if(manager.ManagerId != userId){
                  throw new InvalidOperationException(" Not allowed");
                 }
            }
}

I have in the table:

1   2
2   3

When I try to insert another manager as 3 => 1 I should get exception but I don't. the recursive always return null instead of return user 1.

Any idea why?

Jason G. · Accepted Answer

A circular dependency can occur at any level or branch within the recursive tree not just the bottom level. Currently as soon as you reach the bottom or a user without any managers your recursive function will return without going through the rest of the managers in your foreach. Instead I would change you recursive function to indicate whether or not the combination of UserId and ManagerId will create a circular dependency. Then you can return true as soon as you find a conflict or false if no conflict is found within any branch or level. See example:

private bool CheckCircularDependency(int userId, int managerId, bool rootNode = false)
{
    //Optional: A user may not manage themselves
    if(userId == managerId && rootNode) return true;

    var managers = Managers.GetByManagersId(userId);
    if(managers == null || managers.Count == 0)
    {
        //User is not managing anyone therefore no conflict
        return false;
    }

    foreach (Manager manager in managers)
    {
        //Circular dependency, unless they are managers of each other
        if(manager.UserId == managerId && !rootNode) return true;

         var circularDependency = CheckCircularDependency(manager.UserId, managerId);
        if (circularDependency)
        {
            return true;
        }
    }

    //No conflicts found
    return false;
}

Add method:

public void AddManager(int userId, int managerId)
{
    if(CheckCircularDependency(userId, managerId, true))
    {
        throw new InvalidOperationException(" Not allowed");
    }
    else
    {
        //this is allowed
    }
}

This example assumes Manager.GetByManagersId(userId) returns all records where userId is in the ManagerId column.

Working example at https://dotnetfiddle.net/Jc6tfY with output:

Adding manager 1 => 2 : Success!
Adding manager 2 => 3 : Success!
Adding manager 2 => 1 : Success!
Adding manager 3 => 1 : Not allowed

Prevent a self-referencing table from becoming circular in c#

Answers (2)

Related Questions