Как узнать, был ли раунд вызван родителями (A => B => C => A)

Question

У меня есть следующая структура:

[Employee]
ID
Manager1ID
Manager2ID

Сценарий:

Я хочу сделать проверку, чтобы убедиться, что выбранный Manager1 или Manager2 не вызывает раунд. Другими словами, я хочу знать, существует ли этот случай:

Менеджер A - это B, а менеджер B - это C, а менеджер C - также A // недействителен

A => B => C => A

Чтобы сообщить пользователю, что A не является действительным менеджером для C , потому что C уже является менеджером A .

---

Проблема:

Я хотя бы проверял во время зацикливания менеджеров как родителей в дереве, и когда я нашел выбранного менеджера в списке, я понял, что он недействителен. (Две петли для списков буксировки для Manager1 и Manager2)

Проблема в том, что у каждого сотрудника может быть два менеджера, и в таком случае может существовать раунд:

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

Который не может проверить в моем предложенном решении.

Любая идея!

Answer 1

Вы пытаетесь найти цикл в ориентированном графе .

Answer 2

Я предоставил полное общее решение для n числа репортеров, что более логично, чем репортажи. Если вы хотите переименовать репортеров в менеджеров, вы можете сделать это. Вы можете изменить обход в соответствии с вашими потребностями. Я проверил это с циклом и без цикла. Вроде нормально работает. Дайте мне знать, если это работает для вас.

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 3

, начиная с рассматриваемого сотрудника, сначала выполните поиск по множеству менеджеров и продолжайте накапливать список менеджеров, с которыми вы сталкиваетесь в списке. Каждый раз, когда вы добавляете запись в список, проверяйте, не создаст ли она дублирование. Если это так, значит, вы достигли состояния, которое хотели проверить. Продолжайте этот процесс, пока не достигнете условия дублирования или не достигнете узла, у которого нет менеджеров

Answer 4

Используйте рекурсивную функцию:

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 5

Используйте следующую рекурсивную функцию:

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))
    );

}