Dijkstra's shortest path algorithm in C

Question

Now I have this C implementation of the famous algorithm:

dijkstra.h:

#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include "directed_graph_node.h"
#include "weight_function.h"
#include "list.h"

#ifdef  __cplusplus
extern "C" {
#endif

list_t* dijkstra(directed_graph_node_t* p_source,
                 directed_graph_node_t* p_target,
                 directed_graph_weight_function_t* p_weight_function);    

#ifdef  __cplusplus
}
#endif

#endif  /* DIJKSTRA_H */

dijkstra.c:

#include "dijkstra.h"
#include "list.h"
#include "directed_graph_node.h"
#include "weight_function.h"
#include "unordered_map.h"
#include "unordered_set.h"
#include "heap.h"
#include "utils.h"

typedef struct weight_t {
    double weight;
} weight_t;

static int priority_cmp(void* pa, void* pb) 
{
    double da;
    double db;

    da = ((weight_t*) pa)->weight;
    db = ((weight_t*) pb)->weight;

    if (da < db) 
    {
        return -1;
    }
    else if (da > db) 
    {
        return 1;
    }

    return 0;
}

static const size_t INITIAL_CAPACITY = 16;
static const float  LOAD_FACTOR      = 1.0f;

list_t* dijkstra(directed_graph_node_t* p_source,
                 directed_graph_node_t* p_target,
                 directed_graph_weight_function_t* p_weight_function)
{
    list_t*                   p_list;
    heap_t*                   p_open_set;
    unordered_set_t*          p_closed_set;
    unordered_map_t*          p_parent_map;
    unordered_map_t*          p_cost_map;
    directed_graph_node_t*    p_current;
    directed_graph_node_t*    p_child;
    unordered_set_iterator_t* p_child_iterator;
    weight_t*                 p_weight;
    list_t*                   p_weight_list;
    size_t                    i;

    if (!p_source)          return NULL;
    if (!p_target)          return NULL;
    if (!p_weight_function) return NULL;

    p_open_set = heap_t_alloc(4,
                              INITIAL_CAPACITY,
                              LOAD_FACTOR,
                              hash_function,
                              equals_function,
                              priority_cmp);

    if (!p_open_set) 
    {
        return NULL;
    }

    p_closed_set = unordered_set_t_alloc(INITIAL_CAPACITY,
                                         LOAD_FACTOR,
                                         hash_function,
                                         equals_function);

    if (!p_closed_set) 
    {
        heap_t_free(p_open_set);
        return NULL;
    }

    p_parent_map = unordered_map_t_alloc(INITIAL_CAPACITY,
                                         LOAD_FACTOR,
                                         hash_function,
                                         equals_function);

    if (!p_parent_map) 
    {
        heap_t_free(p_open_set);
        unordered_set_t_free(p_closed_set);
        return NULL;
    }

    p_cost_map = unordered_map_t_alloc(INITIAL_CAPACITY,
                                       LOAD_FACTOR,
                                       hash_function,
                                       equals_function);

    if (!p_cost_map)
    {
        heap_t_free(p_open_set);
        unordered_set_t_free(p_closed_set);
        unordered_map_t_free(p_parent_map);
        return NULL;
    }

    p_weight_list = list_t_alloc(INITIAL_CAPACITY);

    if (!p_weight_list) 
    {
        heap_t_free(p_open_set);
        unordered_set_t_free(p_closed_set);
        unordered_map_t_free(p_parent_map);
        unordered_map_t_free(p_cost_map);
        return NULL;
    }

    p_weight = malloc(sizeof(*p_weight));
    p_weight->weight = 0.0;

    heap_t_add(p_open_set, p_source, p_weight);
    unordered_map_t_put(p_parent_map, p_source, NULL);
    unordered_map_t_put(p_cost_map, p_source, p_weight);
    list_t_push_back(p_weight_list, p_weight);

    while (heap_t_size(p_open_set) > 0)
    {
        p_current = heap_t_extract_min(p_open_set);

        if (equals_function(p_current, p_target)) 
        {
            p_list = traceback_path(p_target, p_parent_map);
            heap_t_free(p_open_set);
            unordered_set_t_free(p_closed_set);
            unordered_map_t_free(p_parent_map);
            unordered_map_t_free(p_cost_map);
            return p_list;
        }

        unordered_set_t_add(p_closed_set, p_current);

        p_child_iterator = 
                unordered_set_iterator_t_alloc(
                    directed_graph_node_t_children_set(p_current));

        while (unordered_set_iterator_t_has_next(p_child_iterator)) 
        {
            unordered_set_iterator_t_next(p_child_iterator, &p_child);

            if (unordered_set_t_contains(p_closed_set, p_child)) {
                continue;
            }

            double tmp_cost = 
                ((weight_t*) unordered_map_t_get(p_cost_map, 
                                                 p_current))->weight;

            tmp_cost += *directed_graph_weight_function_t_get(
                    p_weight_function, 
                    p_current, 
                    p_child);

            if (!unordered_map_t_contains_key(p_parent_map, p_child)) 
            {
                p_weight = malloc(sizeof(*p_weight));
                p_weight->weight = tmp_cost;

                heap_t_add(p_open_set, p_child, p_weight);
                unordered_map_t_put(p_parent_map, p_child, p_current);
                unordered_map_t_put(p_cost_map, p_child, p_weight);
            }
            else if (tmp_cost < 
                    ((weight_t*) unordered_map_t_get(p_cost_map, 
                                                     p_child))->weight)
            {
                p_weight = malloc(sizeof(*p_weight));
                p_weight->weight = tmp_cost;

                heap_t_decrease_key(p_open_set, p_child, p_weight);
                unordered_map_t_put(p_parent_map, p_child, p_current);
                unordered_map_t_put(p_cost_map, p_child, p_weight);
            }
        }

        unordered_set_iterator_t_free(p_child_iterator);
    }

    /* Once here, return a empty path in order to denote the fact that the 
       target node is not reachable from source node. */
    heap_t_free(p_open_set);
    unordered_set_t_free(p_closed_set);
    unordered_map_t_free(p_parent_map);
    unordered_map_t_free(p_cost_map);
    p_list = list_t_alloc(10);

    /* Deallocate the weights. */
    for (i = 0; i < list_t_size(p_weight_list); ++i) 
    {
        free(list_t_get(p_weight_list, i));
    }

    return p_list;
}

