HIerarchical Data representation using LINQ

Question

All,I was trying to comeup with a hierarchical data representation of the following class using LINQ.Can anyone please help me out

public class Employee
    {
       public Employee(int empId,int? managerId)
       {
           this.Id = empId;
           this.MangerId = managerId;
           this.Children = new List<Employee>();
       }
        public int Id { get; set; }
        public int? MangerId { get; set; }
        public string EmployeeName { get; set; }
        public List<Employee> Children { get; set; }
    }

Sample Data

var empList = new List<Employee>
             {
                 new Employee(1,2){EmployeeName = "Joseph"},
                 new Employee(2,3){EmployeeName = "Smith"},                 
                 new Employee(3,4){EmployeeName = "Bob"},
                 new Employee(4,null){EmployeeName = "Doug"},
                 new Employee(5,2){EmployeeName = "Dave"},
                 new Employee(6,4){EmployeeName = "Allan"}
             };

and the output should be like this

/* Doug Bob Allan Smith Joseph Dave

*/

Any help would be greatly appreciated

edit: The top employee will have a managerId of null

Answer 1

Using your model, the Employee models are not directly linked to themselves. Instead, we must use their identifier to walk the hierarchy.

First, we get the root employee:

var rootEmp = EmpList.Single(e => e.MangerId == null);

Then, we walk the hierarchy using a recursive function:

string WalkEmployees(Employee root)
{
    // Create the container of the names
    var builder = new StringBuilder();

    // Get the children of this employee
    var children = EmpList.Where(e => e.MangerId == root.Id);

    // Add the name of the current employee in the container
    builder.Append(root.EmployeeName + " ");

    // For each children, walk them recursively
    foreach (var employee in children)
    {
        builder.Append(WalkEmployees(employee));
    }

    // Return the container of names
    return builder.ToString();
}

Finally, we call the function:

WalkEmployees(rootEmp);

By essence, recursive functions walk the hierarchy vertically:

Doug
- Bob
- - Smith
- - Joseph
- - Dave
- Allan

Nonetheless, you expect an horizontal walk in order to get Allan right after Bob. For that purpose, I added a view model for your employees, that describes their level in the hierarchy.

public class EmployeeViewModel
{
    public EmployeeViewModel(Employee employee, int level)
    {
        Employee = employee;
        Level = level;
    }

    public Employee Employee { get; set; }
    public int Level { get; set; }
}

The function to walk the employees becomes:

IEnumerable<EmployeeViewModel> WalkEmployees(Employee root, int level)
{
    // Create the container of the employees
    var container = new List<EmployeeViewModel> {new EmployeeViewModel(root, level)};

    // Get the children of this employee
    var children = EmpList.Where(e => e.MangerId == root.Id);

    // For each children, walk them recursively
    foreach (var employee in children)
    {
        container.AddRange(WalkEmployees(employee, level + 1));
    }

    // Return the container
    return container;
}

and its call:

var rootEmp = EmpList.Single(e => e.MangerId == null);

var employees = WalkEmployees(rootEmp, 0);

// Order the employees by its level in the hierarchy
var orderedEmployees = employees.OrderBy(vm => vm.Level);

// Display the names
foreach (var orderedEmployee in orderedEmployees)
{
    Console.Write(orderedEmployee.Employee.EmployeeName + " ");
}

you get this result:

Doug
- Bob
- Allan
- - Smith
- - Joseph
- - Dave

Bonus

your model is quite hard to handle, due to the lack of link between the models. Here is a suggestion for a stronger one:

public class Employee
{
    #region Constructors
    public Employee()
    {
        Employees = new List<Employee>();
    }

    public Employee(string name) : this()
    {
        Name = name;
    }

    public Employee(string name, Employee manager) : this(name)
    {
        Manager = manager;
    }

    public Employee(string name, Employee manager, params Employee[] employees) : this(name, manager)
    {
        Employees.AddRange(employees);
    }
    #endregion

    #region Properties
    public List<Employee> Employees { get; set; }
    public int Id { get; set; }
    public Employee Manager { get; set; }
    public string Name { get; set; }
    #endregion
}

You can now generate your employees like that:

/// <summary>
/// Generates the employees in a hierarchy way.
/// </summary>
/// <returns>Returns the root employee.</returns>
Employee GenerateEmployees()
{
    var doug = new Employee("Doug");
    doug.Employees.Add(new Employee("Allan", doug));

    var bob = new Employee("Bob", doug);
    doug.Employees.Add(bob);

    var smith = new Employee("Smith", bob);
    bob.Employees.Add(smith);

    smith.Employees.Add(new Employee("Joseph", smith));
    smith.Employees.Add(new Employee("Dave", smith));

    return doug;
}

And your walk function becomes:

string WalkEmployees(Employee root)
{
    var builder = new StringBuilder();

    builder.Append(root.Name + " ");

    foreach (var employee in root.Employees)
    {
        builder.Append(WalkEmployees(employee));
    }

    return builder.ToString();
}

This implementation makes more sense if you use EntityFramework to design a database using the navigation properties.

Answer 2

Try:

string text = string.Join(" ",
    from i in empList
    orderby i.MangerId.HasValue, i.MangerId descending
    select i.EmployeeName);