algorithm: ordering objects in an array based on constraints

Question

I have a thousand objects of type MyClass

class MyClass{
    array<MyClass> objectsBehind;
    Boolean large;
}

Where objectsBehind is an array of MyClass objects and any of the objects in this array are all part of the 1000 original objects.

I place them in an array and sort them such that an object appears at a higher index in the array than the objects in its objectsBehind array. For example, an object at index 546 could not have any objects in it's objectsBehind array that have an index of above 546 in the sorted array.

My problem is this. Around 20 of the 1000 objects have the property large = true. It is beneficial to group these 'large' objects sequentially in the sorted array, provided the objectsBehind property is not violated. For example, it would be better to have this:

array[45].large = false; array[46].large = true, array[47].large = true, array[48].large = true, array[49].large = false;

than

array[45].large = true; array[46].large = false, array[47].large = true, array[48].large = false, array[49].large = true; 

In the first sequence, I have three large objects grouped together rather than having them spread out in the second example.

I can't think of a good way to do this. Any ideas?

Answer 1

This is probably easily done.

First, to sort the objects before all the objects in the objectsBehind array of each such object, you would use Topological Sort.

The topological sort will each main iteration place a number of elements into the output collection "at the same time".

These objects you sort by the large property, such that all the large objects comes first, followed by all the non-large objects. You probably want to add another sort criteria here so that you can rely on a known order inside the large objects and inside the non-large objects.

Basically, here's how topological sort works (the one I've learned):

1. Start by creating a couple of data structures to hold the "graph", ie. all the links between the objects:
   1. You'll need a dictionary that contains each object, and a list of all the objects it has links to (this is actually not needed in your case since each object has this built in in the objectsBehind property)
   2. You'll need a dictionary that contains each object that is linked to along with how many such links points to the object
   3. You'll need a hashset of all the objects that has no links to them (at the moment)
2. Fill these data structures accordingly
   1. Place all the objects in the hashset (as though they have no inbound links at all)
   2. Loop through all the objects that has links, we'll call this object iteration A
   3. Add the object (that has links from it) and all the links it has to the first dictionary (again, this is not needed for your objects)
   4. Adjust the second dictionary by increasing the number of inbound links for each link from the A object
   5. As you increase the number of inbound links for an object, remove the same object from the hashset (we now know it has at least one inbound link)
3. Start a loop that basically says "as long as I have something in the hashset", this will look at the hashset, which now contains all the objects that have no inbound links
4. In each loop iteration, first output all the objects in the hashset. This "comes first" of what is left. You want to order these to produce a stable sort. In your case I would order all the large objects first, followed by all the non-large objects.
5. Make a copy of the hashset, for enumeration purposes, and clear the hashset, preparing for the next loop iteration
6. Loop through all the objects in the copy, and for each object, loop through all outbound links from it, and for each link, reduce the number of inbound links on the target, in that second dictionary
7. When such a number, the number of inbound links to an object, reaches zero after being decreased, it means there are no longer any "live" links pointing to it, so add it to the hashset
8. Loop around (point 4 and onwards)

If, after point 8 and 4, you have no objects in the hashset, but there are objects in the second dictionary that has not reached zero inbound links, it means you have cycles in the graph, ie. something along "object 1 points to object 2, object 2 points to 3, and 3 points back to 1".

Here is one such solution, you can test this out in LINQPad.

Please note that there are many ways to do topological sort. For instance, this version here will take all the objects that have no objects before them, and output these at the same time. However, you could possibly group objects that come directly after some of these, directly after the object they come after, and still not violate any constraints.

As an example, check out the relationship between 4 and 7 in the code below (you'll have to run it).

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)));
    }
}

Output:

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] ->