directed_graph_node.h:

#ifndef DIRECTED_GRAPH_NODE_H
#define DIRECTED_GRAPH_NODE_H

#include "unordered_set.h"
#include <stdbool.h>
#include <string.h>

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct directed_graph_node_t directed_graph_node_t;

    /***************************************************************************
    * The function for testing node equality.                                  *
    ***************************************************************************/  
    bool equals_function(void* a, void* b);

    /***************************************************************************
    * The function for computing the hash values for nodes.                    *
    ***************************************************************************/  
    size_t hash_function(void* v);

    /***************************************************************************
    * Allocates a new directed graph node with given name.                     *
    ***************************************************************************/  
    directed_graph_node_t* directed_graph_node_t_alloc(char* name);

    /***************************************************************************
    * Creates an arc (p_tail, p_head) and returns true if the arc is actually  *
    * created. 'p_tail' is called a "parent" of 'p_head', and 'p_head' is      *
    * called a "child" of 'p_tail'.                                            *  
    ***************************************************************************/  
    bool                   
    directed_graph_node_t_add_arc(directed_graph_node_t* p_tail,
                                  directed_graph_node_t* p_head);

    /***************************************************************************
    * Returns true if 'p_node' has a child 'p_child_candidate'.                *
    ***************************************************************************/  
    bool directed_graph_node_t_has_child
    (directed_graph_node_t* p_node, directed_graph_node_t* p_child_candidate);

    /***************************************************************************
    * Removes the arc (p_tail, p_node) between the two nodes.                  *
    ***************************************************************************/  
    bool directed_graph_node_t_remove_arc(directed_graph_node_t* p_tail,
                                          directed_graph_node_t* p_head);

    /***************************************************************************
    * Returns the textual representation of the node.                          *
    ***************************************************************************/  
    char* directed_graph_node_t_to_string(directed_graph_node_t* p_node);

    /***************************************************************************
    * Returns the set containing all the child nodes of the given node.        *
    ***************************************************************************/  
    unordered_set_t* 
    directed_graph_node_t_children_set(directed_graph_node_t* p_node);

    /***************************************************************************
    * Returns the set containing all the parent nodes of the given node.       *
    ***************************************************************************/  
    unordered_set_t*
    directed_graph_node_t_parent_set(directed_graph_node_t* p_node);

    /***************************************************************************
    * Removes all the arcs involving the input node.                           *
    ***************************************************************************/  
    void directed_graph_node_t_clear(directed_graph_node_t* p_node);

    /***************************************************************************
    * Deallocates the node.                                                    *
    ***************************************************************************/  
    void directed_graph_node_t_free(directed_graph_node_t* p_node);

