graph.c

Go to the documentation of this file.

 
#include "graph.h"
#include "link_list.h"
#include "queue.h"
#include "stack.h"
#include "heap.h"
#include "disjoint_set.h"
#include "array.h"
 
// function Declarations
t_gen graph_delete(t_gen,t_gen);
t_gen graph_find(t_gen,t_gen);
int graph_len(t_gen);
t_gen graph_add_vertex(t_gen d, t_gen data);
t_gen graph_has_edge(t_gen d, t_gen n1, t_gen n2);
t_gen graph_add_edge(t_gen d, t_gen n1, t_gen n2);
t_gen graph_del_edge(t_gen d, t_gen n1, t_gen n2);
t_gen graph_add_edge_sym(t_gen d, t_gen n1, t_gen n2);
t_gen graph_del_edge_sym(t_gen d, t_gen n1, t_gen n2);
t_gen graph_del_vertex(t_gen d, t_gen n1);
t_gen graph_add_wedge(t_gen d, t_gen n1, t_gen n2, int weight);
t_gen graph_add_wedge_sym(t_gen d, t_gen n1, t_gen n2, int weight);
t_gen graph_bfs(t_gen d, t_gen n);
t_gen graph_dfs(t_gen d, t_gen n);
t_gen graph_toplogicaly_order_dag(t_gen d);
void graph_neigh_print(t_gen d, t_gen neigh);
void graph_print(t_gen d);
void graph_wprint(t_gen d);
void graph_destroy(t_gen d);
 
t_gen create_graph(char *name, int size, t_dparams *prm)
{
    t_graph *g = get_mem(1, sizeof(t_graph));
 
    // Initailze graph Params
    g->name       = name;
    g->count      = 0;
    g->total_edges    = 0;
    g->max_size       = size;
    g->nodes          = get_mem(size, sizeof(t_gnode));
    
    // Initailze graph routines
    g->add_vertex     = graph_add_vertex; 
    g->del_vertex     = graph_del_vertex;
    g->add_edge   = graph_add_edge; 
    g->del_edge   = graph_del_edge;
    g->has_edge   = graph_has_edge;
    g->add_edge_sym   = graph_add_edge_sym; 
    g->del_edge_sym   = graph_del_edge_sym;
    g->add_wedge      = graph_add_wedge; 
    g->add_wedge_sym  = graph_add_wedge_sym; 
    g->bfs            = graph_bfs;
    g->dfs            = graph_dfs;
    g->topo_order_dag = graph_toplogicaly_order_dag;
    g->find       = graph_find;
    g->len        = graph_len;
    g->print      = graph_print;
    g->wprint     = graph_wprint;
    g->destroy    = graph_destroy;
 
    // Initailze data type based operations req for prop working of graph
    g->cmpr       = prm->cmpr;
    g->swap       = prm->swap;
    g->free       = prm->free;
    g->print_data     = prm->print_data;
 
    return (t_gen)g;
}
 
 
int graph_len(t_gen g)
{
    return ((t_graph*)g)->count;
}
 
t_gen graph_find(t_gen d, t_gen data)
{
    t_graph *g = (t_graph*)d;
    int i;
 
    for (i = 0; i < g->count; i++) {
        if (g->cmpr(g->nodes[i].id, data) == eEQUAL) {
            return &g->nodes[i];
        }
    }
 
    return NULL;
}
 
e_cmpr graph_neigh_list_compare(t_gen x, t_gen y)
{
    t_gedge *neighl = (t_gedge*) x;
    t_gnode *node = (t_gnode*) y;
    
    if (neighl->node == node) {
        return eEQUAL;
    }
 
    return eLESS;
}
 
void graph_neigh_list_free(t_gen mem, char *file, int line)
{
    t_gedge *neighl = (t_gedge*) mem;
    
    neighl->node = NULL;
    
    free_mem(neighl);
    
}
 
