问基于约束的数组对象排序算法

EN

const int OBJECT_NUM = 10;

void Main()
{
    Random r = new Random(12345);
    var objects = new List<MyClass>();
    for (int index = 1; index <= OBJECT_NUM; index++)
    {
        var mc = new MyClass { Id = index, IsLarge = (r.Next(100) < 50) };
        objects.Add(mc);
    }
    for (int index = 0; index < objects.Count; index++)
    {
        var temp = new List<MyClass>();
        for (int index2 = index + 1; index2 < objects.Count; index2++)
            if (r.Next(100) < 10 && index2 != index)
                temp.Add(objects[index2]);
        objects[index].ObjectsBehind = temp.ToArray();
    }

    objects.Select(o => o.ToString()).Dump("unsorted");
    objects = LargeTopoSort(objects).ToList();
    objects.Select(o => o.ToString()).Dump("sorted");
}

public static IEnumerable<MyClass> LargeTopoSort(IEnumerable<MyClass> input)
{
    var inboundLinkCount = new Dictionary<MyClass, int>();
    var inputArray = input.ToArray();

    // the hash set initially contains all the objects
    // after the first loop here, it will only contain objects
    // that has no inbound links, they basically have no objects
    // that comes before them, so they are "first"
    var objectsWithNoInboundLinks = new HashSet<MyClass>(inputArray);

    foreach (var source in inputArray)
    {
        int existingInboundLinkCount;

        foreach (var target in source.ObjectsBehind)
        {
            // now increase the number of inbound links for each target
            if (!inboundLinkCount.TryGetValue(target, out existingInboundLinkCount))
                existingInboundLinkCount = 0;
            existingInboundLinkCount += 1;
            inboundLinkCount[target] = existingInboundLinkCount;

            // and remove it from the hash set since it now has at least 1 inbound link
            objectsWithNoInboundLinks.Remove(target);
        }
    }

    while (objectsWithNoInboundLinks.Count > 0)
    {
        // all the objects in the hash set can now be dumped to the output
        // collection "at the same time", but let's order them first

        var orderedObjects =
            (from mc in objectsWithNoInboundLinks
             orderby mc.IsLarge descending, mc.Id
             select mc).ToArray();

        foreach (var mc in orderedObjects)
            yield return mc;

        // prepare for next "block" by clearing the hash set
        // and removing all links from the objects we just output
        objectsWithNoInboundLinks.Clear();

        foreach (var source in orderedObjects)
        {
            foreach (var target in source.ObjectsBehind)
            {
                if (--inboundLinkCount[target] == 0)
                {
                    // we removed the last inbound link to an object
                    // so add it to the hash set so that we can output it
                    objectsWithNoInboundLinks.Add(target);
                }
            }
        }
    }
}

public class MyClass
{
    public int Id; // for debugging in this example
    public MyClass[] ObjectsBehind;
    public bool IsLarge;

    public override string ToString()
    {
        return string.Format("{0} [{1}] -> {2}", Id, IsLarge ? "LARGE" : "small", string.Join(", ", ObjectsBehind.Select(o => o.Id)));
    }
}

unsorted 
1 [LARGE] -> 5 
2 [LARGE] ->  
3 [small] ->  
4 [small] -> 7 
5 [small] ->  
6 [small] ->  
7 [LARGE] ->  
8 [small] ->  
9 [LARGE] -> 10 
10 [small] ->  


sorted 
1 [LARGE] -> 5 
2 [LARGE] ->  
9 [LARGE] -> 10 
3 [small] ->  
4 [small] -> 7 
6 [small] ->  
8 [small] ->  
7 [LARGE] ->  
5 [small] ->  
10 [small] ->