#ifdef  __cplusplus
}
#endif

#endif  /* DIRECTED_GRAPH_NODE_H */

directed_graph_node.c:

#include "directed_graph_node.h"
#include "unordered_set.h"
#include <stdbool.h>
#include <string.h>

typedef struct directed_graph_node_t {
    char* p_name;
    char* p_text;
    unordered_set_t* p_parent_node_set;
    unordered_set_t* p_child_node_set;
} directed_graph_node_t;

static const size_t INITIAL_CAPACITY = 16;
static const size_t MAXIMUM_NAME_STRING_LEN = 80;
static const float  LOAD_FACTOR = 1.0f;

bool equals_function(void* a, void* b)
{
    if (!a || !b) return false;

    return strcmp(((directed_graph_node_t*) a)->p_name,
                  ((directed_graph_node_t*) b)->p_name) == 0;
}

size_t hash_function(void* v) 
{
    size_t ret;
    size_t i;
    char* pc;

    if (!v) return 0;

    ret = 0;
    i = 1;
    pc = ((directed_graph_node_t*) v)->p_name;

    while (*pc) 
    {
        ret += *pc * i;
        ++i;
        ++pc;
    }

    return ret;
}

static const size_t MAXIMUM_NAME_LENGTH = 80;

directed_graph_node_t* directed_graph_node_t_alloc(char* name)
{
    directed_graph_node_t* p_node = malloc(sizeof(*p_node));
    char* p_text;

    if (!p_node) return NULL;

    p_node->p_name = name;

    p_text = malloc(sizeof(char) * MAXIMUM_NAME_STRING_LEN); 

    if (!p_text)
    { 
        free(p_node);
        return NULL;
    }

    p_node->p_child_node_set = unordered_set_t_alloc(INITIAL_CAPACITY,
                                                     LOAD_FACTOR,
                                                     hash_function,
                                                     equals_function);
    if (!p_node->p_child_node_set)
    {
        free(p_text);
        free(p_node);
        return NULL;
    }

    p_node->p_parent_node_set = unordered_set_t_alloc(INITIAL_CAPACITY,
                                                      LOAD_FACTOR,
                                                      hash_function,
                                                      equals_function);
    if (!p_node->p_parent_node_set) 
    {
        unordered_set_t_free(p_node->p_child_node_set);
        free(p_text);
        free(p_node);
        return NULL;
    }

    snprintf(p_text, 
             MAXIMUM_NAME_STRING_LEN, 
             "[directed_graph_node_t: id = %s]",
             name);

    p_node->p_name = name;
    p_node->p_text = p_text;
    return p_node;
}

bool                   
directed_graph_node_t_add_arc(directed_graph_node_t* p_tail,
                              directed_graph_node_t* p_head)
{
    if (!p_tail || !p_head) return false;

    if (!unordered_set_t_add(p_tail->p_child_node_set, p_head)) 
    {
        return false;
    }

    if (!unordered_set_t_add(p_head->p_parent_node_set, p_tail))
    {
        unordered_set_t_remove(p_tail->p_child_node_set, p_head);
        return false;
    }

    return true;
}

bool directed_graph_node_t_has_child
(directed_graph_node_t* p_node, directed_graph_node_t* p_child_candidate)
{
    if (!p_node || !p_child_candidate) return false;

    return unordered_set_t_contains(p_node->p_child_node_set, 
                                    p_child_candidate);
}

