Function fh_decrease_key

src/Tracker/graph/fheap.c:199–296

fh_decrease_key() - decreases the key used for vertex, vertex_no, to * new_value. No check is made to ensure that new_value is in-fact less than * the current value so it is up to the user of this function to ensure that * it is. */

 * it is.
 */
void fh_decrease_key(fheap_t *h, int vertex_no, long new_value)
{
    fheap_node_t *cut_node, *parent, *new_roots, *r, *l;
    int prev_rank;

#if FHEAP_DUMP
printf("decrease_key on vn = %d, ", vertex_no);
#endif

    /* Obtain a pointer to the decreased node and its parent then decrease the
     * nodes key.
     */
    cut_node = h->nodes[vertex_no];
    parent = cut_node->parent;
    cut_node->key = new_value;

    /* No reinsertion occurs if the node changed was a root. */
    if(!parent) {
#if FHEAP_DUMP
printf("decrease_key-exited, ");
#endif
        return;
    }

    /* Update the left and right pointers of cut_node and its two neighbouring
     * nodes.
     */
    l = cut_node->left;
    r = cut_node->right;
    l->right = r;
    r->left = l;
    cut_node->left = cut_node->right = cut_node;

    /* Initially the list of new roots contains only one node. */
    new_roots = cut_node;

    /* While there is a parent node that is marked a cascading cut occurs. */
    while(parent && parent->marked) {

        /* Decrease the rank of cut_node's parent an update its child pointer.
         */
        parent->rank--;
        if(parent->rank) {
            if(parent->child == cut_node) parent->child = r;
        }
        else {
            parent->child = NULL;
        }

        /* Update the cut_node and parent pointers to the parent. */
        cut_node = parent;
        parent = cut_node->parent;

        /* Update the left and right pointers of cut_nodes two neighbouring
         * nodes.
         */
        l = cut_node->left;
        r = cut_node->right;