Add/update/reset files

4 files changed, 122 insertions, 0 deletions

diff --git a/src/Graph.h b/src/Graph.h
new file mode 100644
index 0000000..a0087ce
--- /dev/null
+++ b/src/Graph.h
@@ -0,0 +1,40 @@
+#ifndef GRAPH_H
+#define GRAPH_H
+
+#include "LinkedList.h"
+
+typedef struct Vertex Vertex;
+typedef struct Graph Graph;
+struct Vertex {
+	int id; // a number in [0; numVertices[
+	LinkedList *outNeighbours; // A linked list of vertices.
+	LinkedList *inNeighbours; // A linked list of vertices
+};
+
+struct Graph {
+	int numVertices;
+	int numEdges;
+	Vertex *vertices; // An array of numVertices vertices
+};
+
+// Allocates and constructs a new graph with n vertices.
+// Returns a pointer to the new graph, or NULL on error.
+// Post: the caller owns the graph.
+Graph *Graph_new(int n);
+
+// Adds an edge from the i'th to the j'th vertex (0-indexed).
+void Graph_addEdge(Graph *g, int i, int j);
+
+// Reads a graph from the given file and returns a newly
+// constructed Graph representing it.
+// Returns a pointer to the read graph, or NULL on error.
+// Post: the caller owns the graph.
+Graph *Graph_read(const char *filename);
+
+// Deallocates the given graph and all its associated memory.
+void Graph_delete(Graph *g);
+
+// Prints some useful information about the given graph.
+void Graph_print(Graph *g);
+
+#endif // GRAPH_H
diff --git a/src/LinkedList.h b/src/LinkedList.h
new file mode 100644
index 0000000..f30d44b
--- /dev/null
+++ b/src/LinkedList.h
@@ -0,0 +1,50 @@
+#ifndef LINKEDLIST_H
+#define LINKEDLIST_H
+
+// A linked list containing any type of pointer.
+// The linked list does _not_ own its elements.
+
+typedef struct LinkedList LinkedList;
+typedef struct LinkedListNode LinkedListNode;
+
+struct LinkedList {
+	LinkedListNode *head;
+	LinkedListNode *tail;
+	int size;
+};
+
+struct LinkedListNode {
+	LinkedListNode *next;
+	LinkedListNode *prev;
+	void *data;
+};
+
+// Allocate and initialize an empty linked list.
+// Returns: a pointer to the new linked list, or NULL on error.
+// Post: the caller owns the linked list.
+LinkedList *LinkedList_new();
+
+// Deallocate the given linked list, including all nodes
+// (but _not_ the data they point to, the user owns that).
+void LinkedList_delete(LinkedList *ll);
+
+// Append a the given element to the list.
+// The linked list does _not_ take ownership over the element
+// (only the linked list node).
+// Returns: a pointer to the node with the new element, or NULL on error.
+LinkedListNode *LinkedList_append(LinkedList *ll, void *elem);
+
+// Remove and return the first element from the given list.
+// Pre: ll->size != 0
+void *LinkedList_popFront(LinkedList *ll);
+
+// Find the linked list node containing the given element.
+// Returns: a pointer to the found node, or NULL if the element was not found.
+LinkedListNode *LinkedList_find(LinkedList *ll, void *elem);
+
+// Remove the given node from the given linked list (and deallocate it).
+// Pre: node must belong to ll
+// Returns: node->data
+void *LinkedList_remove(LinkedList *ll, LinkedListNode *node);
+
+#endif // LINKEDLIST_H
diff --git a/src/cycleDetection.h b/src/cycleDetection.h
new file mode 100644
index 0000000..e1b62e0
--- /dev/null
+++ b/src/cycleDetection.h
@@ -0,0 +1,13 @@
+#ifndef CYCLEDETECTION_H
+#define CYCLEDETECTION_H
+
+#include "Graph.h"
+
+// Runs Kahn's algorithm on the graph, and outputs 'CYCLE DETECTED!\n'
+// if a DAG cannot be created, or the vertices as a list fx. '4, 0, 1, 3, 2\n'
+// representing an ordering in the DAG.
+// The output is printed to stdout.
+// The input may be altered in the process.
+void cycleDetection(Graph *g);
+
+#endif // CYCLEDETECTION_H
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..1ab1ebc
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,19 @@
+#include "cycleDetection.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(int argc, char **argv) {
+	if(argc < 2) {
+		printf("Missing argument: input file\n");
+		printf("Usage:\n");
+		printf("%s <filename>\n", argv[0]);
+		return 1;
+	}
+	
+	Graph *g = Graph_read(argv[1]);
+	if(!g) return 2;
+	cycleDetection(g);
+	Graph_delete(g);
+	return 0;
+}