t_gen graph_add_vertex(t_gen d, t_gen data)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_dparams dp;
    
    // existing node return
    node = g->find(g, data);
    if (node != NULL) {
        //LOG_WARN("GRAPH", "%s: node already present\n",g->name);
        return node;
    }
 
    // Graph size full
    if (g->count >=  g->max_size) {
        //LOG_WARN("GRAPH", "%s: No space left to add node in graph\n",g->name);
        return NULL;
    }
 
    // add node to graph
    node = &g->nodes[g->count];
    node->idx = g->count;
    g->count++;
 
    // create link list to store node neighbors
    node->id = data;
    init_data_params(&dp, eUSER);
    dp.free = graph_neigh_list_free;
    dp.cmpr = graph_neigh_list_compare;
//  node->neigh = create_link_list("neighNodes", eDOUBLE_LINKLIST, &dp);
    node->neigh = create_link_list("neighNodes", eXOR_LINKLIST, &dp);
 
    return node;
}
 
t_gen graph_has_edge(t_gen d, t_gen n1, t_gen n2)
{
    t_graph *g = (t_graph*)d;
    t_gnode *A, *B;
 
    A = g->find(g, n1);
    B = g->find(g, n2);
    
    // Nodes not present
    if (A == NULL || B == NULL) {
        return NULL;
    }
    
    // return if B present A's neigh list
    return A->neigh->find(A->neigh, B);
}
 
t_gen graph_add_edge(t_gen d, t_gen n1, t_gen n2)
{
    t_graph *g = (t_graph*)d;
    t_gnode *A, *B;
    t_gedge *edge;
 
    // ADD Node if node doesn't exit else get node
    A = g->add_vertex(g, n1);
    B = g->add_vertex(g, n2);
 
    // Return if Graph FULL
    if (A == NULL || B == NULL) {
        return NULL;
    }
 
    // Return Link already exists
    if (g->has_edge(g, n1, n2) != NULL) {
        return NULL;
    }
 
    g->total_edges++;
 
    edge = get_mem(1, sizeof(t_gedge));
    edge->node  = B;
    edge->weight = 0;
 
    // link N1->N2
    A->neigh->append(A->neigh, edge);
 
    return A;
}
 
t_gen graph_add_wedge(t_gen d, t_gen n1, t_gen n2, int weight)
{
    t_graph *g = (t_graph*)d;
    t_gnode *A, *B;
    t_gedge *edge;
 
    // ADD Node if node doesn't exit else get node
    A = g->add_vertex(g, n1);
    B = g->add_vertex(g, n2);
 
    // Return if Graph FULL
    if (A == NULL || B == NULL) {
        return NULL;
    }
 
    // Return Link already exists
    if (g->has_edge(g, n1, n2) != NULL) {
        return NULL;
    }
 
    g->total_edges++;
 
    edge = get_mem(1, sizeof(t_gedge));
    edge->node  = B;
    edge->weight = weight;
 
    // link N1->N2
    A->neigh->append(A->neigh, edge);
 
    return A;
}
 
t_gen graph_del_edge(t_gen d, t_gen n1, t_gen n2)
{
    t_graph *g = (t_graph*)d;
    t_gnode *A, *B;
 
    A = g->find(g, n1);
    B = g->find(g, n2);
    
    // Nodes not present
    if (A == NULL || B == NULL) {
        return NULL;
    }
    
    // unlink N1->N2
    d = A->neigh->del(A->neigh, B);
    free_mem(d);
    return A;
}
 
t_gen graph_add_edge_sym(t_gen d, t_gen n1, t_gen n2)
{
    t_graph *g = (t_graph*)d;
    t_gen ret;
 
    // link N1->N2
    ret = g->add_edge(g, n1, n2);
    // link N2->N1
    ret = g->add_edge(g, n2, n1);
 
    return ret;
}
 
t_gen graph_add_wedge_sym(t_gen d, t_gen n1, t_gen n2, int weight)
{
    t_graph *g = (t_graph*)d;
    t_gen ret;
 
    // link N1->N2
    ret = g->add_wedge(g, n1, n2, weight);
    // link N2->N1
    ret = g->add_wedge(g, n2, n1, weight);
 
    return ret;
}
 
