1
\$\begingroup\$

I have written some basic implementation of a Minimum Spanning Tree using a indexed minimum priority queue. For the implementation of the Priority Queue I used Sedgewick's Tutorials.

However, it seems that I am passing a lot of arrays around for the priority queue. Here, is my code snippet. Could someone point out the obvious faults and also suggest a better abstraction for the priority queue. (Since Sedgewick's Tutorials were in Java, I translated them to C and I think that my implementation is not good.)

void minimum_spanning_tree(adj_list *adjacency_list)
{
    int pq[NMAX + 1];
    float keys[NMAX];
    int size_of_heap = 0;

    float node_key[NMAX];
    int node_parent[NMAX];
    boolean marked[NMAX] = { FALSE };

    for (int i = 0; i < adjacency_list->no_vert; i++) {
        node_key[i] = INT_MAX;
        node_parent[i] = -1;
        insert(i, &size_of_heap, node_key[i], pq, keys);
    }

    int start_vertex = 0;

    node_key[start_vertex] = 0.0;
    node_parent[start_vertex] = 0;
    decrease_key(start_vertex, &size_of_heap, node_key[start_vertex], pq, keys);

    while (size_of_heap > 0) {
        int vertex = delete_min(&size_of_heap, pq, keys);
        marked[vertex] = TRUE;  // Why marked? Because once an element is deleted
                                // from a queue it is marked i.e. is already included.
        bag *bag_of_vertex = adjacency_list->bags[vertex];
        node *node_of_vertex = bag_of_vertex->first;
        while (node_of_vertex != NULL) {
            relax_min_span_tree(node_of_vertex, node_key, node_parent, &size_of_heap, pq, keys, marked);
            node_of_vertex = node_of_vertex->next;
        }
    }

    // create_minimum_span_tree(start_vertex, adjacency_list, node_key, node_parent);
    create_minimum_span_tree_queue(adjacency_list, node_key, node_parent);
}


void relax_min_span_tree(node *node_of_vertex, float node_key[], int node_parent[], int *size_of_heap, int pq[], float keys[], boolean marked[])
{
    int from, to;
    from = node_of_vertex->from;
    to = node_of_vertex->to;
    if (marked[to] == TRUE)
        return;

    if (node_of_vertex->weight < node_key[to]) {
        node_key[to] = node_of_vertex->weight;
        node_parent[to] = from;
        decrease_key(to, size_of_heap, node_key[to], pq, keys);
    }
}


void create_minimum_span_tree_queue(adj_list *adjacency_list, float node_key[], int node_parent[])
{
    queue *queue_inst = queue_create();

    for (int i = 0; i < adjacency_list->no_vert; i++) {
        edge *edge_inst = (edge *) malloc(sizeof(edge));
        edge_inst->from = node_parent[i];
        edge_inst->to = i;
        edge_inst->weight = node_key[i];

        queue_add(queue_inst, edge_inst);
    }

    fprintf(stdout, "The minimum spanning tree: \n");
    while (!queue_is_empty(queue_inst)) {
        edge *edge_inst = queue_remove(queue_inst);
        fprintf(stdout, "%2d ->%2d == %.2f\n", edge_inst->from, edge_inst->to, edge_inst->weight);
        free(edge_inst);
    }

    queue_destroy(queue_inst);
}

The Indexed Minimum Priority Queue implementation -

boolean insert(int i, int *size, float key, int pq[], float keys[])
{
    if (i < 0 || i > NMAX)          return FALSE;

    (*size)++;
    pq[*size] = i;
    keys[i] = key;
    // swim(size, pq, keys);
    swim_simple(*size, pq, keys);
    return TRUE;
}

boolean greater(int i, int j, int pq[], float keys[])
{
    if (keys[pq[i]] > keys[pq[j]])      return TRUE;
    else                                return FALSE;
}

void exch(int i, int j, int pq[])
{
    int swap = pq[i];
    pq[i] = pq[j];
    pq[j] = swap;
}

void swim_simple(int k, int pq[], float keys[])
{
    if (k == 1)             return;

    while (k > 1 && greater(k/2, k, pq, keys)) {
        exch(k, k/2, pq);
        k = k/2;
    }
}

int delete_min(int *size, int pq[], float keys[])
{
    if ((*size) <= 0) {
        return INT_MAX;
    }

    int min = pq[1];
    exch(1, (*size)--, pq);
    sink(1, size, pq, keys);

    return min;
}

void sink(int k, int *size, int pq[], float keys[])
{
    while (2 * k <= (*size)) {
        int j = 2 * k;
        if (j < (*size) && greater(j, j+1, pq, keys))   j++;
        if (!greater(k, j, pq, keys))                   break;
        exch(k, j, pq);
        k = j;
    }
}

The decrease key method -

boolean decrease_key(int i, int *size, float key, int pq[], float keys[])
{
    if (i < 0 || i > NMAX)              return FALSE;
    keys[i] = key;
    swim(i, pq, keys);  // swim(pq[i], pq, keys) also works, no idea why.
    return TRUE;
}
\$\endgroup\$
  • \$\begingroup\$ @JS1 I have used an index based minimum priority queue. Also I insert all the elements at the beginning itself with INT_MAX. So when a key is changed (i.e. the edge weight is changed) I decrease the key belonging to a particular ID. (I forgot to include that in the code above. I have added it now.) \$\endgroup\$ – yadav_vi Dec 4 '14 at 9:10
  • \$\begingroup\$ No problem, I was just looking for the code. Does swim here mean swim_simple or is there a separate swim function? \$\endgroup\$ – JS1 Dec 4 '14 at 9:40
  • \$\begingroup\$ @JS1 yes, it is the same function. swim implementation was a more complex to understand so I tried simplifying it. My entire project is hosted at GitHub. \$\endgroup\$ – yadav_vi Dec 4 '14 at 9:45
2
\$\begingroup\$

From what I can tell after a quick scan, you have a bug in decrease_key(). This code is suspect:

keys[i] = key;
swim(i, pq, keys); // swim(pq[i], pq, keys) also works, no idea why.

I believe that what is correct is for you to call swim on index k, where k is the index such that pq[k] == i. I'm not sure at the moment how you are supposed to find k. Maybe that is what the complex swim function was for? Your comment about the other way also working shows that the heap is able to correct itself in some cases, so you might not notice the bug immediately.

As far as all the arrays being passed around, I think you should make a heap that encapsulates your variables pq, keys, and size_of_heap. That way, wherever you pass any or all of those variables around (which is a lot), you can just pass a single pointer to your heap structure. Your function calls would turn from:

insert(i, &size_of_heap, node_key[i], pq, keys);
vertex = delete_min(&size_of_heap, pq, keys);
decrease_key(start_vertex, &size_of_heap, node_key[start_vertex], pq, keys);
relax_min_span_tree(node_of_vertex, node_key, node_parent, &size_of_heap, pq, keys, marked);

to:

insert(heap, i, node_key[i]);
vertex = delete_min(heap);
decrease_key(heap, start_vertex, node_key[start_vertex]);
relax_min_span_tree(node_of_vertex, node_key, node_parent, heap, marked);

I forked your github and replaced your heap with my own implementation. You can check heap.c in my fork.

\$\endgroup\$
  • \$\begingroup\$ Now that I think of it swim(pq[i], pq, keys) is correct. Thanks for pointing it out. Any more comments on the coding style? I find the passing of 2-3 arrays very cumbersome. Should I create a structure something like - typedef struct min_prior_q { int size; float keys[NMAX]; int pq[NMAX + 1]; } min_prior_q; \$\endgroup\$ – yadav_vi Dec 4 '14 at 10:44
  • \$\begingroup\$ Actually I don't think swim(pq[i], ...) is right either. Here's one way you can test it. Write a function to check to the validity of the heap (by checking that each node is greater than its two children). Then, after each decrease_key, call the heap checking function. I do have more to say about using structs, but I don't have time right now and I just wanted to let you know about the potential bug first. \$\endgroup\$ – JS1 Dec 4 '14 at 10:49
  • \$\begingroup\$ nice implementation. How do you decide how to name the variables and structs in C? In your implementation, you have used both _ as well as CamelCase. Could you tell me what is the actual method of naming and how do I keep the variable names smaller? \$\endgroup\$ – yadav_vi Dec 5 '14 at 6:26
  • \$\begingroup\$ My naming convention is that I use CamelCase everywhere, but I use a single underscore to separate an "object type" from an "action to the object", for example Heap_Insert. It's just something that I use, but other naming conventions are fine. For variable names, I tend to abbreviate when names get too long. So for example, I would turn node_of_vertex into vertNode. \$\endgroup\$ – JS1 Dec 5 '14 at 6:38
  • 1
    \$\begingroup\$ If you just name your function insert, then how will you also have a linked list in your same program with an insert function? The way I do it, my functions name will never collide. Like I said, other naming conventions are fine. I'm not trying to convince you to use mine. As far as calloc, I've had so many bugs due to uninitialized memory that I almost always use calloc and I usually initialize every local variable even when not necessary. \$\endgroup\$ – JS1 Dec 5 '14 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.