Dijkstra's shortest path algorithm in C

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;
}

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,
equ

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.

```
/

StackExchange Code Review Q#103881, answer score: 5