t_gen graph_del_edge_sym(t_gen d, t_gen n1, t_gen n2)
{
    t_graph *g = (t_graph*)d;
    t_gen ret;
 
    // unlink N1->N2
    ret = g->del_edge(g, n1, n2);
    
    // unlink N2->N1
    ret = g->del_edge(g, n2, n1);
 
}
 
t_gen graph_del_vertex(t_gen d, t_gen n1)
{
    t_graph *g = (t_graph*)d;
    int i;
    t_gnode *A, *node;
    t_gen tmp = NULL;
 
    // Find node
    A = g->find(g, n1);
 
    // return if node doesn't exist
    if (A == NULL) {
        return tmp;
    }
 
 
    // travers all nodes in graph
    // and delete itself from each node->neigh list
    for (i = 0; i < g->count; i++) {
        if (A->idx == i) {
            continue;
        }
        node = &g->nodes[i];
        tmp = node->neigh->del(node->neigh, A);
        free_mem(tmp);
    }
    // destroy neigh list 
    A->neigh->destroy(A->neigh);    
    tmp = A->id;
    
    g->count--;
    
    if (g->count != 0 && g->count != A->idx) {
        // Swap node to be deleted with last node
        A->id = g->nodes[g->count].id;
        A->neigh = g->nodes[g->count].neigh;
    }
 
    return tmp;
}
 
void bfs_core(t_graph *g, t_gnode *node, t_bfsinfo *bfs, t_queue *q, int comp)
{
    t_linklist *neigh_list;
    t_llnode *cur, *end;
    t_gnode *neigh;
    t_gedge *edge;
 
    // Initializations 
    bfs[node->idx].level  = 0; 
    bfs[node->idx].parent = NULL; 
    bfs[node->idx].comp   = comp;
    q->enq(q, node);
    while (q->empty(q) != true) {
        node = q->deq(q);
 
        // For each vertex in queue
        // Increment level and update parent for each new vertex
        neigh_list = (t_linklist*)node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            edge  = cur->data;
            neigh = edge->node;
            // If neigh node not visited add neigh to queue 
            if (bfs[neigh->idx].level == -1) {
                bfs[neigh->idx].level  = bfs[node->idx].level + 1;
                bfs[neigh->idx].parent = node->id;
                bfs[neigh->idx].comp   = comp;
                q->enq(q, neigh);
            }
            // Get next node in neigh list
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
}
 
 
t_gen graph_bfs(t_gen d, t_gen n)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_queue *q;
    t_bfsinfo *bfs = NULL;
    t_dparams dp;
    int comp;
    bool all_nodes_visited = false;
 
    // Find node
    node = g->find(g, n);
 
    // return if node doesn't exist
    if (node == NULL) {
        return bfs;
    }
 
    // Create queue and bfs info array for bfs 
    init_data_params(&dp, eINT32);
    dp.free = dummy_free;
    q = create_queue("bfs_Q", g->count, eLL_QUEUE_CIRC, &dp);
    bfs = get_mem(g->count, sizeof(t_bfsinfo));
    
    // Init bfs data struct for vertex exploration
    for (int i = 0; i < g->count; i++) {
        bfs[i].parent = NULL;
        bfs[i].comp = bfs[i].level  = -1;
    }
 
    // Run BFS for different connected Components of graph
    comp = 0;
    while (all_nodes_visited == false) {
        bfs_core(g, node, bfs, q, comp);
        
        all_nodes_visited = true;
 
        for (int i = 0; i < g->count; i++) {
            // unvisited Vertex remains and belongs to different component
            // Run BFS with new unvisited vertex
            if (bfs[i].level == -1) {
                all_nodes_visited = false;
                node = &g->nodes[i];
                comp++;
                break;
            }
        }
    }
 
    q->destroy(q);
    
    return bfs;
}
 