bool directed_graph_node_t_remove_arc(directed_graph_node_t* p_tail,
                                      directed_graph_node_t* p_head)
{
    if (!p_tail || !p_head) return false;

    unordered_set_t_remove(p_tail->p_child_node_set, p_head);
    unordered_set_t_remove(p_head->p_parent_node_set, p_tail);
    return true;
}

char* directed_graph_node_t_to_string(directed_graph_node_t* p_node)
{
    if (!p_node) return "NULL node";

    return p_node->p_text;
}

unordered_set_t* 
directed_graph_node_t_children_set(directed_graph_node_t* p_node)
{
    return p_node ? p_node->p_child_node_set : NULL;
}

unordered_set_t* 
directed_graph_node_t_parent_set(directed_graph_node_t* p_node)
{
    return p_node ? p_node->p_parent_node_set : NULL;
}

void directed_graph_node_t_clear(directed_graph_node_t* p_node)
{
    unordered_set_iterator_t* p_iterator;
    directed_graph_node_t*    p_tmp_node;

    if (!p_node) return;

    p_iterator = unordered_set_iterator_t_alloc(p_node->p_child_node_set);

    while (unordered_set_iterator_t_has_next(p_iterator)) 
    {
        unordered_set_iterator_t_next(p_iterator, &p_tmp_node);

        if (strcmp(p_node->p_name, p_tmp_node->p_name) != 0) 
        {
            unordered_set_t_remove(p_tmp_node->p_parent_node_set, p_node);
        }
    }

    p_iterator = unordered_set_iterator_t_alloc(p_node->p_parent_node_set);

    while (unordered_set_iterator_t_has_next(p_iterator))
    {
        unordered_set_iterator_t_next(p_iterator, &p_tmp_node);

        if (strcmp(p_node->p_name, p_tmp_node->p_name) != 0) 
        {
            unordered_set_t_remove(p_tmp_node->p_child_node_set, p_node);
        }
    }

    unordered_set_t_clear(p_node->p_parent_node_set);
    unordered_set_t_clear(p_node->p_child_node_set);
}

void directed_graph_node_t_free(directed_graph_node_t* p_node) 
{
    unordered_set_iterator_t* p_iterator;
    directed_graph_node_t* p_tmp_node;

    if (!p_node) return;

    directed_graph_node_t_clear(p_node);
    unordered_set_t_free(p_node->p_child_node_set);
    unordered_set_t_free(p_node->p_parent_node_set);
    free(p_node);
}

utils.h:

#ifndef GRAPH_UTILS_H
#define GRAPH_UTILS_H

#include "directed_graph_node.h"
#include "unordered_map.h"
#include "weight_function.h"
#include "list.h"

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct point_3d_t {
        double x;
        double y;
        double z;
    } point_3d_t;

    typedef struct graph_data_t {
        directed_graph_node_t**           p_node_array;
        directed_graph_weight_function_t* p_weight_function;
        unordered_map_t*                  p_point_map;
    } graph_data_t;

    point_3d_t* random_point(double maxx, double maxy, double maxz);

    double point_3d_t_distance(point_3d_t* p_a, point_3d_t* p_b);

    directed_graph_node_t* choose(directed_graph_node_t** p_table,
                                  const size_t size);

    graph_data_t* create_random_graph(const size_t nodes, 
                                      size_t edges,
                                      const double maxx,
                                      const double maxy,
                                      const double maxz);

    list_t* traceback_path(directed_graph_node_t* p_target,
                           unordered_map_t* p_parent_map);

    bool is_valid_path(list_t* p_path);

    double compute_path_cost(
    list_t* p_path, directed_graph_weight_function_t* p_weight_function);

#ifdef  __cplusplus
}
#endif

#endif  /* GRAPH_UTILS_H */

utils.c:

#include "directed_graph_node.h"
#include "unordered_map.h"
#include "utils.h"
#include "list.h"
#include <math.h>

