Find the longest connect cells region per color

Question

I have been studying graphs/BFS/DFS. working on wrapping my head around the following problem

Given a grid [m,n] where each cell has a value denotes a color, find the longest connected region that shares the same color (color is an int)

I was able to come up with the following algorithm that uses a (BFS) Breadth Search First mechanism. I would appreciate your feedback.

I also wanted to try and craft a solution using DFS. I know I might run into a stack overflow issues if the graph is too big. However, I would appreciate any feedback on how to construct my algo using DFS ( I couldn't wrap my head around DFS with different colors at play)

The initialization method:

/// <summary>
/// Finds the longest connect region per color.
/// </summary>
/// <returns>Returns a pair that has the color and the count of the connected cells</returns>
public static Tuple<int,int> FindLongestConnectedColor()
{
    int[,] graph = {
                        {1, 1, 1, 2,2,3},
                        {1, 1, 1, 2,2,3},
                        {1, 1, 1, 2,2,3}
                    };

    var graphRowsCount = graph.GetLength(0);
    var graphColumnsCount = graph.GetLength(1);

    var visitedCellsPerColor = new Dictionary<int, HashSet<Tuple<int, int>>>();

    // first int represents the color, second int represents the region cells' count
    var longestRegion = new Tuple<int, int>(-1, -1);


    for (int row = 0; row < graphRowsCount; row++)
    {
        for (int column = 0; column < graphColumnsCount; column++)
        {
            var color = graph[row, column];

            if (!visitedCellsPerColor.ContainsKey(color))
            {
                visitedCellsPerColor.Add(color, new HashSet<Tuple<int, int>>());
            }

            if (!visitedCellsPerColor[color].Contains(new Tuple<int, int>(row, column)))
            {
                var length = GetConnectedRegionLength(row, column, graph, visitedCellsPerColor);
                if (longestRegion.Item2 < length)
                {
                    longestRegion = new Tuple<int, int>(color, length);
                }
            }
        }
    }

    return longestRegion;
}

My BFS logic

• I am using two queues to avoid boxing/unboxing performance hit
• I only consider cells that are of the same color
• I only consider unvisited cells if they belong to the same color

Code:

private static int GetConnectedRegionLength(int row, int column, int[,] graph, Dictionary<int, HashSet<Tuple<int, int>>> visited)
{
    var directionRow = new List<int> { -1, +1, 0, 0 };
    var directionColumn = new List<int> { 0, 0, +1, -1 };
    var graphRowsCount = graph.GetLength(0);
    var graphColumnsCount = graph.GetLength(1);

    var connectedCellsCount = 0;

    var color = graph[row, column];

    var q1 = new Queue<int>();
    var q2 = new Queue<int>();

    q1.Enqueue(row);
    q2.Enqueue(column);
    visited[color].Add(new Tuple<int, int>(row, column));
    connectedCellsCount++;

    while (q1.Any())
    {
        // current Row
        var cr = q1.Dequeue();
        // Current Column
        var cc = q2.Dequeue();

        for (int a = 0; a < directionRow.Count; a++)
        {
            var newRow = cr + directionRow[a];
            var newColumn = cc + directionColumn[a];

            if (newRow < 0 || newColumn < 0) continue;
            if (newRow >= graphRowsCount  || newColumn >= graphColumnsCount ) continue;
            if (graph[newRow, newColumn] != color) continue;
            if (visited[color].Contains(new Tuple<int, int>(newRow, newColumn))) continue;

            q1.Enqueue(newRow);
            q2.Enqueue(newColumn);
            visited[color].Add(new Tuple<int, int>(newRow, newColumn));
            connectedCellsCount++;
        }
    }

    return connectedCellsCount;
}

Answer 1

Looks fine overall, but there are a few oddities here and there, and there are some opportunities for significant performance improvements:

• Since you're going to visit every node in the given int[,] graph you might as well use a bool[,] instead of a Dictionary<int, HashSet<Tuple<int, int>>>. I see no reason to group visited nodes per color, because you're already keeping track of the largest group separately. For me, this made things about 6x faster.
• Using an 'old-style' tuple as return type isn't very descriptive. Consider using value-tuples instead: public static (int color, int count) FindLongestConnectedColor().
• In GetConnectedRegionLength, I'd combine directionRow and directionColumn into a single array of (int x, int y) tuples. Not a list - it's not going to be resized. This also provides a small performance increase. Also consider storing it in a static field, so you only need to initialize the array once, for yet another performance increase.
• q1 and q2 are rather undescriptive names - openNodes would be better. It's also unclear why there are two queues instead of one (you mentioned the reason in your post, but it's not documented in the code). About that reason - Queue<T> is generic, so a Queue<Tuple<int, int>> or Queue<(int, int)> is not going to involve boxing. Yes, you'll need to create tuple objects, but you no longer need to call Enqueue and Dequeue twice. Performance should be more or less the same. When in doubt, measure!
• connectedCellsCount can be initialized to 1 directly.
• while (q1.Count > 0) is faster than while (q1.Any()).
• a is rather uncommon as a counter variable name - I'd stick to i.
• Personally I'm not a fan of putting single if-body statements on the same line: if (...) continue;. It makes these 'early-outs' more difficult to spot when scanning code.
• The various if/continue statements can be combined into a single if.

As for breadth-first versus depth-first, I guess I don't really see the point here: the only difference is the order in which you visit nodes, but you still have to visit all of them. Either way, instead of recursion you can also combine iterative code with a stack data-structure. Similar to your current solution, just with a stack instead of a queue.