void dfs_core(t_graph *g, t_gnode *node, t_dfsinfo *dfs, t_stack *s, int comp, int *gcount)
{
    t_linklist *neigh_list;
    t_llnode *cur, *end;
    t_gnode *neigh;
    t_gedge *edge;
    int count = *gcount;
    
    dfs[node->idx].parent = NULL;
    dfs[node->idx].pre    = count++;
    dfs[node->idx].comp   = comp;
    s->push(s, node);
    do {
        neigh_list = (t_linklist*)node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        // Depth Traversal of unvisited neighbor vertex
        // Don't check Neighbor list if already all neighbors visited  
        while (cur && dfs[node->idx].visited_neighbors != 0) {
            edge  = cur->data;
            neigh = edge->node;
            // For each unvisited neighbor vertex
            // update parent and pre count 
            // Push Node to stack break for Depth Traversal
            if (dfs[neigh->idx].pre == -1) {
                dfs[neigh->idx].parent = node->id;
                dfs[neigh->idx].pre    = count++;
                dfs[neigh->idx].comp   = comp;
                s->push(s, neigh);
                node = neigh;
                break;
            } 
            // Else get next unvisited vertex in neigh list
            else {  
                // Get next unvisited node in neigh list
                cur = neigh_list->next_node(neigh_list, cur);
                
                if (cur == end) {
                    // All neighbor of current node have been visited
                    dfs[node->idx].visited_neighbors = 0;
                    break;
                }
            }
        }
            
        node = s->pop(s);
        // Pop'd node has unvisted neighbors
        // Push node on to stack again to continue DFS for unvisited neighbors
        if (dfs[node->idx].visited_neighbors != 0 && cur) {
            s->push(s, node);
            continue;
        }
    
        // All neighbors visited update post count on exit
        dfs[node->idx].post = count++;
    } while (s->empty(s) != true);
    
    // Preserve count value for remaining nodes
    *gcount = count;
}
 
 
t_gen graph_dfs(t_gen d, t_gen n)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_stack *s;
    t_dfsinfo *dfs = NULL;
    t_dparams dp;
    int count, comp;
    bool all_nodes_visited = false;
 
    // Find node
    node = g->find(g, n);
 
    // return if node doesn't exist
    if (node == NULL) {
        return dfs;
    }
 
    // Create stack and dfs info array for dfs 
    init_data_params(&dp, eINT32);
    dp.free = dummy_free;
    s = create_stack("dfs_Stack", g->count, eLL_STACK, &dp);
    dfs = get_mem(g->count, sizeof(t_dfsinfo));
    
    // Init dfs data struct for vertex exploration
    for (int i = 0; i < g->count; i++) {
        dfs[i].comp = -1;
        dfs[i].parent = NULL;
        dfs[i].pre = dfs[i].post = -1;
        dfs[i].visited_neighbors = 1;
    }
 
    // Run DFS for different connected Components of graph
    comp = count = 0; 
    while (all_nodes_visited == false) {
        dfs_core(g, node, dfs, s, comp, &count);
        
        all_nodes_visited = true;
        for (int i = 0; i < g->count; i++) {
            // unvisited Vertex remains and belongs to different component
            // Run DFS with new unvisited vertex
            if (dfs[i].pre == -1) {
                all_nodes_visited = false;
                node = &g->nodes[i];
                comp++;
                break;
            }
        }
    }
    s->destroy(s);
    
    return dfs;
}
 
