Programar 53: algoritmo dijkstra, c + linked list + priority queue

[HappyHippyHippo]

Após ler o artigo na revisto Programar, edição 53 de Agosto de 2016, com o tema Algoritmo de Dijkstra, só me ocorreu uma coisa.

A autora do artigo foi a própria a afirmar que a sua implementação é somente uma de várias maneiras de abordar o problema. No entanto, eu nunca gostei a solução de uso de uma tabela/matriz para a resolução do problema. Sempre achei que é um desperdício de memória e origina um código menos intuitivo do que o algoritmo realmente está a fazer.

Para isso, aqui está uma solução em C, que usa linked lists e uma priority queue (que para mim é provavelmente a solução mais fácil de perceber)

main.c

#include "graph.h"

#include <stdlib.h>
#include <stdio.h>

#define SOURCE "A"
#define DESTINATION "E"

int main(int argc, char ** argv) {
    Graph * graph = NULL;

    if ((graph = graph_create()) == NULL) {
        printf("Error allocation graph memory\n");
        exit(-1);
    }

    graph_add_node(graph, "G");
    graph_add_node(graph, "F");
    graph_add_node(graph, "E");
    graph_add_node(graph, "D");
    graph_add_node(graph, "C");
    graph_add_node(graph, "B");
    graph_add_node(graph, "A");

    graph_node_add_edge(graph_get_node(graph, "A"), 14, graph_get_node(graph, "F"));
    graph_node_add_edge(graph_get_node(graph, "A"),  9, graph_get_node(graph, "C"));
    graph_node_add_edge(graph_get_node(graph, "A"),  7, graph_get_node(graph, "B"));

    graph_node_add_edge(graph_get_node(graph, "B"), 15, graph_get_node(graph, "D"));
    graph_node_add_edge(graph_get_node(graph, "B"), 10, graph_get_node(graph, "C"));
    graph_node_add_edge(graph_get_node(graph, "B"),  7, graph_get_node(graph, "A"));

    graph_node_add_edge(graph_get_node(graph, "C"),  2, graph_get_node(graph, "F"));
    graph_node_add_edge(graph_get_node(graph, "C"), 11, graph_get_node(graph, "D"));
    graph_node_add_edge(graph_get_node(graph, "C"), 10, graph_get_node(graph, "B"));
    graph_node_add_edge(graph_get_node(graph, "C"),  9, graph_get_node(graph, "A"));

    graph_node_add_edge(graph_get_node(graph, "D"),  6, graph_get_node(graph, "E"));
    graph_node_add_edge(graph_get_node(graph, "D"), 11, graph_get_node(graph, "C"));
    graph_node_add_edge(graph_get_node(graph, "D"), 15, graph_get_node(graph, "B"));

    graph_node_add_edge(graph_get_node(graph, "E"),  9, graph_get_node(graph, "F"));
    graph_node_add_edge(graph_get_node(graph, "E"),  6, graph_get_node(graph, "D"));

    graph_node_add_edge(graph_get_node(graph, "F"),  9, graph_get_node(graph, "E"));
    graph_node_add_edge(graph_get_node(graph, "F"),  2, graph_get_node(graph, "C"));
    graph_node_add_edge(graph_get_node(graph, "F"), 14, graph_get_node(graph, "A"));

    graph_print(graph);

    GraphEdge ** path = graph_path(graph, graph_get_node(graph, SOURCE), graph_get_node(graph, DESTINATION));

    if (!(* path)) {
        printf("No path");
    } else {
        printf("N(%s) ", SOURCE);

        GraphEdge ** it = path;
        while (* it) {
            printf("-> E(%2d -> %s)", (*it)->cost, (*it)->target->ID);
            it++;
        }
    }

    free(path);
    graph_destroy(& graph);

    return 0;
}

graph.h

#ifndef GRAPH_H
#define GRAPH_H

/// Tipos de dados usados na definição de uma (di)grafo
typedef struct GraphEdge GraphEdge;
typedef struct GraphNode GraphNode;
typedef struct Graph Graph;

/// Estrutura usada para guardar a informação de uma aresta do (di)grafo
struct GraphEdge {
    GraphNode * owner;
    GraphEdge * next;

    unsigned int cost;
    GraphNode * target;
};

