How to get extreme leaf node against heights parent in self referencing linq

user_4042141 0
Viewed 94

I having the data structure 

-Emp1 - Emp1_1 - Emp1_1_1
               - Emp1_1_2
      - Emp1_2 - Emp1_2_1
               - Emp1_2_2
-Emp2 - Emp2_1 - Emp2_1_1
               - Emp2_1_2
      - Emp2_2 - Emp2_2_1
               - Emp2_2_2

I want a dictionary which hold extreme leaf node as key and its highest parent as value. OP:

(Emp1_1_1, Emp1) (Emp1_1_2, Emp1) (Emp1_2_1, Emp1) (Emp1_2_2, Emp1) (Emp2_1_1, Emp2) (Emp2_1_2, Emp2) (Emp2_2_1, Emp2) (Emp2_2_2, Emp2)

(Emp1_1_1, Emp1)
(Emp1_1_2, Emp1) 
(Emp1_2_1, Emp1)
(Emp1_2_2, Emp1)
(Emp2_1_1, Emp2)
(Emp2_1_2, Emp2)
(Emp2_2_1, Emp2)
(Emp2_2_2, Emp2)

Below is c# code

public class Program
    {
        public static void Main()
        {
            var program = new Program();
            var empList = program.GetData();
           //Some linq which return the expected dictionary.
            Console.WriteLine("Press any key to exit");
            Console.ReadKey();
        }

        public class Employee
        {
            public int Id { get; set; }
            public string Name { get; set; }
            public int parentEmployee { get; set; }
            public List<Employee> childList { get; set; }
        }

        List<Employee> GetData()
        {
            var empList = new List<Employee>();

            var emp1 = new Employee() { Id = 1, Name = "Emp1_Name", childList = new List<Employee>() };
            var emp1_1 = new Employee() { Id = 2, Name = "Emp1_1_Name", parentEmployee = emp1.Id, childList = new List<Employee>() };
            var emp1_2 = new Employee() { Id = 3, Name = "Emp1_2_Name", parentEmployee = emp1.Id, childList = new List<Employee>() };
            emp1.childList.Add(emp1_1);
            emp1.childList.Add(emp1_2);
            var emp1_1_1 = new Employee() { Id = 4, Name = "Emp1_1_1_Name", parentEmployee = emp1_1.Id };
            var emp1_1_2 = new Employee() { Id = 5, Name = "Emp1_1_2_Name", parentEmployee = emp1_1.Id };
            emp1_1.childList.Add(emp1_1_1);
            emp1_1.childList.Add(emp1_1_2);
            var emp1_2_1 = new Employee() { Id = 6, Name = "Emp1_2_1_Name", parentEmployee = emp1_2.Id };
            var emp1_2_2 = new Employee() { Id = 7, Name = "Emp1_2_2_Name", parentEmployee = emp1_2.Id };
            emp1_2.childList.Add(emp1_2_1);
            emp1_2.childList.Add(emp1_2_2);



            var emp2 = new Employee() { Id = 1, Name = "emp2_Name", childList = new List<Employee>() };
            var emp2_1 = new Employee() { Id = 2, Name = "emp2_1_Name", parentEmployee = emp2.Id, childList = new List<Employee>() };
            var emp2_2 = new Employee() { Id = 3, Name = "emp2_2_Name", parentEmployee = emp2.Id, childList = new List<Employee>() };
            emp2.childList.Add(emp2_1);
            emp2.childList.Add(emp2_2);
            var emp2_1_1 = new Employee() { Id = 4, Name = "emp2_1_1_Name", parentEmployee = emp2_1.Id };
            var emp2_1_2 = new Employee() { Id = 5, Name = "emp2_1_2_Name", parentEmployee = emp2_1.Id };
            emp2_1.childList.Add(emp2_1_1);
            emp2_1.childList.Add(emp2_1_2);
            var emp2_2_1 = new Employee() { Id = 6, Name = "emp2_2_1_Name", parentEmployee = emp2_2.Id };
            var emp2_2_2 = new Employee() { Id = 7, Name = "emp2_2_2_Name", parentEmployee = emp2_2.Id };
            emp2_2.childList.Add(emp2_2_1);
            emp2_2.childList.Add(emp2_2_2);

            empList.Add(emp1);
            empList.Add(emp2);
            return empList;
        }
    }

I tried some solution like calling private self referencing function in linq, But it works for a one parent - one child relation.

linq c#
2 Answers

If the use of a recursive function is acceptable:

        Func<IEnumerable<Employee>, IEnumerable<Employee>> flatten = null;
        flatten = (IEnumerable<Employee> employees) => 
            employees.SelectMany(c => c.childList != null ? flatten(c.childList) : Enumerable.Empty<Employee>()).Concat(employees);

        var dict = (
            from topNode in empList
                    from node in flatten(topNode.childList)
                    where node.childList == null || node.childList.Count == 0
                    select new KeyValuePair<string, string>(node.Name, topNode.Name)
            ).ToDictionary(kv => kv.Key, kv => kv.Value);


        foreach(var keyValuePair in dict)
        {
            Console.WriteLine($"Key={keyValuePair.Key}, Value={keyValuePair.Value}");
        }

This outputs:

Key=Emp1_1_1_Name, Value=Emp1_Name
Key=Emp1_1_2_Name, Value=Emp1_Name
Key=Emp1_2_1_Name, Value=Emp1_Name
Key=Emp1_2_2_Name, Value=Emp1_Name
Key=emp2_1_1_Name, Value=emp2_Name
Key=emp2_1_2_Name, Value=emp2_Name
Key=emp2_2_1_Name, Value=emp2_Name
Key=emp2_2_2_Name, Value=emp2_Name
user_56826080

try this

public static void Main()
{
    var program = new Program();
    var empList = program.GetData();

    Func<IEnumerable<Employee>, Employee, Dictionary<Employee, Employee>> TreeToDict = null;
    TreeToDict = (employees, topParent) => 
    employees.SelectMany(e => 
                         {
                             if(e.childList != null)
                             {
                                 return TreeToDict(e.childList, topParent == null ? e : topParent);
                             }
                             else
                             {
                                 Dictionary<Employee, Employee> dict = new Dictionary<Employee, Employee>();
                                 dict.Add(e, topParent == null ? e : topParent);
                                 return dict;
                             }

                         }).ToDictionary(x => x.Key, x => x.Value);

    foreach(var emp in TreeToDict (empList, null))
    {
        Console.WriteLine("key : {0}, value {1}", emp.Key.Name, emp.Value.Name);
    }
}

result

key : Emp1_1_1_Name, value Emp1_Name
key : Emp1_1_2_Name, value Emp1_Name
key : Emp1_2_1_Name, value Emp1_Name
key : Emp1_2_2_Name, value Emp1_Name
key : emp2_1_1_Name, value emp2_Name
key : emp2_1_2_Name, value emp2_Name
key : emp2_2_1_Name, value emp2_Name
key : emp2_2_2_Name, value emp2_Name
user_63383370
Related