t_gen graph_dfs_optimised(t_gen d, t_gen n)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node, *neigh;
    t_gedge *edge;
    t_stack *s;
    t_dfsinfo *dfs = NULL;
    t_dparams dp;
    t_linklist *neigh_list;
    t_llnode *cur, *end = NULL;
    int count = 0;
 
    // Find node
    node = g->find(g, n);
 
    // return if node doesn't exist
    if (node == NULL) {
        return dfs;
    }
 
    // Create queue and dfs info array for dfs 
    init_data_params(&dp, eINT32);
    dp.free = dummy_free;
    s = create_stack("dfs_Stack", g->count, eLL_STACK, &dp);
    dfs = get_mem(g->count, sizeof(t_dfsinfo));
    
    // Init dfs data struct for vertex exploration
    for (int i = 0; i < g->count; i++) {
        dfs[i].parent = NULL;
        dfs[i].pre = dfs[i].post = -1;
        neigh_list = (t_linklist*)(g->nodes[i].neigh);
        dfs[i].visited_neighbors = neigh_list->len(neigh_list);
    }
    
    dfs[node->idx].pre = count++;
    s->push(s, node);
    do {    
        neigh_list = (t_linklist*)node->neigh;
        cur = neigh_list->head_node(neigh_list);
 
        // Depth Traversal of unvisited neighbor vertex
        // Don't check Neighbor list if already visited all the neighbors
        while (cur && dfs[node->idx].visited_neighbors != 0) {
            edge  = cur->data;
            neigh = edge->node;
            dfs[node->idx].visited_neighbors--;
            // For each vertex unvisited vertex
            // update parent and pre count 
            // Push Node to stack for Depth Traversal
            if (dfs[neigh->idx].pre == -1) {
                dfs[neigh->idx].parent = node->id;
                s->push(s, neigh);
                dfs[neigh->idx].pre = count++;
                node = neigh;
 
                // Constant 0(1) del and append on link list
                // To ensure not visiting a previously visited vertex
                // By pushing the unvisited node to last
                // And eliminating it being revisited
                // By traversing  the list only 'visited_neighbors' times
                edge = neigh_list->del_idx(neigh_list, 0);
                neigh_list->append(neigh_list, edge);
                break;
            }  
            // Else get next unvisited vertex in neigh list
            else {  
                // Get next unvisited node in neigh list
                cur = neigh_list->next_node(neigh_list, cur);
                
                if (cur == end) {
                    // All neighbor of current node have been visited
                    //dfs[node->idx].visited_neighbors = true;
                    break;
                }
            }
        }
            
        node = s->pop(s);
        // Pop'd node has unvisted neighbors
        // Push node on to stack again to continue DFS for unvisited neighbors
        if (dfs[node->idx].visited_neighbors != 0) {
            s->push(s, node);
            continue;
        }
    
        // All neighbors visited update post count on exit
        dfs[node->idx].post = count++;
    } while (s->empty(s) != true);
 
    s->destroy(s);
    
    return dfs;
}
 
 
t_gen graph_toplogicaly_order_dag(t_gen d)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node, *neigh;
    t_gedge *edge;
    t_linklist *neigh_list;
    t_llnode *cur,*end;
    t_daginfo *dag_inf;
    t_dparams dp;
    t_queue *q;
 
    // Create queue and array for dag_inf
    dag_inf = get_mem(g->count, sizeof(t_daginfo));
    init_data_params(&dp, eINT32);
    dp.free = dummy_free;
    q = create_queue("topo_dag", g->count, eLL_QUEUE_CIRC, &dp);
    
    // Indegree initialization
    for (int i = 0; i < g->count; i++) {
        dag_inf[i].indegree     = 0;
        dag_inf[i].longest_path = 0;
    }
 
    // Update indegree for all nodes
    for (int i = 0; i < g->count; i++) {
        neigh_list = g->nodes[i].neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            edge = cur->data;
            node = edge->node;
            dag_inf[node->idx].indegree += 1;
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
    
    // Add vertices with indegree 0
    for (int i = 0; i < g->count; i++) {
        if (dag_inf[i].indegree == 0) {
            q->enq(q, &g->nodes[i]);
        }
    }
    
    // Start exploration to sort/order by
    // Enumerating the vertices(delete/visited)
    while (q->empty(q) != true) {
        node = q->deq(q);
        // Enumerate node, i.e, mark as visited
        dag_inf[node->idx].node     =  node->id;
        dag_inf[node->idx].indegree = -1;
        
        // update longest path and indegree of neighbors
        // for the enumerated vertex
        neigh_list = node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            edge  = cur->data;
            neigh = edge->node;
            dag_inf[neigh->idx].indegree -= 1;
            // update path as max of parent and cur longest path
            dag_inf[neigh->idx].longest_path = 
                (dag_inf[neigh->idx].longest_path > dag_inf[node->idx].longest_path) ?
                dag_inf[neigh->idx].longest_path : (dag_inf[node->idx].longest_path + 1);
            
            //push to queue any neigh with indegree 0 
            if (dag_inf[neigh->idx].indegree == 0) {
                q->enq(q, neigh);
            }   
            // Get next neigh
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
    
    q->destroy(q);
 
    return dag_inf;
}
 
void graph_neigh_print(t_gen d, t_gen neigh)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_gedge *edge;
    t_linklist *l = (t_linklist*)neigh;
    t_llnode *cur, *end;
 
    printf("{ ");
    cur = l->head_node(l);
    while (cur) {
        edge  = cur->data;
        node  = edge->node;
        g->print_data(node->id);
        printf(" ");
        cur = l->next_node(l, cur);
        if (cur == end) {
            break;
        }
    }
    printf("}");
}
 
