Finding unconnected sets 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&lt;List&lt;Box&gt;&gt; FindUnconnectedSets(List&lt;Box&gt; boxes)
{
    List&lt;List&lt;Box&gt;&gt; unconnectedSets = new List&lt;List&lt;Box&gt;&gt;();

    while (boxes.Count() != 0)
    {
        List&lt;Box&gt; set = new List&lt;Box&gt;();

        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 &gt;= b2.XOrigin + b2.Size)
            return false;
        if (b2.XOrigin &gt;= XOrigin + Size)
            return false;
        if (YOrigin &gt;= b2.YOrigin + b2.Size)
            return false;
        if (b2.YOrigin &gt;= 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. :)
Since we are talking about sets, it's probably better to use collection types that represent a set: HashSet&lt;T&gt; and ISet&lt;T&gt;.

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&lt;in T&gt;
{
    bool IsConnectedTo(T other);
}

public class Box: IConnected&lt;Box&gt;
{
    ....

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


And the FindUnconnectedSets:

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

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

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

    return unconnectedSets;
}