/// Estrutura usada para guardar a informação de um nó do (di)grafo
struct GraphNode {
    Graph * owner;
    GraphNode * next;

    char * ID;
    GraphEdge * edge_list;
    unsigned int edge_count;

    struct {
        GraphEdge * path;
        unsigned int cost;
        unsigned int steps;
    } tree;
};

/// Estrutura usada para guardar a informação de um (di)grafo
struct Graph {
    GraphNode * node_list;
    unsigned int node_count;
};

/// Função construtora de uma (di)grafo
///
/// @return Ponteiro para o (di)grafo criado
Graph * graph_create(void);

/// Função de destruição/libertação de memória de um (di)grafo
///
/// @param graph Referência para o ponteiro pque guarda o (di)grafo a ser
///              destruido
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_destroy(Graph ** graph);

/// Função usada para adicionar um novo nó ao (di)grafo
///
/// @param graph Referência ao (di)grafo que irá conter o nó criado
/// @param ID    String com o nome identificador do nó a ser criado
///
/// @return Ponteiro para o nó criado
GraphNode * graph_add_node(Graph * graph, char * ID);

/// Função usada para obter um nó do (di)grafo
///
/// @param graph Referência ao (di)grafo que contem o nó a ser obtido
/// @param ID    String com o nome identificador do nó a ser obtido
///
/// @return Ponteiro para o nó encontrado
GraphNode * graph_get_node(Graph * graph, char * ID);

/// Função usada para remover um nó do (di)grafo
///
/// @param graph Referência ao (di)grafo que contem o nó a ser removido
/// @param ID    String com o nome identificador do nó a ser removido
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_remove_node(Graph * graph, char * ID);

/// Função usada para adicionar uma nova aresta a um nó do (di)grafo
///
/// @param node  Referência ao nó do (di)grafo que irá conter a nova aresta
/// @param cost  Valor de custo de transitar na aresta
/// @para target Referência ao nó destino da aresta
///
/// @return Ponteiro para a aresta criado
GraphEdge * graph_node_add_edge(GraphNode * node, unsigned int cost, GraphNode * target);

/// Função usada para obter uma aresta de um nó do (di)grafo
///
/// @param node  Referência ao nó do (di)grafo que contem a aresta a ser obtida
/// @param index Índice da aresta a ser obtida
///
/// @return Ponteiro para a aresta obtida
GraphEdge * graph_node_get_edge(GraphNode * node, unsigned int index);

/// Função usada para remover uma aresta de um nó do (di)grafo
///
/// @param node  Referência ao nó do (di)grafo que contem a aresta a ser
///              removida
/// @param index Índice da aresta a ser removida
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_node_remove_edge(GraphNode * node, unsigned int index);

/// Função de escrita do (di)grafo na consola
///
/// @param graph Referência do (di)grafo a ser imprimido
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_print(Graph * graph);

/// Função de determinação do caminho mais curto
///
/// @param graph Referência do (di)grafo onde a pesquisa de percurso irá ser
///              efectuada
/// @param src   Referência ao nó de origem do caminho a ser pesquisado
/// @param dest  Referência ao nó de destino do caminho a ser pesquisado
///
/// @return Lista de aresta que compoem o caminho encontrado
///         Esta lista é alocada internamente e deverá ser libertada
///         posteriormente
GraphEdge ** graph_path(Graph * graph, GraphNode * src, GraphNode * dest);

#endif

graph.c

#include "graph.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// PRIVATE ----------------------------------------------------------------

/// Função de destruição de uma aresta
///
/// @param edge Referência ao ponteiro que guarda a aresta a ser destruida
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_destroy_edge(GraphEdge ** edge) {
    // validar argumentos
    if (!edge || !(*edge))
        return -1;

    // libertar a memória da aresta
    free(* edge);
    * edge = NULL;

    return 0;
}

/// Função de destruição de um nó
///
/// @param node Referência ao ponteiro que guarda o nóa a ser destruido
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_destroy_node(GraphNode ** node) {
    // validar argumentos
    if (!node || !(*node))
        return -1;

    // ciclo de libertação de memória das arestas do nó
    GraphNode * aux = (GraphNode *) * node;
    while (aux->edge_count) {
        GraphEdge * del = aux->edge_list;
        aux->edge_list = aux->edge_list->next;
        aux->edge_count--;

        graph_destroy_edge(& del);
    }

    // libertar a memória do nó
    free((* node)->ID);
    free(* node);
    * node = NULL;

    return 0;
}

/// Função de impressão de uma aresta na consola
///
/// @param edge Referência â aresta que irá ser imprimida
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_print_edge(GraphEdge * edge) {
    // validar argumentos
    if (!edge)
        return -1;

    // aprestar a informação da aresta
    printf(" E(%2d -> %s),", edge->cost, edge->target->ID);

    return 0;
}

/// Função de impressão de um nó na consola
///
/// @param node Referência ao nó que irá ser imprimido
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_print_node(GraphNode * node) {
    // validar argumentos
    if (!node)
        return -1;

    // aprestar a informação do nó
    printf("    N(%s) -> ", node->ID);

    // ciclo de apresentação das arestas do nó
    GraphEdge * edge = node->edge_list;
    while (edge) {
        graph_print_edge(edge);
        edge = edge->next;
    }
    printf("\n");

    return 0;
}

/// Função usada para remover todas as arestas de um nó que tem como destino um
/// nó definido pelo ID dado como argumento da chamada da função
/// Esta implementação é necessária para garantir a coerencia dos dados após a
/// remoção de um nó de forma a eliminiar aresta para nós removidos
///
/// @param node Referência do nó que contem as arestas a serem elimindas
/// @param ID   Identificador do nó de destino das arestas a serem eliminadas
///
/// @return Valor inteiro que indica sucesso da operação ao ter o valor de zero
///          ou erro caso contrário
int graph_node_remove_edges_to(GraphNode * node, char * ID) {
    // validar argumentos
    if (!node || !ID)
        return -1;

    GraphEdge * del = NULL;

    // ciclo de remoção das arestas que sáo encontradas no início da lista
    while (node->edge_list && strcmp(node->edge_list->target->ID, ID) == 0) {
        del = node->edge_list;
        node->edge_list = node->edge_list->next;

        graph_destroy_edge(& del);
        node->edge_count--;
    }

    // ciclo de pesquisa e remoção das arestas no mei oda lista
    GraphEdge * it = node->edge_list;
    while (it && it->next) {
        if (strcmp(it->next->target->ID, ID) == 0) {
            del = it->next;
            it->next = it->next->next;

            graph_destroy_edge(& del);
            node->edge_count--;
        } else
            it = it->next;
    }

    return 0;
}

/// Tipo de dados que implementa um priority queue de arestas a ser usada
/// durante a execução do "dijkstra algorihtm"
typedef struct GraphEdgeQueue {
    struct GraphEdgeQueue * next;
    GraphEdge * edge;
} GraphEdgeQueue;

/// Função que insere uma aresta na queue tendo como parâmetro de prioridade, o
/// custo associado ao processo dado pelo custo a aresta adicionado ao custo
/// já calculado para chegar ao nó origem da aresta inserida
///
/// @param queue Referência à queue que irá guardar a aresta a ser inserida
/// @param edge  Referência à aresta a ser inserida na queue
///
/// @return Referência à queue final
GraphEdgeQueue * graph_edge_queue_push(GraphEdgeQueue * queue, GraphEdge * edge) {
    // validar argumentos
    if (!edge)
        return queue;

    // alocar memória para a nova entrada da queue
    GraphEdgeQueue * entry = NULL;
    if ((entry = malloc(sizeof(GraphEdgeQueue))) == NULL)
        return NULL;

    // inicializar a entrada
    entry->edge = edge;
    entry->next = NULL;

    // verificar se a queue se encnotra vazia ou que mesmo assim, a aresta
    // deverá ser inserida na primeira posição da queue (maior prioridade)
    if (!queue || queue->edge->owner->tree.cost + queue->edge->cost > entry->edge->owner->tree.cost + entry->edge->cost) {
        entry->next = queue;
        queue = entry;
    } else {
        // ciclo de pesquisa pela posição da queue onde a aresta deverá ser
        // inserida
        GraphEdgeQueue * it = queue;
        while (it->next && it->next->edge->owner->tree.cost + it->next->edge->cost <= entry->edge->owner->tree.cost + entry->edge->cost)
            it = it->next;

        // inserir a entrada na posição encontrada
        entry->next = it->next;
        it->next = entry;
    }

    return queue;
}