void graph_print(t_gen d)
{
    t_graph *g = (t_graph*)d;
    int i;
    
    printf("%s: vertex:%d edges:%d\n", g->name, g->count, g->total_edges);
 
    for (i = 0; i < g->count; i++) {
        g->print_data(g->nodes[i].id);
        printf(":");
        graph_neigh_print(g,g->nodes[i].neigh);
        printf("\n");
    } 
}
 
void graph_wneigh_print(t_gen d, t_gen neigh)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_gedge *edge;
    t_linklist *l = (t_linklist*)neigh;
    t_llnode *cur, *end;
 
    printf("{ ");
    cur = l->head_node(l);
    while (cur) {
        edge  = cur->data;
        node  = edge->node;
        printf("<");
        g->print_data(node->id);
        printf(" %d> ", edge->weight);
        cur = l->next_node(l, cur);
        if (cur == end) {
            break;
        }
    }
    printf("}");
}
 
 
void graph_wprint(t_gen d)
{
    t_graph *g = (t_graph*)d;
    int i;
    
    printf("%s: vertex:%d edges:%d\n", g->name, g->count, g->total_edges);
 
    for (i = 0; i < g->count; i++) {
        g->print_data(g->nodes[i].id);
        printf(":");
        graph_wneigh_print(g,g->nodes[i].neigh);
        printf("\n");
    } 
}
 
e_cmpr graph_wedge_cmpr(t_gen x, t_gen y)
{
    t_gedge *A = (t_gedge*)x;
    t_gedge *B = (t_gedge*)y;
    e_cmpr ret = eEQUAL;
    
    if (A->weight > B->weight) {
        ret = eGREAT;
    }
    else if (A->weight < B->weight) {
        ret = eLESS;
    }
    
    return ret;
}
 
e_cmpr graph_wedge_cmpr_idx(t_gen x, int i, int j)
{
    t_gen *arr = (t_gen*)x;
    return graph_wedge_cmpr(arr[i], arr[j]);
}
 
e_cmpr graph_wedge_cmpr_idx2(t_gen x, int i, int j)
{
    t_distinfo *arr = (t_distinfo*)x;
    return graph_wedge_cmpr(&arr[i], &arr[j]);
}
 
SWP_IDX(t_distinfo, graph_wedge_swap_idx)
 
 
t_gen dijkstra(t_gen d, t_gen data)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_gedge *v, *u;
    t_llnode *cur, *end;
    t_linklist *neigh_list;
    t_distinfo *dist, *tmp;
    t_heap *h;
    t_dparams dp;
    t_gen *pq;
    int alt_weight;
 
    // Get vertex
    node = g->find(g, data);
    if (node == NULL) {
        return NULL;
    }   
 
    // Data specific operation for generic min heap
    init_data_params(&dp, eUSER);
    dp.free     = dummy_free;
    dp.cmpr     = graph_wedge_cmpr; 
    dp.cmpr_idx = graph_wedge_cmpr_idx;
    dp.swap_idx = gen_swp_idx;
    dp.copy_idx = gen_cpy_idx;
    dp.get_idx  = gen_get_idx;
 
    // Creating a generic min heap to store edges
    pq   = get_mem(g->count, sizeof(t_gen));    
    h    = create_heap("Dijkstra's Heap", pq, g->count, eMIN_HEAP, &dp);
    
    // Initalize all dist to all nodes as infinite 
    dist = get_mem(g->count, sizeof(t_distinfo));   
    for (int i = 0; i < g->count; i++) {
        dist[i].edge.node   = &g->nodes[i];
        dist[i].edge.weight = INT_MAX; 
        dist[i].parent      = NULL;
    }
    
    // Set the source node dist as 0
    dist[node->idx].edge.weight = 0; 
    
    // Add source vertex to heap 
    h->insert(h, &dist[node->idx].edge);
    while (h->empty(h) != true) {
        // Get min dist vertex from heap and traverse all its edges
        // check if dist from cur vertex to its neigh vertex is smaller
        // Using heaps cos extract min is O(1)
        u = h->extract(h);
 
        neigh_list = (t_linklist*)u->node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            v = (t_gedge*)cur->data;
 
            // If cur dist is greater than the alt dist
            alt_weight = u->weight + v->weight;
            if (dist[v->node->idx].edge.weight > alt_weight) {
                // Set cur dist as alt dist, update parent
                // and add edge to heap
                dist[v->node->idx].edge.weight = alt_weight;
                dist[v->node->idx].parent = u->node;
                h->insert(h, &dist[v->node->idx].edge);
            }
            
            // Exit after neigh list traversal complete
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
    
    // Destroy heap and destroy the array used for storing heap
    h->destroy(h);
    free_mem(pq);
 
    return dist;
}
 
