Stanisław Strzelecki - kod

#include "graph.h"
#include "heap.h"
#include "memory.h"

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct Edge Edge;

typedef struct Vertex Vertex;

typedef struct Graph Graph;

/**
 * Struktura przechowująca wierzchołek grafu.
 */
struct Vertex
{
    List *edges;
    bool allowed;
    bool visited;
    Distance distance;
    Edge *from;
    String name;
};

/**
 * Struktura przechowująca krawędź grafu.
 */
struct Edge
{
    Vertex *to;
    uint32_t length;
    int32_t year;
    bool active;
    Edge *opposite;
    void *placeInList;
};

/**
 * Struktura przechowująca graf.
 */
struct Graph
{
    List *vertexes;
    List *emptyList;
    int32_t size;
    int32_t edgeSize;
};

Edge *makeEdge(Vertex *to, uint32_t length, int32_t year)
{
    Edge *edge = allocMisc(sizeof(Edge));
    edge->to = to;
    edge->length = length;
    edge->year = year;
    edge->active = true;
    return edge;
}


Graph *newGraph()
{
    Graph *graph = allocMisc(sizeof(Graph));
    if (!graph)
        return graph;
    graph->vertexes = newList();
    graph->emptyList = newList();
    graph->size = 0;
    graph->edgeSize = 0;

    if (!graph->vertexes || !graph->emptyList)
    {
        if (graph->vertexes)
            removeList(graph->vertexes);
        if (graph->emptyList)
            removeList(graph->emptyList);
        freeMemory(graph);
        return NULL;
    }
    return graph;
}


Edge *addEdge(Vertex *vertex1, Vertex *vertex2, uint32_t length, int32_t year, Graph *graph)
{
    Edge *edge1 = makeEdge(vertex2, length, year);
    Edge *edge2 = makeEdge(vertex1, length, year);
    if (!edge1 || !edge2)
    {
        freeMemory(edge1);
        freeMemory(edge2);
        return NULL;
    }

    edge1->opposite = edge2;
    edge2->opposite = edge1;
    addToList(vertex1->edges, edge1);
    addToList(vertex2->edges, edge2);
    edge1->placeInList = firstListElement(vertex1->edges);
    edge2->placeInList = firstListElement(vertex2->edges);
    graph->edgeSize++;
    return edge1;
}


void updateEdgeYear(Edge* edge, int32_t newYear)
{
    edge->year = newYear;
    edge->opposite->year = newYear;
}


void removeEdge(Edge* edge, Graph *graph)
{
    removeListElement(edge->placeInList);

    removeListElement(edge->opposite->placeInList);
    freeMemory(edge->opposite);

    freeMemory(edge);

    graph->edgeSize++;
}


Vertex *addVertex(String name, Graph *graph)
{
    Vertex *newVertex = allocMisc(sizeof(Vertex));
    if (!newVertex)
        return NULL;
    if (!addToList(graph->vertexes, newVertex))
    {
        freeMemory(newVertex);
        return NULL;
    }

    graph->size++;
    newVertex->edges = newList();
    newVertex->allowed = true;
    newVertex->visited = false;
    newVertex->distance = infDistance();
    newVertex->name = name;
    return newVertex;
}


void removeVertex(Vertex *vertex, Graph *graph)
{
    while (firstListElement(vertex->edges))
    {
        removeEdge(firstListElement(vertex->edges)->value, graph);
    }
    removeList(vertex->edges);
    freeMemory(vertex);
    graph->size--;
}


void removeGraph(Graph *graph)
{
    for (ListElement *element = firstListElement(graph->vertexes); element; element = nextListElement(element))
    {
        removeVertex(element->value, graph);
    }
    removeList(graph->vertexes);
    removeList(graph->emptyList);
    freeMemory(graph);
}


void cleanVertexes(Graph *graph)
{
    for (ListElement *element = firstListElement(graph->vertexes); element; element = nextListElement(element))
    {
        Vertex *vertex = element->value;
        vertex->visited = false;
        vertex->allowed = true;
        vertex->distance = infDistance();
        vertex->from = NULL;
    }
}


Distance shortestPath(Vertex *start, Vertex *target, List *zabronione, Graph *graph)
{
    cleanVertexes(graph);

    for (ListElement *element = firstListElement(zabronione); element; element = nextListElement(element))
    {
        Vertex *aktualVertex = element->value;
        aktualVertex->allowed = false;
        element = nextListElement(element);
        if (!element)
            break;
    }

    start->allowed = true;
    start->distance = newDistance();
    target->allowed = true;

    Heap *priorytyQueue = newHeap(graph->edgeSize);
    if (!priorytyQueue)
        return start->distance;
    pushHeap(priorytyQueue, start->distance, start);

    while (!isHeapEmpty(priorytyQueue))
    {
        Vertex *v = frontHeap(priorytyQueue);
        popHeap(priorytyQueue);
        if (v->visited)
            continue;
        v->visited = true;

        for (ListElement *element = firstListElement(v->edges); element; element = nextListElement(element))
        {
            Edge *e = element->value;
            if (!e->active || !e->to->allowed)
                continue;

            int32_t cmp = compareDistance(e->to->distance, modifyDistance(v->distance, e->length, e->year));
            e->to->distance = getBetterDistance(e->to->distance, modifyDistance(v->distance, e->length, e->year));
            if (cmp > 0)
            {
                e->to->from = e;
                pushHeap(priorytyQueue, e->to->distance, e->to);
            }
        }
    }

    removeHeap(priorytyQueue);
    Distance result = target->distance;
    if (result.howMany != 1)
        return target->distance;
    result.pathTo = newList();
    if (!result.pathTo)
        return result;

    addToList(result.pathTo, target);
    while (target != start)
    {
        if (!addToList(result.pathTo, target->from))
        {
            removeList(result.pathTo);
            result.pathTo = NULL;
            return result;
        }

        if (!addToList(result.pathTo, target->from->opposite->to))
        {
            removeList(result.pathTo);
            result.pathTo = NULL;
            return result;
        }
        target = target->from->opposite->to;
    }
    return result;
}