disjoint_set.c

Go to the documentation of this file.

 
#include "disjoint_set.h"
 
void destroy_disjoint_set(t_gen d);
void disjoint_set_make (t_gen d);
int disjoint_set_find(t_gen d, int x);
int disjoint_set_merge (t_gen d, int x, int y);
void disjoint_set_print (t_gen d);
 
 
t_gen create_disjoint_set(char *name, int size)
{
    t_disjset *set = get_mem(1, sizeof(t_disjset));
 
    set->name    = name;
    set->size    = size;
    set->subset  = get_mem(size, sizeof(t_dsetnode));
 
    set->make    = disjoint_set_make; 
    set->find    = disjoint_set_find;
    set->merge   = disjoint_set_merge;
    
    set->print   = disjoint_set_print;
    set->destroy = destroy_disjoint_set;
 
    return set;
}
 
void destroy_disjoint_set(t_gen d)
{
    t_disjset *set = (t_disjset*)d;
 
    free_mem(set->subset);
    free_mem(set);
}
 
void disjoint_set_make (t_gen d)
{
    t_disjset *set = (t_disjset*)d;
 
    for(int i = 0; i < set->size; i++) {
        set->subset[i].size   = 1; 
        set->subset[i].parent = i; 
    }
}
 
int disjoint_set_find(t_gen d, int x)
{
    t_disjset *set = (t_disjset*)d;
    int parent = set->subset[x].parent;
    while (parent != x) {
        parent = set->subset[x].parent;
        set->subset[x].parent = set->subset[parent].parent;
        x =  set->subset[x].parent;
    }
 
    return x;
}
 
int disjoint_set_merge (t_gen d, int x, int y)
{
    t_disjset *set = (t_disjset*)d;
 
    x = set->find(set, x);
    y = set->find(set, y);
 
    if (x == y) {
        return -1;
    }
    
    if (set->subset[x].size < set->subset[y].size) {
        set->subset[x].parent = y;
        set->subset[x].size += set->subset[y].size; 
    }
    else {
        set->subset[y].parent = x;
        set->subset[y].size += set->subset[x].size; 
    }
    
    return 0;
}
 
void disjoint_set_print (t_gen d)
{
    t_disjset *set = (t_disjset*)d;
 
 
    for(int i = 0; i < set->size; i++) {
        printf("[%d: %d %d] ",i, set->subset[i].parent, 
                set->subset[i].size);
    }
    printf("\n");
}