point_3d_t* random_point(double maxx, double maxy, double maxz) 
{
    point_3d_t* p_ret = malloc(sizeof(*p_ret));

    if (!p_ret) return NULL;

    p_ret->x = ((double) rand() / (double) RAND_MAX) * maxx;
    p_ret->y = ((double) rand() / (double) RAND_MAX) * maxy;
    p_ret->z = ((double) rand() / (double) RAND_MAX) * maxz;

    return p_ret;
}

double point_3d_t_distance(point_3d_t* p_a, point_3d_t* p_b) 
{
    double dx = p_a->x - p_b->x;
    double dy = p_a->y - p_b->y;
    double dz = p_a->z - p_b->z;

    return sqrt(dx * dx + dy * dy + dz * dz);
}

directed_graph_node_t* choose(directed_graph_node_t** p_table,
                                     const size_t size)
{
    size_t index = rand() % size;
    return p_table[index];
}

graph_data_t* create_random_graph(const size_t nodes, 
                                  size_t edges,
                                  const double maxx,
                                  const double maxy,
                                  const double maxz)
{
    size_t i;
    char* p_name;

    directed_graph_node_t*              p_tail;
    directed_graph_node_t*              p_head;
    directed_graph_weight_function_t*   p_weight_function;
    unordered_map_t*                    p_point_map;
    point_3d_t*                         p_a;
    point_3d_t*                         p_b;
    graph_data_t*                       p_ret;

    p_ret = malloc(sizeof(*p_ret));

    if (!p_ret) return NULL;

    directed_graph_node_t** p_node_array = 
            malloc(sizeof(directed_graph_node_t*) * nodes);

    if (!p_ret) 
    {
        free(p_ret);
        return NULL;
    }

    if (!(p_weight_function = 
            directed_graph_weight_function_t_alloc(hash_function,
                                                   equals_function)))
    {
        free(p_ret);
        free(p_node_array);
        return NULL;
    }

    if (!(p_point_map = unordered_map_t_alloc(16, 
                                              1.0f, 
                                              hash_function,
                                              equals_function)))  
    {
        directed_graph_weight_function_t_free(p_weight_function);
        free(p_ret);
        free(p_node_array);
        return NULL;
    }

    for (i = 0; i < nodes; ++i) 
    {
        p_name = malloc(sizeof(char) * 20);
        sprintf(p_name, "%d", i);
        p_node_array[i] = directed_graph_node_t_alloc(p_name);
//        printf("%s\n", directed_graph_node_t_to_string(p_node_array[i]));
        unordered_map_t_put(p_point_map, 
                            p_node_array[i], 
                            random_point(maxx, maxy, maxz));
    }

    while (edges > 0)
    {
        p_tail = choose(p_node_array, nodes);
        p_head = choose(p_node_array, nodes);

        p_a = unordered_map_t_get(p_point_map, p_tail);
        p_b = unordered_map_t_get(p_point_map, p_head);

        directed_graph_node_t_add_arc(p_tail, p_head);

        directed_graph_weight_function_t_put(
                p_weight_function,
                p_tail,
                p_head,
                1.2 * point_3d_t_distance(p_a, p_b));

        --edges;
    }

    p_ret->p_node_array      = p_node_array;
    p_ret->p_weight_function = p_weight_function;
    p_ret->p_point_map       = p_point_map;

    return p_ret;
}

list_t* traceback_path(directed_graph_node_t* p_target,
                       unordered_map_t* p_parent_map)
{
    list_t* p_ret;
    directed_graph_node_t* p_current;

    if (!p_target)     return NULL;
    if (!p_parent_map) return NULL;

    p_ret = list_t_alloc(10);

    if (!p_ret)        return NULL;

    p_current = p_target;

    while (p_current) 
    {
        list_t_push_front(p_ret, p_current);
        p_current = unordered_map_t_get(p_parent_map, p_current);
    }

    return p_ret;
}

bool is_valid_path(list_t* p_path)
{
    size_t i;
    size_t sz;

    if (!p_path) return false;

    /* A empty path is defined to be valid. */
    if ((sz = list_t_size(p_path)) == 0) return true;

    for (i = 0; i < sz - 1; ++i) 
    {
        if (!directed_graph_node_t_has_child(list_t_get(p_path, i),
                                             list_t_get(p_path, i + 1))) 
        {
            return false;
        }
    }

    return true;
}

