initial commit

2 files changed, 252 insertions, 0 deletions

diff --git a/comp2521/sna/Dijkstra.c b/comp2521/sna/Dijkstra.c
new file mode 100644
index 0000000..2600690
--- /dev/null
+++ b/comp2521/sna/Dijkstra.c
@@ -0,0 +1,153 @@
+#include "Dijkstra.h"
+
+#include "PQ.h"
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ShortestPaths {
+        int numNodes;    // The number of vertices in the graph
+
+        Vertex src;      // The source vertex
+
+        int *dist;       // An  array  of distances from the source vertex -
+                         // one for each vertex (the distance  from  src  to
+                         // itself is 0)
+                         // dist[v] contains the distance from src to v
+
+        PredNode **pred; // An  array  of  predecessor  lists - one for each
+                         // vertex
+                         // pred[v] contains the predecessor list for vertex
+                         // v
+}
+
+PredNode {
+        Vertex v;
+        struct PredNode *next;
+};
+*/
+
+static void free_pred_list(PredNode *head) {
+    for (PredNode *i = head; i != NULL;) {
+        PredNode *tmp = i->next;
+        free(i);
+        i = tmp;
+    }
+}
+
+static PredNode *add_pred_back(PredNode *head, const Vertex v) {
+    PredNode *ret = calloc(1, sizeof(PredNode));
+    ret->v = v;
+    // Empty Case.
+    if (head == NULL) {
+        return ret;
+    }
+    PredNode *last = head;
+    // Find the last element in the linked list.
+    for (PredNode *i = head->next; i != NULL; i = i->next) {
+        last = i;
+    }
+    last->next = ret;
+    return head;
+}
+
+// Finds the shortest path from src to all other vertices and stores this
+// information in a ShortestPaths struct.
+// However, if there are multiple shortest paths of the same weight, also store
+// such paths as preds.
+ShortestPaths dijkstra(Graph g, Vertex src) {
+
+    // Initialise return struct ret and allocate appropriate memory.
+    ShortestPaths ret;
+    ret.src = src;
+    const int num_nodes = GraphNumVertices(g);
+    ret.numNodes = num_nodes;
+    ret.dist = calloc((unsigned int)num_nodes, sizeof(int));
+    ret.pred = calloc((unsigned int)num_nodes, sizeof(PredNode));
+
+    // Set all distances as INT_MAX to represent infinity, but the src vertex
+    // as 0 to ensure it is chosen first.
+    for (int i = 0; i < num_nodes; ++i) {
+        ret.dist[i] = INT_MAX;
+    }
+    ret.dist[src] = 0;
+
+    // Initialise queue, insert itself in queue and initialise its distance
+    // as 0.
+    PQ queue = PQNew();
+    PQInsert(queue, src, ret.dist[src]);
+
+    // Perform Dijkstra's algorithm by looping through the queue until empty.
+    while (!PQIsEmpty(queue)) {
+        // Dequeue the vertex with the lowest weight.
+        const Vertex vertex = PQDequeue(queue);
+
+        // Loop through all adjacent vertices for the vertex.
+        AdjList adjacents = GraphOutIncident(g, vertex);
+        for (AdjList i = adjacents; i != NULL; i = i->next) {
+            const int v = i->v;
+            const int w = i->weight;
+            const int path = ret.dist[vertex] + w;
+
+            // Inefficient path, continue.
+            if (ret.dist[v] < path) {
+                continue;
+            }
+
+            // Better path than previously discovered. Free the current pred
+            // list and update distance.
+            if (ret.dist[v] > path) {
+                ret.dist[v] = path;
+                PQInsert(queue, v, ret.dist[v]);
+                free_pred_list(ret.pred[v]);
+                ret.pred[v] = NULL;
+            }
+
+            // Update pred list.
+            ret.pred[v] = add_pred_back(ret.pred[v], vertex);
+        }
+    }
+
+    // After performing the algorithm, we must set all INT_MAX distances back
+    // to zero to conform to the spec.
+    for (int i = 0; i < num_nodes; ++i) {
+        if (ret.dist[i] == INT_MAX) {
+            ret.dist[i] = 0;
+        }
+    }
+
+    return ret;
+}
+
+// Prints out the ShortestPaths structure.
+// Does not need to comply with any requirements.
+void showShortestPaths(ShortestPaths sps) {
+    printf("Shortest path\n");
+    printf("\tNumNodes: %d\n", sps.numNodes);
+    printf("\tsrc: %d\n", sps.src);
+    printf("\tdist\n");
+    for (int i = 0; i < sps.numNodes; ++i) {
+        printf("\t\t%d: %d\n", i, sps.dist[i]);
+    }
+    printf("\tpred\n");
+    for (int i = 0; i < sps.numNodes; ++i) {
+        printf("\t\t%d\n", i);
+        for (PredNode *j = sps.pred[i]; j != NULL; j = j->next) {
+            printf("\t\t\t%d\n", j->v);
+        }
+    }
+}
+
+// Frees all memory associated with a ShortestPaths structure.
+void freeShortestPaths(ShortestPaths sps) {
+    for (int i = 0; i < sps.numNodes; ++i) {
+        for (PredNode *j = sps.pred[i]; j != NULL;) {
+            PredNode *next = j->next;
+            free(j);
+            j = next;
+        }
+    }
+    free(sps.pred);
+    free(sps.dist);
+}
diff --git a/comp2521/sna/Dijkstra.h b/comp2521/sna/Dijkstra.h
new file mode 100644
index 0000000..0c3578b
--- /dev/null
+++ b/comp2521/sna/Dijkstra.h
@@ -0,0 +1,99 @@
+// Dijkstra ADT interface
+// COMP2521 Assignment 2
+
+// Note: You MUST NOT modify this file.
+
+#include <stdbool.h>
+
+#include "Graph.h"
+
+typedef struct PredNode {
+	Vertex v;
+	struct PredNode *next;
+} PredNode;
+
+typedef struct ShortestPaths {
+	int numNodes;    // The number of vertices in the graph
+	
+	Vertex src;      // The source vertex
+	
+	int *dist;       // An  array  of distances from the source vertex -
+	                 // one for each vertex (the distance  from  src  to
+	                 // itself is 0)
+	                 // dist[v] contains the distance from src to v
+	                 
+	PredNode **pred; // An  array  of  predecessor  lists - one for each
+	                 // vertex
+	                 // pred[v] contains the predecessor list for vertex
+	                 // v
+} ShortestPaths;
+
+/**
+ * Finds  all  shortest  paths  from  a given source vertex to all other
+ * vertices as discussed in the lectures.
+ *
+ * This  function  offers  one **additional feature** - if there is more
+ * than one shortest path from the source vertex to  another  vertex,  a
+ * vertex  could  have  multiple predecessors (see spec for an example).
+ * The function must keep track of multiple predecessors for each vertex
+ * (if  they  exist)  by storing the predecessor(s) in the corresponding
+ * linked list for that vertex. This will be discussed in detail in  the
+ * lecture.
+ * 
+ * For  example,  suppose that while finding the shortest paths from the
+ * source vertex 0 to all other vertices, we discovered  that  vertex  1
+ * has two possible predecessors on different shortest paths. 
+ * 
+ * Node 0
+ *   Distance
+ *     0 : X
+ *     1 : 2
+ *     2 : 1
+ *   Preds
+ *     0 : NULL
+ *     1 : [0]->[2]->NULL
+ *     2 : [0]->NULL
+ * 
+ * Node 1
+ *   Distance
+ *     0 : 2
+ *     1 : X
+ *     2 : 3
+ *   Preds
+ *     0 : [1]->NULL
+ *     1 : NULL
+ *     2 : [0]->NULL
+ * 
+ * Node 2
+ *   Distance
+ *     0 : 3
+ *     1 : 1
+ *     2 : X
+ *   Preds
+ *     0 : [1]->NULL
+ *     1 : [2]->NULL
+ *     2 : NULL
+ * 
+ * The  function  returns  a 'ShortestPaths' structure with the required
+ * information:
+ * - the number of vertices in the graph
+ * - the source vertex
+ * - distance array
+ * - array of predecessor lists
+ */
+ShortestPaths dijkstra(Graph g, Vertex src);
+
+/**
+ * This  function  is  for  you to print out the ShortestPaths structure
+ * while you are debugging/testing your implementation. 
+ * 
+ * We  will  not call this function during testing, so you may print out
+ * the given ShortestPaths structure in whatever format you want.
+ */
+void showShortestPaths(ShortestPaths sps);
+
+/**
+ * Frees all memory associated with the given ShortestPaths structure.
+ */
+void freeShortestPaths(ShortestPaths sps);
+