JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 2.3. Handling Grid-Represented Graphs
 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?ProblemOne 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.SolutionGrid 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; k0) //... ```_________________________________________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 DiscussionIn 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 #include   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=0 && c maze) { int i,j,k; vector m; vector x,y; //pad the maze with '.' string t(maze[0].size()+2,'.'); m.push_back(t); for (i=0; i=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.
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 2.3. Handling Grid-Represented Graphs Previous Thread  |  Next Thread