double compute_path_cost(list_t* p_path, 
                         directed_graph_weight_function_t* p_weight_function)
{
    size_t i;
    size_t sz;
    double cost = 0.0;

    if (!p_path) return 0.0;

    /* A empty path is defined to be valid. */
    if ((sz = list_t_size(p_path)) == 0) return 0.0;

    for (i = 0; i < sz - 1; ++i) 
    {
        cost += *directed_graph_weight_function_t_get(p_weight_function,
                                                      list_t_get(p_path, i),
                                                      list_t_get(p_path, i + 1));
    }

    return cost;
}

weight_function.h:

#ifndef WEIGHT_FUNCTION_H
#define WEIGHT_FUNCTION_H

#include "directed_graph_node.h"
#include <stdbool.h>

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct directed_graph_weight_function_t 
                   directed_graph_weight_function_t;

    /***************************************************************************
    * Allocates a new, empty weight function.                                  *
    ***************************************************************************/  
    directed_graph_weight_function_t* 
    directed_graph_weight_function_t_alloc(size_t (*p_hash_function)(void*),
                                           bool (*p_equals_function)(void*, 
                                                                     void*));

    /***************************************************************************
    * Associates the weight 'weight' with the arc ('p_tail', 'p_head').        *
    ***************************************************************************/  
    bool directed_graph_weight_function_t_put
        (directed_graph_weight_function_t* p_function,
         directed_graph_node_t* p_tail,
         directed_graph_node_t* p_head,
         double weight);

    /***************************************************************************
    * Reads the weight for the arc ('p_tail', 'p_head').                       *
    ***************************************************************************/  
    double* directed_graph_weight_function_t_get(
            directed_graph_weight_function_t* p_function,
            directed_graph_node_t* p_tail,
            directed_graph_node_t* p_head);

    /***************************************************************************
    * Deallocate the weight function.                                          *
    ***************************************************************************/  
    void directed_graph_weight_function_t_free
        (directed_graph_weight_function_t* p_function);

#ifdef  __cplusplus
}
#endif

#endif  /* WEIGHT_FUNCTION_H */

weight_function.c:

#include "weight_function.h"
#include "unordered_map.h"

typedef struct directed_graph_weight_function_t {
    unordered_map_t* p_first_level_map;
    size_t (*p_hash_function)(void*);
    bool (*p_equals_function)(void*, void*);
} directed_graph_weight_function_t;

static size_t INITIAL_CAPACITY = 16;
static size_t LOAD_FACTOR = 1.0f;

directed_graph_weight_function_t* directed_graph_weight_function_t_alloc
                                 (size_t (*p_hash_function)(void*),
                                  bool (*p_equals_function)(void*, void*))
{
    directed_graph_weight_function_t* p_ret;

    if (!p_hash_function)   return NULL;
    if (!p_equals_function) return NULL;

    p_ret = malloc(sizeof(*p_ret));

    if (!p_ret) return NULL;

    p_ret->p_first_level_map = unordered_map_t_alloc(INITIAL_CAPACITY,
                                                     LOAD_FACTOR,
                                                     p_hash_function,
                                                     p_equals_function);
    p_ret->p_hash_function   = p_hash_function;
    p_ret->p_equals_function = p_equals_function;
    return p_ret;
}

