How to know whether there is a round has been caused by parents (A=>B=>C=>A)

Question

I have the following structure:

[Employee]
ID
Manager1ID
Manager2ID

Scenario:

I want to make a validation to ensure that the chosen Manager1 or Manager2 does not cause a round. In other words, I want to know whether this case exists:

The manager of A is B & the manager of B is C and the manger of C is also A // not valid

A => B => C => A

To tell the user that A is not a valid manager for C because C is already a manager of A .

---

The problem:

I though of checking in a while loop the managers as parents in a tree, and when I found the chosen manager in the list I know that it is not valid. (Two loops for tow lists for Manager1 and Manager2)

The problem is that every employee might have two managers and a round maybe exists in a case like this:

A => B (Manager1) => C (Manager2) => A

Which is not able to check in my suggested solution.

Any idea!

Answer 1

You try to find a cycle in a directed graph.

Answer 2

Use a recursive function:

List<Employee> lineage = new List<Employee>();
Validate(theUser, lineage);

public void Validate(Employee employee, List<Employee> lineage)
{
  if (lineage.Contains(employee))
     throw new InvalidOperationException("Circular graph");

  lineage.Add(employee);

  if (employee.Manager != null)
    Validate(employee.Manager, lineage)
}

Answer 3

starting from the employee in question, do a breadth first search on the set of managers and keep accumulating the list of managers you come across in a list. Each time you add an entry to the list, check if it would create a duplication. If it would, it means you have reached the condition you wanted to check for. Keep continuing this process until you either hit a duplication condition or you reach a node which does not have managers

Answer 4

I have provided a complete generic solution for n number of reportees which is more logical than reportees. If you like to rename reportees to managers, you can do so. You can modify the traversal to suit your needs. I have tested this with cycle and without cycle. It seems to work fine. Let me know if this works for you.

using System;
using System.Collections.Generic;


namespace GenericDictionary
{
    class Program
    {
        static void Main(string[] args)
        {
            Employee employee = new Employee("Employee", null);
            Employee manager = new Employee("Manager", employee);
            Employee CEO = new Employee("CEO", manager);
            CEO.AddReportee(new Employee("Manager2", employee));

            // Uncomment this line to see exception in action
            // employee.AddReportee(CEO);
            try
            {
                CEO.DisplayReportees();
            }
            catch (InvalidOperationException ex)
            {
                Console.WriteLine();
                Console.WriteLine("***** Exception: " + ex.Message + " *****");
            }

            Console.ReadLine();
        }

        public class Employee
        {
            public List<Employee> Reportees { get; private set; }
            public string Name { get; private set; }
            public Employee(string name, Employee reportee)
            {
                this.Reportees = new List<Employee>();
                this.Name = name;
                this.Reportees.Add(reportee);
            }
            public void AddReportee(Employee reportee)
            {
                Reportees.Add(reportee);
            }
            int indentationCount = 0;
            List<Employee> traversedNodes = new List<Employee>();
            void DisplayReportees(Employee employee)
            {
                traversedNodes.Add(employee);
                for (int i = 0; i < indentationCount; i++)
                    Console.Write(" ");
                Console.WriteLine(employee.Name);
                indentationCount = indentationCount + 3;

                foreach (Employee reportee in employee.Reportees)
                {
                    if (AlreadyTraversed(reportee))
                        throw new InvalidOperationException("Circular graph at node " + reportee.Name);
                    if (reportee != null)
                        DisplayReportees(reportee);
                }
                indentationCount = indentationCount - 3;
                traversedNodes.Remove(employee);
            }

            bool AlreadyTraversed(Employee employee)
            {
                return traversedNodes.Contains(employee);
            }

            public void DisplayReportees()
            {
                DisplayReportees(this);
            }
        }
    }
}

Answer 5

Use the following recursive function:

Boolean CheckManagers(Employee emp)
{

    if ((emp.Manager1ID.HasValue && emp.Manager1ID == emp.ID) ||
       (emp.Manager2ID.HasValue && emp.Manager2ID == emp.ID)) return false;

    return 
    (
        (!emp.Manager1ID.HasValue || (emp.Manager1ID.HasValue && CheckManagers((Employee) emp.Manager1)) && 
        (!emp.Manager2ID.HasValue || (emp.Manager2ID.HasValue && CheckManagers((Employee) emp.Manager2))
    );

}