Finding unconnected sets

Question

I have a list of boxes, and wish to group them into unconnected sets of overlapping boxes. (Note that two boxes A and B may not overlap each other, but if they are both overlapped by a box C, they will still be grouped together).

The following works ok, but I feel like it could be made a lot more concise with LINQ, or possibly made faster.

private List<List<Box>> FindUnconnectedSets(List<Box> boxes)
{
    List<List<Box>> unconnectedSets = new List<List<Box>>();

    while (boxes.Count() != 0)
    {
        List<Box> set = new List<Box>();

        bool found = true;
        while (found)
        {
            found = false;

            foreach (Box newBox in boxes)
            {
                if (set.Count != 0)
                {
                    foreach (Box setBox in set)
                    {
                        if (newBox.Overlaps(setBox))
                        {
                            set.Add(newBox);
                            boxes.Remove(newBox);
                            found = true;
                            break;
                        }
                    }
                }
                else
                {
                    set.Add(newBox);
                    boxes.Remove(newBox);
                    found = true;
                }

                if (found)
                    break;
            }
        }

        unconnectedSets.Add(set);
    }

    return unconnectedSets;
}

Edit: added the Box class. It's not all that interesting really.

private class Box
{
    public Box(int xOrigin, int yOrigin, int size)
    {
        XOrigin = xOrigin;
        YOrigin = yOrigin;

        Size = size;
    }

    public int XOrigin;
    public int YOrigin;

    public int Size;

    public override string ToString()
    {
        string s = "Box: "
            + "(" + XOrigin.ToString() + ", " + YOrigin.ToString() + ")"
            + " " + Size.ToString();
        return s;
    }

    public bool Overlaps(Box b2)
    {
        if (XOrigin >= b2.XOrigin + b2.Size)
            return false;
        if (b2.XOrigin >= XOrigin + Size)
            return false;
        if (YOrigin >= b2.YOrigin + b2.Size)
            return false;
        if (b2.YOrigin >= YOrigin + Size)
            return false;

        return true;
    }
}

Comments welcome, both on the LINQifying side, and algorithm suggestions if you think I'm going about this the wrong way, as well as any other feedback. :)

Answer 1

I've made a first attempt at shortening and simplifying the code with LINQ. First, I created a helper method for moving items from one List to another based on this StackOverflow question.

private int MoveItemsWhere<T>(Func<T, bool> predicate, List<T> source, List<T> target)
{
    var selected = new HashSet<T>(source.Where(predicate));
    target.AddRange(selected);
    source.RemoveAll(selected.Contains);
    return selected.Count;
}

Then I modified the FindUnconnectedSets to use LINQ for finding overlapping boxes:

private List<List<Box>> FindUnconnectedSets(List<Box> boxes)
{
    var unconnectedSets = new List<List<Box>>();
    while (boxes.Count > 0)
    {
        var set = boxes.Take(1).ToList();
        boxes = boxes.Skip(1).ToList();

        int numAdded;
        do
        {
            numAdded = MoveItemsWhere(b => set.Any(s => s.Overlaps(b)), boxes, set);
        } while (numAdded > 0);

        unconnectedSets.Add(set);
    }
    return unconnectedSets;
}

Some notes on the above code:

• I'm using implicit declarations with var. Personal preference, but I find it a little cleaner than repeating long types like List<List<Box>>.
• I changed the criteria from a bool found to int numAdded because I think it's a little clearer about the purpose.
• The core LINQ logic is b => set.Any(s => s.Overlaps(b)); this looks up every item from boxes where any item in set overlaps with the box.

Answer 2

Since we are talking about sets, it's probably better to use collection types that represent a set: HashSet<T> and ISet<T>.

Another improvement you can make is to keep track of the boxes you've added to current set at the last iteration (horizon of your expansion), and try to match candidate boxes only with them.

Note that resulting solution doesn't use the knowledge about box matching logic, so it might be a good idea to extract the interface that defines the connection between elements (i.e. a method that checks for the presence of link between nodes).

As a result I've got the following solution:

public interface IConnected<in T>
{
    bool IsConnectedTo(T other);
}

public class Box: IConnected<Box>
{
    ....

    public bool IsConnectedTo(Box other)
    {
        return Overlaps(other);
    }
}

And the FindUnconnectedSets:

public static List<ISet<T>> FindUnconnectedSets<T>(IEnumerable<T> boxes) where T : IConnected<T>
{
    var remainingBoxes = new HashSet<T>(boxes);
    var unconnectedSets = new List<ISet<T>>();

    while (remainingBoxes.Count > 0)
    {
        var newBoxes = new[] { remainingBoxes.First() }; //on each iteration will contain newly added boxes to current set
        var currentSet = new HashSet<T>();
        unconnectedSets.Add(currentSet);

        do
        {
            currentSet.UnionWith(newBoxes);
            remainingBoxes.ExceptWith(newBoxes);
            newBoxes = remainingBoxes
                .Where(remainingBox => newBoxes.Any(setBox => setBox.IsConnectedTo(remainingBox)))
                .ToArray();
        } while (newBoxes.Length > 0);
    }

    return unconnectedSets;
}

Answer 3

The general approach seems fine; I couldn't think of a radically different algorithm - but LINQ does help indeed.

I used it to improve your code in two respects:

• The distinction between an empty list and one that contains elements overlapping the current box at the innermost level was executing the same code in both cases; using LINQ for the checks (especially replacing the foreach) allowed me to write this in a much more concise manner and remove the code duplication.
• The while-found-break kludge that was necessary because removing items from the target list of an iteration breaks the iterator was quite hard to fully wrap one's head around. This could be eliminated with a simple but effective trick: I iterate over a 'snapshot' copy of the boxes list while still removing the items from the original list. That prevents the iterator from breaking while still removing all the boxes from future checks that have already found their home (the ToList() call after the Select() query is very important for that to work). As a result, I only need to iterate through the current remaining boxes list once per set instead of needing to restart as many times as I find a box that belongs in the current set. Because I'm only removing items we've already left behind in the current iteration, that is not a problem for the correctness of the algorithm.

I also replaced the condition in the remaining while loop with a call to Any() instead of checking Count(); the effect is the same, but it has slightly better performance, especially on longer lists. It would be nice to get rid of the while completely in favor of another LINQ construct, but I don't see a way to do that.

public IList<IList<Box>> FindUnconnectedSets(IList<Box> boxes)
{
    IList<IList<Box>> unconnectedSets = new List<IList<Box>>();

    while (boxes.Any())
    {
        IList<Box> set = new List<Box>();

        foreach (Box newBox in boxes.Select(b => b).ToList())
        {
            if ((!set.Any()) || (set.Any(b => newBox.Overlaps(b))))
            {
                set.Add(newBox);
                boxes.Remove(newBox);
            }
        }

        unconnectedSets.Add(set);
    }

    return unconnectedSets;
}

Oh, and I replaced List<> with IList<> where possible, mainly out of a general preference for abstractions over concrete implementations; this changes nothing functionally.

By the way: If you use ReSharper, it will suggest pulling up the innermost if condition into a Where() call instead of the Select() in the foreach parameter; while that is technically correct and a more 'proficient' use of the possibilities of LINQ, it obscures the meaning of the condition and makes it harder to understand. Goes to show that shortest way to write something is not always the best.

Answer 4

Actually, your Box class itself interests me a bit. From the way it seems to be used, I'd make it immutable, as such:

public sealed class Box
{
    private readonly int xOrigin;
    private readonly int yOrigin;

    private readonly int size;

    public Box(int xOrigin, int yOrigin, int size)
    {
        this.xOrigin = xOrigin;
        this.yOrigin = yOrigin;

        this.size = size;
    }

    public int XOrigin { get { return this.xOrigin; } }
    public int YOrigin { get { return this.yOrigin; } }

    public int Size { get { return this.size; } }

    public override string ToString()
    {
        return "Box: "
            + "(" + this.xOrigin + ", " + this.yOrigin + ")"
            + " " + this.size;
    }

    public bool Overlaps(Box b2)
    {
        if (b2 == null)
            throw new ArgumentNullException("b2");
        if (this.xOrigin >= b2.XOrigin + b2.Size)
            return false;
        if (b2.XOrigin >= this.xOrigin + this.size)
            return false;
        if (this.yOrigin >= b2.YOrigin + b2.Size)
            return false;
        if (b2.YOrigin >= this.yOrigin + this.size)
            return false;

        return true;
    }
}

This may also be a decent candidate for being turned into a struct, if your Boxes can be happy with an XOrigin, YOrigin and Size of 0 by default.