HierarchicalOrderByExtensions.cs

using QuickGraph;
using QuickGraph.Algorithms;
using System.Collections.Generic;
using System.Linq;

namespace NA.Linq.Extensions
{
    public static class HierarchicalOrderByExtensions
    {
        public delegate bool IsDescendantAncestorRelationDelegate<T>(T descendantCandidate, T ancestorCandidate);

        public static IEnumerable<T> HierarchicalOrderBy<T>(this IReadOnlyCollection<T> items, IsDescendantAncestorRelationDelegate<T> relationPredicate)
        {
            var graph = new BidirectionalGraph<T, Edge<T>>(allowParallelEdges: false);
            graph.AddVertexRange(items);
            graph.AddEdgeRange(items
                    .SelectMany(item1 => items
                        .Where(item2 => !Equals(item1, item2) && relationPredicate(item1, item2))
                        .Select(item2 => new Edge<T>(item1, item2))));
            var reducedGraph = graph.ComputeTransitiveReduction();
            reducedGraph.AddVertexRange(graph.Roots()); // fixup to add vertices without edges
            var sorted = reducedGraph.TopologicalSort();
            return sorted;
        }
    }
}