Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * The Union Find implementation using up-trees.
- */
- #include <stdlib.h>
- #include <stdio.h>
- #include <stdbool.h>
- #include "lib/unionfind.h"
- #include "lib/graph.h"
- #include "lib/pixel.h"
- #include <math.h>
- int min(int p1, int p2) {
- if (p1>p2)
- return p2;
- return p1;
- }
- int max(int p1, int p2) {
- if (p1>p2)
- return p1;
- return p2;
- }
- /*pixelID root(int x, int y, pixelID parentID[ROWS][COLS]) {
- while ()
- } */
- /* Find and return the index of the root of the pixel with pixelID idx. */
- pixelID up_trees_find(pixelID parentID[ROWS][COLS], unsigned int w, pixelID idx) {
- int x = get_x_coord(idx,w);
- int y = get_y_coord(idx,w);
- if (parentID[y][x] == -1)
- return get_pixel_id(x,y,idx);
- printf("%d\n",parentID[y][x] );
- int cx = get_x_coord(parentID[y][x],w);
- int cy = get_y_coord(parentID[y][x],w);
- return up_trees_find(parentID, w, get_pixel_id(cx,cy,w));
- }
- /* Merge the two groups to which pixel p1 and pixel p2 belong. */
- void up_trees_union(pixelID parentID[ROWS][COLS], unsigned int w, pixelID p1, pixelID p2) {
- pixelID f1 = min(p1,p2);
- pixelID f2 = max(p1,p2);
- f1 = up_trees_find(parentID, w, f1);
- f2 = up_trees_find(parentID, w, f2);
- int x = get_x_coord(f2,w);
- int y = get_y_coord(f2,w);
- parentID[y][x] = f1;
- }
- /* Store forest of up-trees in the array parentID, given the graph G. */
- void up_trees_new(graph G, pixelID parentID[ROWS][COLS]) {
- for (unsigned y =0; y<(*G).image_height; y++){
- for (unsigned x =0; x<(*G).image_width; x++) {
- parentID[y][x] = -1;
- }
- }
- }
- /*
- * Run UNION-FIND, and store the final forest of up-trees in array parentID,
- * where count is a boolean flag indicating whether to print out the count.
- */
- void run_union_find(graph G, pixelID parentID[ROWS][COLS], bool count) {
- int calls = 0;
- //test and debug up trees find
- int g = (*G).image_height;
- for (unsigned y = 0; y < (*G).image_height; y++) {
- for (unsigned x = 0; x < (*G).image_width; x++) {
- if (((x+1<(*G).image_width) && (equal_colors((*G).pixels[y][x],(*G).pixels[y][x+1])))) {
- if (up_trees_find(parentID, (*G).image_width , get_pixel_id(x,y,g)) != up_trees_find(parentID, (*G).image_width, get_pixel_id(x+1,y,g) )) {
- up_trees_union(parentID, (*G).image_width, get_pixel_id(x,y,g), get_pixel_id(x+1,y,g));
- calls++;
- }
- }
- if ( (y+1<(*G).image_height) && (equal_colors((*G).pixels[y][x],(*G).pixels[y+1][x]))) {
- if (up_trees_find(parentID, (*G).image_width ,get_pixel_id(x,y,g)) != up_trees_find(parentID, (*G).image_width, get_pixel_id(x,y+1,g)) ) {
- up_trees_union(parentID, (*G).image_width, get_pixel_id(x,y,g), get_pixel_id(x,y+1,g));
- calls++;
- }
- }
- }
- }
- if (count == true)
- printf("The number of times that the method UNION was called for this image is: %d\n",calls );
- return;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement