How to I sort this hierarchical list?

Question

The problem

I've got an unordered List<Item>, where each Item can point to another Item in the list by a unique ID.

I want to sort the list so that each Item is followed by the Item to which it points.

Initializing the list

public class Item {
    public string ID {get;set;}
    public string nextID {get;set;}
}

void Main()
{

    var items = new List<Item>();

    items.Add(new Item  { ID = "X", nextID = "" });
    items.Add(new Item  { ID = "A", nextID = "D" });
    items.Add(new Item  { ID = "C", nextID = "B" });
    items.Add(new Item  { ID = "E", nextID = "" });
    items.Add(new Item  { ID = "B", nextID = "A" });    
    items.Add(new Item  { ID = "D", nextID = "" });         

    SortItems(items);

    // should result in Items with IDs in this order: ["X","E","C","B","A","D"]

}

Answer 1

Using the topological sort function TSort() from this answer, I wrote the following function to sort to my specifications:

public List<Item> sortItems(List<Item> items) {

    // perform a topological sort
    var sortedItems = 
        items.TSort(item => items.Where(o=>item.ID == o.nextID || item.nextID == ""))
        .ToList();

    // this next code moves the unpointed items to top of list

    // find items that are not pointed to, and do not point to any other item
    var soloItems= 
        sortedItems.Where(o => !sortedItems.Where(p => p.nextID == o.ID).Any() && o.nextID == "").ToList();

    // reverse the soloItems list so they
    // to appear in the same order in which 
    // they were found in unsorted list
    soloItems.Reverse();    

    // move the soloItems from the bottom of sortedItems to the top of sortedItems
    sortedItems.RemoveAll(o => soloItems.Contains(o));
    sortedItems.InsertRange(0,soloItems);

    return sortedItems;     

}

Answer 2

Interesting problem. At first I wondered if it would be possible using a simple Linq query construction with some selector delegates, but that gets messy quite quickly.

The below simple linq construction gets you part of the way, but really requires use and propagation of counts and original input order as well.

// Simple Linq, but just not good enough
// Need to also propagate original input order and count the number of siblings
Func<IEnumerable<Item>, Item, IEnumerable<Item>> SelectSuccessors = (set, item) => set.Where(i => i.ID == item.nextID);
Func<IEnumerable<Item>, IEnumerable<Item>, IEnumerable<Item>> Flatten = null;
Flatten = (set, sibblingPool) => set
    .SelectMany(i => new[] { i }.Concat(Flatten(SelectSuccessors(sibblingPool.Except(set), i), sibblingPool.Except(set))));
var unparented = items.Where(i => !items.Any(n => n.nextID == i.ID));
foreach (var item in Flatten(unparented, items))
    Console.WriteLine(item.ID);

Its result is ["X", "C", "B", "A", "D", "E"]

A very different type of construction is to really capture the recursive structure of this problem, in a self recursive data structure:

public class ItemHierarchy : Tuple<Item, int, List<ItemHierarchy>>
{
    public static List<ItemHierarchy> BuildHierarchy(IEnumerable<Item> items)
    {
        var inputOrderNumbered = items.Select((item, order) => Tuple.Create(item, order));
        var roots = inputOrderNumbered.Where(i => !items.Any(n => n.nextID == i.Item1.ID));
        return roots.Select(r => BuildFor(r.Item1, r.Item2, inputOrderNumbered.Except(roots))).ToList();
    }

    public Item Item 
    { 
        get { return this.Item1; } 
    }
    public int OriginalInputOrder
    {
        get { return this.Item2; }
    }
    public int NumberOfDescendents
    {
        get { return this.Item3.Count + this.Item3.Sum(i => i.NumberOfDescendents); }
    }
    public IEnumerable<Item> Flattened
    {
        get { return new[] { this.Item }.Concat(Descendents); }
    }
    public List<ItemHierarchy> DescendentHierarchy
    {
        get { return this.Item3; }
    }
    public IEnumerable<Item> Descendents
    {
        get { return this.Item3.SelectMany(i => new [] { i.Item }.Concat(i.Descendents)); }
    }
    public IEnumerable<Item> Leafs
    {
        get
        {
            if (NumberOfDescendents == 0)
                return new[] { this.Item };
            else
                return DescendentHierarchy.SelectMany(d => d.Leafs);
        }
    }
    protected ItemHierarchy(Item item, int originalOrder, IEnumerable<Tuple<Item, int>> descendents, IEnumerable<Tuple<Item, int>> remaining)
        : base(item, originalOrder, descendents.Select(d => BuildFor(d.Item1, d.Item2, remaining)).ToList())
    {
    }

    private static ItemHierarchy BuildFor(Item item, int originalOrder, IEnumerable<Tuple<Item, int>> numberedSiblings)
    {
        var descendents = numberedSiblings.Where(s => s.Item1.ID == item.nextID);
        return new ItemHierarchy(item, originalOrder, descendents, numberedSiblings.Except(descendents));
    }
}

Which can then be used to solve the problem you posed as:

// This works quite well.
// As a bonus it preserves the original input information 
// and offers a navigatable/queryable hierarchy.
var hierarchy = ItemHierarchy.BuildHierarchy(items);
foreach (var item in hierarchy.OrderBy(r => r.NumberOfDescendents).ThenBy(r => r.OriginalInputOrder).SelectMany(r => r.Flattened))
    Console.WriteLine(item.ID);