/// Função usada para remover um elemento da queue
///
/// @param queue Referência à queue que contem a aresta a ser removida
/// @param edge  Referência para um ponteiro que irá guardar a aresta removida
///
/// @return Referência à queue final
GraphEdgeQueue * graph_edge_queue_pop(GraphEdgeQueue * queue, GraphEdge ** edge) {
    // validar argumentos
    if (!queue || !edge)
        return queue;

    // remoção da entrada à cabeça
    GraphEdgeQueue * del = queue;
    queue = queue->next;
    * edge = del->edge;

    // libertação da memoria alocada para a entrada da queue
    free(del);

    return queue;
}

// PUBLIC ----------------------------------------------------------------

Graph * graph_create(void) {
    Graph * graph = NULL;

    // alocação de memória para o (di)grafo
    if ((graph = malloc(sizeof(Graph))) != NULL) {
        graph->node_list = NULL;
        graph->node_count = 0;
    }

    return graph;
}

int graph_destroy(Graph ** graph) {
    // validar argumentos
    if (!graph || !(*graph))
        return -1;

    // ciclo de libertação de memória dos nós do (di)grafo
    Graph * aux = (Graph *) * graph;
    while (aux->node_count) {
        GraphNode * del = aux->node_list;
        aux->node_list = aux->node_list->next;
        aux->node_count--;

        graph_destroy_node(& del);
    }

    // libertação de memória
    free(* graph);
    * graph = NULL;

    return 0;
}

GraphNode * graph_add_node(Graph * graph, char * ID) {
    // validar argumentos
    if (!graph || !ID)
        return NULL;

    GraphNode * node = NULL;

    // alocação de memória para o nó a ser inserido
    if ((node = malloc(sizeof(GraphNode))) == NULL)
        return NULL;

    size_t length = strlen(ID) + 1;
    if ((node->ID = malloc(length)) == NULL) {
        free(node);
        return NULL;
    }

    // inicialização do nó criado
    strcpy(node->ID, ID);
    node->owner = graph;
    node->next = graph->node_list;
    node->edge_list = NULL;    
    node->edge_count = 0;
    node->tree.path = NULL;
    node->tree.cost = 0;
    node->tree.steps = 0;

    // inserir o nó à cabeça da lista de nós do (di)grafo
    graph->node_list = node;
    graph->node_count++;

    return node;
}

GraphNode * graph_get_node(Graph * graph, char * ID) {
    // validar argumentos
    if (!graph || !ID)
        return NULL;

    // ciclo de pesquisa pelo no pretendido
    GraphNode * node = graph->node_list;
    while (node && strcmp(node->ID, ID) != 0)
        node = node->next;

    return node;
}

int graph_remove_node(Graph * graph, char * ID) {
    // validar argumentos
    if (!graph || !ID)
        return -1;

    // verificar se o (di)grafo náo tem nós
    if (!graph->node_list)
        return -2;

    GraphNode * it = NULL;
    GraphNode * del = NULL;

    // verificar se o nó a ser removido encontrasse à cabeça da lista
    if (strcmp(graph->node_list->ID, ID) == 0) {
        del = graph->node_list;
        graph->node_list = graph->node_list->next;
    } else {
        // ciclo de pesquisa pelo nó a ser removido
        it = graph->node_list;
        while (it->next && strcmp(it->next->ID, ID) != 0)
            it = it->next;

        // verificar se o nó foi encontrado e remover-lo da lista
        if (it->next) {
            del = it->next;
            it->next = it->next->next;
        }
    }

    // verificar se o nó foi encontrado
    if (!del)
        return -2;

    // remover de todos os nós que ficaram na lista, as arestas que possuem como
    // destino, o nó removido
    it = graph->node_list;
    while (it) {
        graph_node_remove_edges_to(it, ID);
        it = it->next;
    }

    // destruição do nó removido
    graph_destroy_node(& del);
    graph->node_count--;

    return 0;
}

GraphEdge * graph_node_add_edge(GraphNode * node, unsigned int cost, GraphNode * target) {
    // validar argumentos
    if (!node || !target || node->owner != target->owner)
        return NULL;

    // alocação de memória da aresta a ser criada
    GraphEdge * edge = NULL;
    if ((edge = malloc(sizeof(GraphEdge))) == NULL)
        return NULL;

    // inicialização da aresta alocada
    edge->owner = node;
    edge->next = node->edge_list;
    edge->cost = cost;
    edge->target = target;

    // inserir a aresta criada à cabeça de aresta do nó
    node->edge_list = edge;
    node->edge_count++;

    return edge;
}