t_gen bellman_ford(t_gen d, t_gen data)
{
    t_graph *g = (t_graph*)d;
    t_gnode *node;
    t_gedge *v, *u;
    t_llnode *cur, *end;
    t_linklist *neigh_list;
    t_distinfo *dist, *tmp;
    t_dparams dp;
    t_queue *q;
    int alt_weight;
    bool *in_q;
 
    // Get vertex
    node = g->find(g, data);
    if (node == NULL) {
        return NULL;
    }
 
    init_data_params(&dp, eINT32);
    dp.free = dummy_free;
    q = create_queue("bellman_q", g->count, eLL_QUEUE_CIRC, &dp);
    
    // Initalize all dist to all nodes as infinite 
    dist = get_mem(g->count, sizeof(t_distinfo));   
    in_q = get_mem(g->count, sizeof(bool));     
    for (int i = 0; i < g->count; i++) {
        dist[i].edge.node   = &g->nodes[i];
        dist[i].edge.weight = INT_MAX; 
        dist[i].parent      = NULL;
        in_q[i] = false;
    }
    
    // Set the source node dist as 0
    dist[node->idx].edge.weight = 0; 
    q->enq(q, &dist[node->idx].edge);
    in_q[node->idx] = true;
    while (q->empty(q) != true) {
        u = q->deq(q);
        in_q[u->node->idx] = false;
        neigh_list = (t_linklist*)u->node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
    
        while (cur) {
            v = (t_gedge*)cur->data;
 
            // If cur dist is greater than the alt dist
            alt_weight = dist[u->node->idx].edge.weight + v->weight;
            if (dist[v->node->idx].edge.weight > alt_weight) {
                // Set cur dist as alt dist, update parent
                // and add edge to queue if vertex not already in queue
                dist[v->node->idx].edge.weight = alt_weight;
                dist[v->node->idx].parent = u->node;
                if (in_q[v->node->idx] != true) {
                    q->enq(q, &dist[v->node->idx].edge);
                    in_q[v->node->idx] = true;
                }
 
            }
 
            // Exit after neigh list traversal complete
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
    
    q->destroy(q);
    free_mem(in_q);
 
    return dist;
}
 
t_gen prims_mst(t_gen d)
{
    t_graph *g = (t_graph*)d;
    t_gedge *v, *u;
    t_llnode *cur, *end;
    t_linklist *neigh_list;
    t_distinfo *dist, *tmp;
    t_heap *h;
    t_dparams dp;
    t_gen *pq;
 
    // Data specific operation for generic min heap
    init_data_params(&dp, eUSER);
    dp.free     = dummy_free;
    dp.cmpr     = graph_wedge_cmpr; 
    dp.cmpr_idx = graph_wedge_cmpr_idx;
    dp.swap_idx = gen_swp_idx;
    dp.copy_idx = gen_cpy_idx;
    dp.get_idx  = gen_get_idx;
 
    // Creating a generic min heap to store edges
    pq   = get_mem(g->count, sizeof(t_gen));    
    h    = create_heap("Dijkstra's Heap", pq, g->count, eMIN_HEAP, &dp);
    
    // Initalize all dist to all nodes as infinite 
    dist = get_mem(g->count, sizeof(t_distinfo));   
    for (int i = 0; i < g->count; i++) {
        dist[i].edge.node   = &g->nodes[i];
        dist[i].edge.weight = INT_MAX; 
        dist[i].parent      = NULL;
    }
    
    
    // Set 0 as start vertex
    h->insert(h, &dist[0].edge);
    while (h->empty(h) != true) {
        // Of the edges that connect the tree to vertices not yet in the tree,
        // Find the minimum-weight edge, and transfer it to the tree
        u = h->extract(h);
 
        neigh_list = (t_linklist*)u->node->neigh;
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            v = (t_gedge*)cur->data;
            
            // If cur edge weight is greater than new edge
            // and the end vertex is not visited
            if (dist[v->node->idx].edge.weight > v->weight) {
                // Set new edge as part of MST, update parent
                // and add edge to heap
                dist[v->node->idx].edge.weight = v->weight;
                dist[v->node->idx].parent = u->node;
                h->insert(h, &dist[v->node->idx].edge);
            }
            
            // Exit after neigh list traversal complete
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
    
    // Destroy heap and destroy the array used for storing heap
    h->destroy(h);
    free_mem(pq);
 
    return dist;
}
 
t_gen kruskals_mst(t_gen d)
{
    t_graph *g = (t_graph*)d;
    t_gnode *v, *u;
    t_llnode *cur, *end;
    t_linklist *neigh_list;
    t_distinfo *dist, *tmp;
    t_dparams dp;
    t_disjset *set;
    int i, j;
 
    // Allocate mem for edge list
    tmp  = get_mem(g->total_edges, sizeof(t_distinfo));
    // Allocate mem for storing MST
    dist = get_mem(g->count, sizeof(t_distinfo));
    // Create a disjoint set
    set  = create_disjoint_set("Kruskal graph set", g->total_edges);
 
    // Create edge list from Adjancency list
    for (j = i = 0; i < g->count; i++) {
        neigh_list = (t_linklist*)(g->nodes[i].neigh);
        cur = neigh_list->head_node(neigh_list);
        end = neigh_list->end_node(neigh_list);
        while (cur) {
            tmp[j].parent = &g->nodes[i];
            tmp[j++].edge = *((t_gedge*)cur->data);
            
            // Exit after neigh list traversal complete
            cur = neigh_list->next_node(neigh_list, cur);
            if (cur == end) {
                break;
            }
        }
    }
 
    // Data specific operation for sorting edges
    init_data_params(&dp, eUSER);
    dp.cmpr_idx = graph_wedge_cmpr_idx2;
    dp.swap_idx = graph_wedge_swap_idx;
    
    // Sort the edge List based on weights
    quick_sort(tmp, g->total_edges, &dp);
 
    // Make a disjoint set for all the vertex in graph
    //(create a forest (a set of trees), where each vertex in the graph is a separate tree)
    set->make(set);
 
    // Get edges in ascending order from the edge list
    // Kruskals algorithm terminates if MST is formed(dist contains V-1 edges) 
    // or, all edges have been visited
    for (j = i = 0; (j < g->count) && (i < g->total_edges); i++) {
        u = tmp[i].parent;
        v = tmp[i].edge.node;
        
        // If edges connect two different trees add to forest(Minimum spanning Tree)
        if (set->find(set, u->idx) != set->find(set, v->idx)) {
            dist[j++] = tmp[i];
            set->merge(set, u->idx, v->idx);
        }
    }
    
    // Destroy disjoint set and the  edge list
    set->destroy(set);
    free_mem(tmp);
 
    return dist;
}
 
void graph_destroy(t_gen d)
{
    t_graph *g = (t_graph*)d;
    int i;
    
    // Go through each node and delete neigh list and data
    for (i = 0; i < g->count; i++) {
        g->nodes[i].neigh->destroy(g->nodes[i].neigh);
        g->free(g->nodes[i].id, __FILE__, __LINE__);
    }
    
    free_mem(g->nodes);
    free_mem(g);
}