bool directed_graph_weight_function_t_put
    (directed_graph_weight_function_t* p_weight_function,
     directed_graph_node_t* p_tail,
     directed_graph_node_t* p_head,
     double weight)
{
    unordered_map_t* p_tmp_map;
    double* p_weight;

    if (!p_weight_function) return false;
    if (!p_tail)            return false;
    if (!p_head)            return false;

    p_tmp_map = unordered_map_t_get(p_weight_function->p_first_level_map,
                                    p_tail);

    if (p_tmp_map) 
    {
        p_weight = malloc(sizeof(double));
        *p_weight = weight;
        unordered_map_t_put(p_tmp_map, p_head, p_weight);
        return unordered_map_t_contains_key(p_tmp_map, p_head);
    }

    p_tmp_map = unordered_map_t_alloc(INITIAL_CAPACITY,
                                      LOAD_FACTOR,
                                      p_weight_function->p_hash_function,
                                      p_weight_function->p_equals_function);

    if (!p_tmp_map) return false;

    unordered_map_t_put(p_weight_function->p_first_level_map, 
                        p_tail, 
                        p_tmp_map);

    if (!unordered_map_t_contains_key(p_weight_function->p_first_level_map, 
                                      p_tail)) return false;

    p_weight = malloc(sizeof(double));
    *p_weight = weight;

    unordered_map_t_put(p_tmp_map, p_head, p_weight);

    if (!unordered_map_t_contains_key(p_tmp_map, p_head)) 
    {
        free(p_weight);
        return false;
    }

    return true;
}

double* directed_graph_weight_function_t_get(
        directed_graph_weight_function_t* p_function,
        directed_graph_node_t* p_tail,
        directed_graph_node_t* p_head)
{
    unordered_map_t* p_second_level_map;

    if (!p_function) return NULL;
    if (!p_tail)     return NULL;
    if (!p_head)     return NULL;

    if (!(p_second_level_map = unordered_map_t_get(
            p_function->p_first_level_map, p_tail))) 
    {
        return NULL;
    }

    return unordered_map_t_get(p_second_level_map, p_head);
}

void directed_graph_weight_function_t_free
    (directed_graph_weight_function_t* p_function)
{
    unordered_map_iterator_t* p_iterator;
    unordered_map_iterator_t* p_iterator_2;
    unordered_map_t*          p_map;
    directed_graph_node_t*    p_node;
    directed_graph_node_t*    p_node_2;
    double*                   p_weight;

    if (!p_function) return;

    p_iterator = unordered_map_iterator_t_alloc(p_function->p_first_level_map);

    while (unordered_map_iterator_t_has_next(p_iterator))
    {
        unordered_map_iterator_t_next(p_iterator, &p_node, &p_map);
        p_iterator_2 = unordered_map_iterator_t_alloc(p_map);

        while (unordered_map_iterator_t_has_next(p_iterator_2)) 
        {
            unordered_map_iterator_t_next(p_iterator_2, &p_node_2, &p_weight);
            free(p_weight);
        }

        unordered_map_t_free(p_map);
    }

    unordered_map_t_free(p_function->p_first_level_map);
}

So am I doing idiomatic C here? Memory leaks? Bugs?

For rapid demonstration you could try:

git clone [email protected]:coderodde/pathfinding.c.git && cd pathfinding.c && make 

The repository holding everything needed for demonstration is here.

Answer 1

WOW that's a lot of code to implement Dijkstra (is my first thought). Maybe you want to use C++?

Prefer not to include header files in header files unless you need to.

#include "directed_graph_node.h"
#include "weight_function.h"
#include "list.h"

You should use forward declarations in the header files when you can (assuming this is all your code). This will help in preventing circular dependencies.

Separation of Concerns

