toposort.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

//https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search


namespace Brainworks.ClassLib {

  public interface IObjectWithParent<K> where K:struct {
    K ID { get; }

    K? Parent { get; }
  }

  enum NodeMark { None, Temporary, Permanent }

  public class TopoSortNode<T> {

      readonly T mItem;

      public T Item {
        get { return mItem; }
      }


      List<TopoSortNode<T>> mDescendants = new List<TopoSortNode<T>>();

      public List<TopoSortNode<T>> Descendants {
        get { return mDescendants; }      
      }

      NodeMark mMark;

      internal NodeMark Mark {
        get { return mMark; }        
      }

      public TopoSortNode(T item) {
        mItem = item;
      }

      internal string Visit(List<TopoSortNode<T>> sortResult) {
        if(mMark==NodeMark.Permanent) {
          return null;
        }
        if(mMark==NodeMark.Temporary) {
          return "strLoopInDependencies";
        }
        mMark = NodeMark.Temporary;

        foreach(var desc in mDescendants) {
          var result = desc.Visit(sortResult);
          if(result!=null) {
            return result;
          }
        }
        mMark = NodeMark.Permanent;
        sortResult.Add(this);
        return null;
      }

  }


  public static class SortUtils {

    public const string strLoopInDependencies = "strLoopInDependencies";

    public const string strParentNotFound = "strParentNotFound";

    /// <summary>
    /// Sorts items in reverse topological order (leafs first, roots last), with error detection
    /// </summary>
    /// <typeparam name="K">Item ID type</typeparam>
    /// <typeparam name="T">Item type</typeparam>
    /// <param name="items">Items list</param>
    /// <returns>Tuple of (sorted node list, null, null) or (null, error string, error item) </returns>
    public static Tuple<List<TopoSortNode<T>>, string, T> TopoSortReverse<K,T>(List<T> items) where K:struct where T:IObjectWithParent<K> {
      Dictionary<K, TopoSortNode<T>> nodes = items.ToDictionary(item => item.ID, item => new TopoSortNode<T>(item));
      foreach(var kv in nodes) {

        if(kv.Value.Item.Parent.HasValue) {
          TopoSortNode<T> node;
          if(!nodes.TryGetValue(kv.Value.Item.Parent.Value, out node)) {
            return new Tuple<List<TopoSortNode<T>>, string, T>(null, strParentNotFound, kv.Value.Item);
          }
          node.Descendants.Add(kv.Value);
        }
      }

      List<TopoSortNode<T>> sortResult = new List<TopoSortNode<T>>();
      foreach(var kv in nodes) {
        if(kv.Value.Mark!=NodeMark.None) {
          continue;
        }
        var result = kv.Value.Visit(sortResult);
        if(result!=null) {
          return new Tuple<List<TopoSortNode<T>>, string, T>(null, result, kv.Value.Item);
        }
      }

      return new Tuple<List<TopoSortNode<T>>, string, T>(sortResult, null, default(T));

    }

  }
}