JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
2.3. Handling Grid-Represented Graphs | Reply
A rewrite of this recipe, incorporating comments. Does anybody remember problems in which rotating and reflecting directions really helps?

Problem

One of most common graph representations in TopCoder problems is square grid graph, with vertices corresponding to cells of a grid, and edges connect vertices in adjacent cells (and sometimes other pairs of vertices, depending on the problem statement). Such structure of a graph allows a lot of small tricks that simplify and standardize processing it. Note that grid processing is rarely the main part of the problem, but having it standardized as much as possible helps concentrate on actual problem solving instead of coding.

Solution

Grid graphs are usually rectangular ones, given as an array of strings, where each character is one grid cell and one graph vertex. If the grid describes some kind of a maze, with impassable cells, such cells simply don't have a corresponding vertex (or have a vertex without edges leading to it - whichever way of thinking about it you prefer). The most common case of edges is von-Neumann neighborhood, when edges connect vertically and horizontally adjacent cells. Sometimes diagonally adjacent cells are added to form Moore neighborhood, and in rare cases other types of neighborhood are introduced.

In case of grid representation, graphs are rarely converted to explicit lists of vertices and edges; instead they are processed based on the original grid. The usual task is graph traversal (as part of finding the shortest path of some kind). For it, we need to be able to find all vertices which are adjacent to a certain vertex. For von-Neumann neighborhood a cell in row i and column j (denoted as (i,j)) has four adjacent vertices - (i+1,j), (i-1,j), (i,j+1) and (i,j-1). They can be processed explicitly, by coding processing of each cell separately (we're not giving the code, so that you don't think that's the advice!). However, this method requires a lot of copy-pasting (especially for larger neighborhoods) and is really error-prone - editing copy-pasted code adds small typos easily, and testing might not reveal them.

A much cleaner and safer way to process grid graphs is the following. Introduce arrays of deltas drow and dcol, which contain offsets of adjacent cells (relative to main cell). After this, you will be able to process all adjacent cells in a loop:

for (k=0; k<drow.size(); k++)
{   //process cell (row+drow[k], col+dcol[k])
    ...
}


Alternatively, you can skip forming arrays (which might be tricky for non-standard grids) but instead loop through all possible values of drow and dcol and reject those which don't result in valid adjacent cell (see the table for clarification).

This technique is universal and applicable to all grid-based graphs and neighborhoods on them, regardless of shape of the grid. The exact values of drow and dcol for non-standard grid might depend on its representation. It's a good idea to have values of deltas for main grid shapes pre-written and use them as required instead of reinventing them each time.
(this should be a table, with images showing the neighborhoods, matching values of drow and dcol and matching loops; it will look more neat than it does now)
_________________________________________
von-Neumann

drow = {1, 0, -1, 0}
dcol = {0, 1, 0, -1}

for (drow=-1; drow<=1; drow++)
for (dcol=-1; dcol<=1; dcol++)
    if (abs(drow)+abs(dcol)==1)
        //...

_________________________________________
Moore

drow = {1, 1, 1, 0, -1, -1, -1, 0}
dcol = {1, 0, -1, -1, -1, 0, 1, 1}

for (drow=-1; drow<=1; drow++)
for (dcol=-1; dcol<=1; dcol++)
    if (abs(drow)+abs(dcol)>0)
        //...

_________________________________________
triangular grid (TrianglesBoard)

  --> c
| /\
| /__\
\|/ /\ /\
/__\/__\
r /\ /\ /\
/__\/__\/__\


for cell board[i][j] adjacent ones will be [i][j-1], [i][j+1] and [i-1][j-1] for odd j and [i+1][j+1] for even j
_________________________________________

hexagonal grid (Hex)
coordinates are (diagonal distance, vertical distance)

            \
__ _\| d
| /a \__
| \__/d \__
\|/ /b \__/g \__
\__/e \__/l \
v /c \__/h \__/
\__/f \__/
\__/


dd = { 1,1,0,-1,-1, 0}
dv = {-1,0,1, 1, 0,-1}
_________________________________________

hexagonal grid (ExploringHoneycombs)
coordinates are (row, column)

     --> c
__ __
| /a \__/g \__
| \__/d \__/k \
\|/ /b \__/h \__/
\__/e \__/l \
r /c \__/j \__/
\__/f \__/m \
\__/ \__/


drow0 = { 1, -1, 0, 0, -1, -1 } (for even columns)
drow1 = { 1, -1, 0, 0, 1, 1 } (for odd columns)
dcol = { 0, 0, 1, -1, 1, -1 }
_________________________________________

3D rectangular grid (LightsCube)

for (dx=-1; dx<=1; dx++)
for (dy=-1; dy<=1; dy++)
for (dz=-1; dz<=1; dz++)
    if (abs(drow)+abs(dcol)>0)
        //...

_________________________________________

Chess knight move (ChessKnight)

drow = { 1, 2, 2, 1, -1, -2, -2, -1 }
dcol = { 2, 1, -1, -2, -2, -1, 1, 2 }

for (drow = -2; drow <= 2; drow++)
for (dcol = -2; dcol <= 2; dcol++)
    if (abs(drow*dcol) == 2) 
        //...

_________________________________________

Another trick helps treating boundary conditions. See, cells which are in row 0 or R-1, or in column 0 or C-1, have less neighbors than central ones. Trying to use a generic formula and to access cells outside of the grid results in an error, and it might be tiresome to check whether the cell is within the grid each time it is accessed. This can be avoided by padding the original grid with rows and columns of impassable cells on each side. This way, the border cells are guaranteed not to be reached, so boundary checks can be omitted.
Re: 2.3. Handling Grid-Represented Graphs (response to post by Nickolas) | Reply
Discussion

In some problems the order of deltas within their arrays can be important. Ordering directions clockwise or counterclockwise allows to rotate and mirror them as the problem requires. Aother case when this is useful is when the problem requires some ordering, for example, if you need a lexicographically first shortest way to get out of a maze - you just need to try movements in alphabetical order.

The described technique can be applied not only to graph traversal problems, but to any tasks which involve finding vertices adjacent to given one; thus, in problems GameOfLife and FuzzyLife it can be used nicely for counting number of live cells around given one.

Now, let's have a look at several classic examples of grid-based problems.

Problem TroytownKeeper is an interesting example of problem, in which grid should be padded not with impassable cells, but with passable ones, so that padding preserves visibility of all faces of the maze. Other than that, maze is processed in quite a standard way. C++ code follows:

#include <string>
#include <vector>
 
using namespace std;
 
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
 
bool inside(int r, int c, int R, int C) {
    return r>=0 && r<R && c>=0 && c<C;
}
 
class TroytownKeeper {
    public:
    int limeLiters(vector <string> maze)  {
        int i,j,k;
        vector<string> m;
        vector<int> x,y;
        //pad the maze with '.'
        string t(maze[0].size()+2,'.');
        m.push_back(t);
        for (i=0; i<maze.size(); i++)
            m.push_back("."+maze[i]+".");
        m.push_back(t);
        //bfs
        m[0][0]=' ';
        x.push_back(0);
        y.push_back(0);
        i=0;
        while (i<x.size())
        {   for (j=0; j<4; j++)
                if (inside(x[i]+dx[j], y[i]+dy[j], m.size(), m[0].size()) && (m[x[i]+dx[j]][y[i]+dy[j]]=='.'))
                {   //move
                    x.push_back(x[i]+dx[j]);
                    y.push_back(y[i]+dy[j]);
                    m[x[i]+dx[j]][y[i]+dy[j]]=' ';
                }
            i++;
        }
        //count visible faces
        int ans=0;
        for (i=0; i<m.size(); i++)
        for (j=0; j<m[0].size(); j++)
            if (m[i][j]==' ')
                for (k=0; k<4; k++)
                    if (inside(i+dx[k], j+dy[k], m.size(), m[0].size()) && (m[i+dx[k]][j+dy[k]]=='#'))
                        ans++;
        return ans;
    }
};



Problem ChessKnight is based on processing knight movement, with a bit of math. To solve it, we need to iterate n times, keeping track of probabilities of the knight being on each cell of the board during each move. Java solution follows:

public class ChessKnight
{   public double probability(int x, int y, int n)
    {   double prob[][][] = new double[8][8][n+1];
        int di[] = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };
        int dj[] = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
        int i,j,k,d;
        double res=0;
        prob[x-1][y-1][0] = 1;
        for (k=1; k<=n; k++)
            for (i=0; i<8; i++)
            for (j=0; j<8; j++)
                for (d=0; d<8; d++)
                    if (i+di[d]>=0 && i+di[d]<8 && j+dj[d]>=0 && j+dj[d]<8)
                        prob[i+di[d]][j+dj[d]][k] += prob[i][j][k-1]/8;
        for (i=0; i<8; i++)
        for (j=0; j<8; j++)
            res += prob[i][j][n];
        return res;
    }
}
Re: 2.3. Handling Grid-Represented Graphs (response to post by Nickolas) | Reply
Cool - I've never seen this before, thanks. Nice pictures! Could you change <2 to <=1 though, because it makes the code easier to understand.
Re: 2.3. Handling Grid-Represented Graphs (response to post by Nickolas) | Reply
Indeed, great job on the representations. The if condition on the 3D rectangular grid is wrong, though.

Edit: looks like I should be invited to post here. I got here by googling and didn't see the notice on the forum board. Sorry!
Re: 2.3. Handling Grid-Represented Graphs (response to post by luizribeiro) | Reply
No, it's ok to point out the bug - thanks, I'll fix it in the final version.
RSS