Graph problems
Find neighbour in array
Find all the neighbours of a given element in array
Neighbours can be defined as
- Neighbours are only vertical and horizontal elements next to given element
- Neighbours are only vertical, horizontal and diagonal elements next to given element
- Neighbours are all vertical, horizontal and diagonal elements next to given element
1 2/****************************************************** 3 * Function: neighbour(int sx, int sy) 4 * This function returns the neighbour of sx, sy 5 * For e.g. 6 * 1 2 3 7 * 4 5 6 8 * 7 8 9 9 * 10 * Neighbour for 5 (1,1) = 4, 2, 6, 8 11 * Neighbour for 1 (0,0) = 4, 2 12 * ****************************************************/ 13void neighbour(int sx, int sy) 14{ 15 if (sy - 1 >= startCol && sy - 1 <= col) { 16 printf("\n[%d][%d]: %d ", sx, sy - 1, array[sx][sy - 1]); 17 } 18 19 if (sx - 1 >= startRow && sx - 1 <= row) { 20 printf("\n[%d][%d]: %d ", sx - 1, sy, array[sx - 1][sy]); 21 } 22 23 if (sy + 1 >= startCol && sy + 1 <= col) { 24 printf("\n[%d][%d]: %d ", sx, sy + 1, array[sx][sy + 1]); 25 } 26 27 if (sx + 1 >= startRow && sx + 1 <= row) { 28 printf("\n[%d][%d]: %d ", sx + 1, sy,array[sx + 1][sy]); 29 } 30}
1 2/****************************************************** 3 * Function: diagnolNeighbour(int sx, int sy) 4 * This function returns the neighbour of sx, sy and 5 * diagonal neighbours too. 6 * For e.g. 7 * 1 2 3 8 * 4 5 6 9 * 7 8 9 10 * 11 * Neighbour for 5 (1,1) = 4, 2, 6, 8, 1, 3, 7, 9 12 * Neighbour for 1 (0,0) = 4, 2, 5 13 * ****************************************************/ 14void diagnolNeighbour(int sx, int sy) { 15 if (sy - 1 >= startCol && sy - 1 <= col) { 16 printf("%d ", array[sx][sy - 1]); 17 } 18 19 if (sx - 1 >= startRow && sx - 1 <= row) { 20 printf("%d ", array[sx - 1][sy]); 21 22 //Diagnols 23 if (sy - 1 >= startCol && sy - 1 <= col) { 24 printf("%d ", array[sx - 1][sy - 1]); 25 } 26 if (sy + 1 >= startCol && sy + 1 <= col) { 27 printf("%d ", array[sx - 1][sy + 1]); 28 } 29 } 30 31 if (sy + 1 >= startCol && sy + 1 <= col) { 32 printf("%d ", array[sx][sy + 1]); 33 } 34 35 if (sx + 1 >= startRow && sx + 1 <= row) { 36 printf("%d ", array[sx + 1][sy]); 37 38 //Diagnols 39 if (sy - 1 >= startCol && sy - 1 <= col) { 40 printf("%d ", array[sx + 1][sy - 1]); 41 } 42 if (sy + 1 >= startCol && sy + 1 <= col) { 43 printf("%d ", array[sx + 1][sy + 1]); 44 } 45 } 46}
1 2/********************************************************** 3 * Function: allNeighbour(int sx, int sy) 4 * This function returns all the neighbour of sx, sy and 5 * all diagonal neighbours. 6 * For e.g. 7 * 1 2 3 4 8 * 5 6 7 8 9 * 9 10 11 12 10 * 13 14 15 16 11 * 12 * Neighbour for 5 (1,0) = 1, 9, 13, 6, 7, 8, 10, 15 13 * Neighbour for 11 (2,2) = 3, 7, 15, 9, 10, 12, 1, 6, 16 14 * ********************************************************/ 15void allNeighbour(int sx, int sy) 16{ 17 int done = 0; 18 int tempX = sx; 19 int tempY = sy; 20 int i = 0; 21 int j = 0; 22 23 // Get all the elements in row 24 for (i = 0; i <= row; i++) { 25 if (array[i][sy] == array[sx][sy]) { 26 continue; 27 } 28 printf("%d ", array[i][sy]); 29 } 30 31 // Get all the elements in col 32 for (j = 0; j <= col; j++) { 33 if (array[sx][j] == array[sx][sy]) { 34 continue; 35 } 36 printf("%d ", array[sx][j]); 37 } 38 39 // Diagnols 40 while (1) { 41 tempX--; tempY--; 42 if (tempX >= startRow && tempY >= startCol) { 43 printf("%d ", array[tempX][tempY]); 44 } else { 45 done = 1; 46 } 47 48 sx++,sy++; 49 if (sx <= row && sy <= col) { 50 printf("%d ", array[sx][sy]); 51 } else if (done) { 52 break; 53 } 54 } 55}
Find all the ascending paths in graph
Given array as
Find all the paths from 1 to 3. The possible ascending path are
1 ->6->8->9-> 3
1 ->4->7->9->3
1 ->6->7->2->3 is not the right solution as 7 > 2
1 2#include <stdio.h> 3#include <stdlib.h> 4 5#define xIndex 3 6#define yIndex 3 7#define TRUE 1 8#define FALSE 0 9 10int startIndX = 0; 11int startIndY = 0; 12int endIndX = 2; 13int endIndY = 2; 14 15// Structure to construct final path 16typedef struct node { 17 int x; 18 int y; 19 int parentVal; 20} parent; 21 22typedef struct queue { 23 int x; 24 int y; 25 struct queue *next; 26} qnode; 27 28qnode *head; 29qnode *tail; 30 31// Neighbour index coordinates 32int neighbourIndex[4][2]; 33int array[xIndex][yIndex]; 34int visited[xIndex][yIndex]; 35int row = xIndex - 1; 36int col = yIndex - 1; 37int startRow = 0; 38int startCol = 0; 39 40parent* parentArr[xIndex][yIndex]; 41 42// Function declarations 43void neighbour(int sx, int sy); 44int isVisited(int x, int y); 45void markVisited(int x, int y); 46void markUnvisited(int x, int y); 47void markParent(int childX, int childY, int parentX, int parentY); 48void findPath(int startX, int startY, int endX, int endY); 49void enqueue(int x, int y); 50qnode* dequeue(); 51int isQueueEmpty(); 52void printPath(int x, int y); 53void freeQueue(); 54void test1(); 55 56 57void neighbour(int sx, int sy) 58{ 59 int i = 0; 60 int j = 0; 61 62 for (i = 0; i < 4; i++) { 63 for (j = 0; j < 2; j++) { 64 neighbourIndex[i][j] = -1; 65 } 66 } 67 68 i = 0; j = 0; 69 70 if (sy - 1 >= startCol && sy - 1 <= col) { 71 neighbourIndex[i][0] = sx; 72 neighbourIndex[i][1] = sy - 1; 73 i++; 74 } 75 76 if (sx - 1 >= startRow && sx - 1 <= row) { 77 neighbourIndex[i][0] = sx - 1; 78 neighbourIndex[i][1] = sy; 79 i++; 80 } 81 82 if (sy + 1 >= startCol && sy + 1 <= col) { 83 neighbourIndex[i][0] = sx; 84 neighbourIndex[i][1] = sy + 1; 85 i++; 86 } 87 88 if (sx + 1 >= startRow && sx + 1 <= row) { 89 neighbourIndex[i][0] = sx + 1; 90 neighbourIndex[i][1] = sy; 91 i++; 92 } 93} 94 95int isVisited(int x, int y) 96{ 97 return visited[x][y]; 98} 99 100void markVisited(int x, int y) 101{ 102 visited[x][y] = 1; 103} 104 105void markUnvisited(int x, int y) 106{ 107 visited[x][y] = 0; 108} 109 110void markParent(int childX, int childY, int parentX, int parentY) 111{ 112 parent* temp = (parent *)malloc(sizeof(parent)); 113 114 if (temp == NULL) { 115 // Put ASSERT 116 } 117 118 temp->x = parentX; 119 temp->y = parentY; 120 temp->parentVal = array[parentX][parentY]; 121 122 parentArr[childX][childY] = temp; 123} 124 125void enqueue(int x, int y) 126{ 127 qnode *temp = (qnode *)malloc(sizeof(qnode)); 128 if (temp == NULL) { 129 // Put ASSERT 130 } 131 132 temp->x = x; 133 temp->y = y; 134 temp->next = NULL; 135 136 tail->next = temp; 137 138 tail = temp; 139} 140 141qnode* dequeue() 142{ 143 qnode *temp; 144 145 if (!isQueueEmpty()) { 146 temp = head->next; 147 148 if (temp == tail) { 149 tail = head; 150 } 151 head->next = temp->next; 152 return temp; 153 } 154 155 return head->next; 156} 157 158int isQueueEmpty() 159{ 160 if (head->next == NULL) { 161 return TRUE; 162 } 163 164 return FALSE; 165} 166 167void freeQueue() 168{ 169 qnode* temp; 170 171 while (head->next != NULL) { 172 temp = head->next; 173 head->next = head->next->next; 174 175 free (temp); 176 } 177 178} 179 180void printPath(int x, int y) 181{ 182 parent *pInfo; 183 184 printf("Path:\n"); 185 while (1) { 186 printf ("%d ", array[x][y]); 187 188 pInfo = parentArr[x][y]; 189 x = pInfo->x; 190 y = pInfo->y; 191 192 if (x == startIndX && y == startIndY) { 193 printf ("%d ", array[x][y]); 194 break; 195 } 196 } 197} 198 199void findPath(int startX, int startY, int endX, int endY) 200{ 201 int i = 0; 202 int j = 0; 203 int x = startX; 204 int y = startY; 205 int neighbourX = startX; 206 int neighbourY = startY; 207 int reached = FALSE; 208 qnode *nextNode; 209 210 211 while (1) { 212 neighbour(x, y); 213 214 // Check, are we neighbour of destination? 215 for (i = 0; i < 4; i++) { 216 if (neighbourIndex[i][0] == endX && neighbourIndex[i][1] == endY) { 217 // Reached destination 218 neighbourX = neighbourIndex[i][0]; 219 neighbourY = neighbourIndex[i][1]; 220 markParent(neighbourX, neighbourY, x, y); 221 222 reached = TRUE; 223 break; 224 } else { 225 // Validate neighbour 226 if (neighbourIndex[i][0] != -1) { 227 neighbourX = neighbourIndex[i][0]; 228 neighbourY = neighbourIndex[i][1]; 229 if (array[x][y] < array[neighbourX][neighbourY]) { 230 // Mark neighbour index as visited 231 markVisited(x, y); 232 markVisited(neighbourX, neighbourY); 233 234 // Make me parent of neighbour index 235 markParent(neighbourX, neighbourY, x, y); 236 237 // Add neighbour to queue 238 enqueue(neighbourX, neighbourY); 239 } 240 } 241 } 242 } // end of for 243 244 if (reached) { 245 // print path 246 printPath(endIndX, endIndY); 247 break; 248 } 249 250 if (isQueueEmpty()) { 251 // If queue is empty then halt, no path found 252 printf ("No valid path exist"); 253 break; 254 } 255 256 // Get next item from queue 257 nextNode = dequeue(); 258 if (nextNode != NULL) { 259 x = nextNode->x; 260 y = nextNode->y; 261 262 free (nextNode); 263 } 264 } // end of while 265} 266 267 268void test1() 269{ 270 int i = 0; 271 int j = 0; 272 273 array[0][0] = 1; 274 array[0][1] = 6; 275 array[0][2] = 8; 276 array[1][0] = 4; 277 array[1][1] = 7; 278 array[1][2] = 9; 279 array[2][0] = 5; 280 array[2][1] = 2; 281 array[2][2] = 3; 282 283 printf("\n\n"); 284 for (i = 0; i <= row; i++) { 285 for (j = 0; j <= col; j++) { 286 printf("%d ", array[i][j]); 287 } 288 printf("\n"); 289 } 290 291 findPath(startIndX, startIndY, endIndX, endIndY); 292 freeQueue(); 293} 294 295int main() 296{ 297 head = (qnode*)malloc(sizeof(qnode)); 298 head->x = -1; 299 head->y = -1; 300 head->next = NULL; 301 302 tail = head; 303 304 test1(); 305 306 return 0; 307}