GraphEdge * graph_node_get_edge(GraphNode * node, unsigned int index) {
    // validar argumentos
    if (!node || node->edge_count <= index)
        return NULL;

    // ciclo de pesquisa da aresta pretendida
    unsigned int it = 0;
    GraphEdge * edge = node->edge_list;
    while (it != index) {
        edge = edge->next;
        it++;
    }

    return edge;
}

int graph_node_remove_edge(GraphNode * node, unsigned int index) {
    // validar argumentos
    if (!node || node->edge_count <= index)
        return -1;

    GraphEdge * del = NULL;

    // verificar se a aresta a ser removido se necontra à cabeça da lista
    if (index == 0) {
        del = node->edge_list;
        node->edge_list = node->edge_list->next;
    } else {
        // ciclo de pesquisa pela aresta a ser removida
        unsigned int it = 0;
        GraphEdge * edge = node->edge_list;
        while (it != index - 1) {
            edge = edge->next;
            it++;
        }

        // remove a aresta encontrada da lista
        del = edge->next;
        edge->next = edge->next->next;
    }

    // destruição da aresta removida
    graph_destroy_edge(& del);
    node->edge_count--;

    return 0;
}

int graph_print(Graph * graph) {
    // validar argumentos
    if (!graph)
        return -1;

    printf("Graph :\n");

    // ciclo de impressãodos nós do (di)grafo
    GraphNode * node = graph->node_list;
    while (node) {
        graph_print_node(node);
        node = node->next;
    }

    return 0;
}

GraphEdge ** graph_path(Graph * graph, GraphNode * src, GraphNode * dest) {
    // validar argumentos
    if (!graph || !src || src->owner != graph || !dest || dest->owner != graph)
        return NULL;

    // inicialização dos dados de criação/composição da árvore de menor custo
    GraphNode * node = graph->node_list;
    while (node) {
        node->tree.path = NULL;
        node->tree.cost = 0;
        node->tree.steps = 0;
        node = node->next;
    }

    GraphEdgeQueue * queue = NULL;
    GraphNode * current = src;
    GraphEdge * edge = NULL;

    // ciclo que implementa o "dijkstra algorithm"
    current->tree.path = (GraphEdge * ) 1;
    do {
        // ciclo de inserção da lista de aresta do último nó que foi inserido na
        // árvore de menor custo
        edge = current->edge_list;
        while (edge) {
            // verificar se a aresta tem como destino um nó que já se encontra
            // na árvore de menor custo
            if (!edge->target->tree.path)
                queue = graph_edge_queue_push(queue, edge);
            edge = edge->next;
        }

        // verificar se exsitem arestas na queue
        if (queue) {
            // pesquisa pela aresta de menor custo na queue que não como destino
            // um nó que já se encontra na árvore de menor custo
            do {
                edge = NULL;
                queue = graph_edge_queue_pop(queue, & edge);
            } while (edge && edge->target->tree.path);

            // verificar se void encontrada um aresta válida
            if (edge) {
                // inserir o nó destino da aresta na árvore de menor custo
                current = edge->target;
                current->tree.path = edge;
                current->tree.cost = edge->owner->tree.cost + edge->cost;
                current->tree.steps = edge->owner->tree.steps + 1;
            }
        }
    } while (queue && current != dest);

    // ciclo de limpeza/destruição da queue
    while (queue)
        queue = graph_edge_queue_pop(queue, &edge);

    // gerar a lista de arestas que indicará a caminho encontrado
    GraphEdge ** path = NULL;
    unsigned int path_length = graph->node_count + 1;
    if ((path = malloc(sizeof(GraphEdge *) * path_length)) == NULL)
        return NULL;
    memset(path, 0, sizeof(GraphEdge *) * path_length);

    // verificar se o algoritmo encontrou um caminho
    if (current == dest) {
        // ciclo de escrita/composição do caminho encontrado no array alocado
        while (current != src) {
            path[current->tree.steps - 1] = current->tree.path;
            current = current->tree.path->owner;
        }
    }

    return path;
}