Sorting multiple collections of objects by looking at each object's own path

Question

This is my code problem and it's killing me. I can't figure out how to do this ... I find myself creating temp arrays to hold references, loops in loops.. it's a mess.

The setup

Look at the image. We have 3 Something collections (layers) with cross-references between collections.

The goal is to order the Somethings as indicated by the arrows. However, C is more important than B who is more important than A (it's a bottom-up importance). A Something can change the natural order by following another Something in a different "Layer".

So the desired order is:

+----+----+----+---+---+---+---+---+----+----+----+---+---+---+---+
| 14 | 15 | 17 | 7 | 8 | 1 | 2 | 9 | 18 | 19 | 12 | 3 | 4 | 5 | 6 |
+----+----+----+---+---+---+---+---+----+----+----+---+---+---+---+

You will probably have to look a few times before you arrive at the same conclusion. Let me break it down for you.

We start in layer C (C outranks B and A, remember?) ... first column on the left is the start column. We have 14, 15 and 17. We don't want 18, because 18 does not have a reference back to 17. So we move up a layer and start at the beginning again with 7 and 8. It ends there, since 9 does not reference 8.

We move up one layer again and get 1 and 2.

Then it gets difficult -- 2 is followed by 9, so we get 9 first. Then we see that 9 is followed by 18, so we grab that one. Here is the important part -- C outranks B and A, so we first get 19, then go up to fetch 12 and then we go back to layer A to continue after 2 and get 3,4,5,6.

There must be some ingenieus way to do this and still keep it fast. This is a stripped down example. The real thing has dozens of objects and layers.

The real thing has a virtual propery that completes the 1-to-many relationship. I want to avoid that property, because it adds another collection to the mix, but in case it would make things easier I'll add that here.

class Something
{
  public int Id {get;set;}
  public int FollowsId {get;set;}
  public IEnumerable<Something> FollowedBy {get;set;}
}

I renamed the properties so it would be easier to grasp.

Answer 1

You can just treat this as a tree structure, and then just walk it left-to-right (or in your case, nodes directly linked from a sublayer prior to nodes from the same layer) ensuring to yield the current node before navigating sub-nodes...

Working code:

public class Layer
{
    public string Name { get; set; }
    public int Priority { get; set; }

    public Something Head { get; set; }
    public Something Add(Something s) { 
        if (this.Head == null) this.Head = s; 
        s.Layer = this; 
        this.Items.Add(s); 
        return s; 
    }
    public Something this[int id] { 
        get { return this.Items.SingleOrDefault(s => s.Id == id); } 
    }
    public List<Something> Items = new List<Something>();

    private void BuildTree(List<Something> list, Something s = null)
    {
        list.Add(s);
        foreach(Something ss in s.Followers.OrderBy(sss => sss.Layer.Priority))
        {
            BuildTree(list, ss);
        }
    }
    public List<Something> Tree
    {
        get 
        {
            List<Something> list = new List<Something>();
            if (this.Head != null) BuildTree(list, this.Head);
            return list;
        }
    }
}

public class Something
{
    public int Id { get; set; }
    public Layer Layer { get; set; }
    public List<Something> Followers = new List<Something>();
    public void Follows(Something s) { s.Followers.Add(this); }
}

void Main()
{
    Layer A = new Layer() { 
        Name="A", 
        Priority = 3
    };
    A.Add(new Something() { Id = 1 });
    A.Add(new Something() { Id = 2 }).Follows(A[1]);
    A.Add(new Something() { Id = 3 }).Follows(A[2]);
    A.Add(new Something() { Id = 4 }).Follows(A[3]);
    A.Add(new Something() { Id = 5 }).Follows(A[4]);
    A.Add(new Something() { Id = 6 }).Follows(A[5]);

    Layer B = new Layer() { 
        Name = "B",
        Priority = 2
    };
    B.Add(new Something() { Id = 7 });
    B.Add(new Something() { Id = 8 }).Follows(B[7]);
    B.Add(new Something() { Id = 9 }).Follows(A[2]);
    B.Add(new Something() { Id = 12 }).Follows(B[9]);

    Layer C = new Layer() {
        Name = "C",
        Priority = 1
    };
    C.Add(new Something() { Id = 14 });
    C.Add(new Something() { Id = 15 }).Follows(C[14]);
    C.Add(new Something() { Id = 17 }).Follows(C[15]);
    C.Add(new Something() { Id = 18 }).Follows(B[9]);
    C.Add(new Something() { Id = 19 }).Follows(C[18]);

    List<Something> orderedItems = new List<Something>();
    List<Layer> layers = new List<Layer>() { A, B, C };
    foreach(Layer l in layers.OrderBy(ll => ll.Priority)) orderedItems.AddRange(l.Tree);
}

If you run this in LinqPad, then after the last line, you can:

string.Join(",", orderedItems.Select(s => s.Id.ToString())).Dump();

to see the output:

14,15,17,7,8,1,2,9,18,19,12,3,4,5,6

Answer 2

What you're describing sounds a lot like a topological sort, with a few extra modifications. If you have a set of transitive constraints on a group of objects, then a topological ordering of the objects is one where the elements are listed out in an order where all of the constraints are satisfied. In your case, you have two different classes of constraints in play:

1. The explicit constraints that you've given above.
2. The implicit constraint that elements in group C precede elements in group B and elements in group B precede elements in group A whenever possible.

To explicitly convert this into a topological sorting problem, you can do the following. First, create a graph where each array cell is a node. Next, add in the explicit constraints that you already know about. Then, add in the implicit constraints by adding in edges from group A to group B and then from group B to group C. Finally, run a topological sorting algorithm - there are many of them, and they're very efficient - to get back a linearized ordering obeying all of your constraints.

I'm not actually a C# programmer and so I don't know the best way to actually code this up, but I suspect that there are good topological sorting libraries out there online. In the worst case, you should be able to code one up on your own; the DFS-based topological sorting algorithm is rather straightforward.

This approach assumes that, like in your picture, the "follows" relation never has something in a higher array following something in a lower array. If that's not the case, this setup might not work because you may get cycles in the graph. In that case, you can consider using a different approach where you use a normal topological sort, but whenever you have a choice about which node to include next in the topological ordering, you always choose the one from the deepest level.