You are mixing memory management code with application logic. You should try and separate the two. In the function dijkstra() about half the function is dedicated to handling memory management and not implementing dijkstra. You should try and split this code into separate functions (Or create a container like class with functions that does the memory management for you (within its code).

If I was going to write this it would look like:

struct Container
{
    heap_t*                   p_open_set;
    unordered_set_t*          p_closed_set;
    unordered_map_t*          p_parent_map;
    unordered_map_t*          p_cost_map;
    list_t*                   p_weight_list;
    weight_t*                 p_weight;
};
void initContainer(Container* container)
{
    container->p_open_set    = buildOpenSet();
    container->p_closed_set  = buildClosedSet();
    container->p_parent_map  = buildParentMap();
    container->p_cost_map    = buildCosntMap();
    container->p_weight_list = list_t_alloc(INITIAL_CAPACITY);
    container->p_weight      = malloc(sizeof(*p_weight)); 

    if (container->p_weight){
        container->p_weight->weight = 0.0;
    }
};
void freeContaine(Container* container)
{
    // You will need to check these work with NULL but
    // if not write a quick wrapper.
    unordered_map_t_free(container->p_cost_map);
    unordered_map_t_free(container->p_parent_map);
    unordered_set_t_free(container->p_closed_set);
    heap_t_free(container->p_open_set);
    list_t_free(container->p_weight_list);
    free(container->p_weight);
}
int isContainerInit()
{
    return p_open_set && p_closed_set && p_parent_map ... etc;
}
... Add more functions as appropriate.

list_t* dijkstra(directed_graph_node_t* p_source,
                 directed_graph_node_t* p_target,
                 directed_graph_weight_function_t* p_weight_function)
{
    // Check the pre-conditions first.
    if (!p_source)          return NULL;
    if (!p_target)          return NULL;
    if (!p_weight_function) return NULL;


    // Event C allows you to declare objects
    // at any point in the function now.
    // So don't declare variables until you need them
    Container                 data;
    initContainer(&data);

    if (!isContainerInit(&data)) 
    {
        freeContaine(&data)
        return NULL;
    }

    addNodeToContainer(&data, p_source, p_weight);

    while (!isContainerEmpty(&data))
    {
        directed_graph_node_t* p_current = getNextCandidate(&data);

        if (equals_function(p_current, p_target)) 
        {
            list_t* p_list = traceback_path(p_target, p_parent_map);
            freeContaine(&data)
            return p_list;
        }

        addToSeenList(&data, p_current);

        unordered_set_iterator_t* p_child_iterator = getIterator(&data, p_current);

        while (unordered_set_iterator_t_has_next(p_child_iterator)) 
        {
            directed_graph_node_t*    p_child;
            unordered_set_iterator_t_next(p_child_iterator, &p_child);

            if (haveAlreadyFoundNode(&data, p_child)) {
                continue;
            }

            double tmp_cost = getWeightForTrip(&data, p_current, p_child);

            tmp_cost += *directed_graph_weight_function_t_get(
                    p_weight_function, 
                    p_current, 
                    p_child);

            addNodeToRoute(&data, p_child, tmp_cost);
        }

        unordered_set_iterator_t_free(p_child_iterator);
    }

    freeContaine(&data)
    list_t* p_list = list_t_alloc(10);

    /* Deallocate the weights. */
    for (i = 0; i < list_t_size(p_weight_list); ++i) 
    {
        free(list_t_get(p_weight_list, i));
    }

    return p_list;
}

Comments

Comments have to provide real information. Otherwise they are useless. Maintaining comments is as hard as maintiang the code. So unless they provide real information you should not write any. Bad comments are worse then no comments.

This comment does not provide me any more information than the function name already does. If you provded an WHY or HIGH LEVEL how that may be useful.

    /***************************************************************************
    * The function for testing node equality.                                  *
    ***************************************************************************/  
    bool equals_function(void* a, void* b);

Again useless comment, I get the same information from the function names as from the comment. So there seems little point in the comment.

    /***************************************************************************
    * The function for computing the hash values for nodes.                    *
    ***************************************************************************/  
    size_t hash_function(void* v);

I can keep doing this but you get the point. If the comment provides no more information than the function name they are a waste of space. And more importantly a cost to maintain.

    /***************************************************************************
    * Allocates a new directed graph node with given name.                     *
    ***************************************************************************/  
    directed_graph_node_t* directed_graph_node_t_alloc(char* name);

I would say this is actually bordering on useful.

    /***************************************************************************
    * Creates an arc (p_tail, p_head) and returns true if the arc is actually  *
    * created. 'p_tail' is called a "parent" of 'p_head', and 'p_head' is      *
    * called a "child" of 'p_tail'.                                            *  
    ***************************************************************************/  

Again not useful. I got all the information I needed from the name of the function.

    /***************************************************************************
    * Returns true if 'p_node' has a child 'p_child_candidate'.                *
    ***************************************************************************/  
    bool directed_graph_node_t_has_child
    (directed_graph_node_t* p_node, directed_graph_node_t* p_child_candidate);

Hash functions

Writing a good hash function is hard

size_t hash_function(void* v) 

I would definitely avoid using your own. There are lots on the internet. Most are trash. You seem to have picked one of the more trivial ones. Which I would not use beyond a toy project.