From a23cb6d6f011950b11789898c10e63f4473a5200 Mon Sep 17 00:00:00 2001 From: Mikkel Thestrup Date: Sun, 30 Nov 2025 14:24:52 +0100 Subject: Updated every file and function to follow style guide --- src/Graph.h | 40 ------------------------ src/LinkedList.c | 86 --------------------------------------------------- src/LinkedList.h | 50 ------------------------------ src/cycleDetection.h | 13 -------- src/cycle_detection.h | 13 ++++++++ src/graph.c | 16 ++++++++++ src/graph.h | 40 ++++++++++++++++++++++++ src/linked_list.c | 86 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/linked_list.h | 50 ++++++++++++++++++++++++++++++ src/main.c | 8 ++--- 10 files changed, 209 insertions(+), 193 deletions(-) delete mode 100644 src/Graph.h delete mode 100644 src/LinkedList.c delete mode 100644 src/LinkedList.h delete mode 100644 src/cycleDetection.h create mode 100644 src/cycle_detection.h create mode 100644 src/graph.c create mode 100644 src/graph.h create mode 100644 src/linked_list.c create mode 100644 src/linked_list.h diff --git a/src/Graph.h b/src/Graph.h deleted file mode 100644 index 3e7cfaa..0000000 --- a/src/Graph.h +++ /dev/null @@ -1,40 +0,0 @@ -#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.c b/src/LinkedList.c deleted file mode 100644 index aac05d6..0000000 --- a/src/LinkedList.c +++ /dev/null @@ -1,86 +0,0 @@ -#include "LinkedList.h" -#include - -LinkedList *linkedlist_new(void) { - LinkedList *ll = malloc(sizeof(LinkedList)); - if (!ll) return NULL; - - ll->head = NULL; - ll->tail = NULL; - ll->size = 0; - - return ll; -} - -void linkedlist_delete(LinkedList *ll) { - LinkedListNode *node = ll->head; - LinkedListNode *next; - - while (node) { - next = node->next; - free(node); - node = next; - } - - free(ll); -} - -LinkedListNode *linkedlist_append(LinkedList *ll, void *elem) { - LinkedListNode *new_node = malloc(sizeof(LinkedListNode)); - if (!new_node) return NULL; - - new_node->data = elem; - new_node->next = NULL; - if (!ll->head) { - new_node->prev = NULL; - ll->head = new_node; - ll->tail = new_node; - } else { - ll->tail->next = new_node; - new_node->prev = ll->tail; - ll->tail = new_node; - } - - ll->size++; - return new_node; -} - -void *linkedlist_popfront(LinkedList *ll) { - if (!ll->head) return NULL; - - void *elem = ll->head->data; - LinkedListNode *node = ll->head; - ll->head = ll->head->next; - - ll->size--; - free(node); - return elem; -} - -LinkedListNode *linkedlist_find(LinkedList *ll, void *elem) { - if (!ll->head) return NULL; - - LinkedListNode *node = ll->head; - while (node) { - /* !NOTE should use a given comparator function - * instead of '==' operator */ - if (node->data == elem) return node; - node = node->next; - } - - return NULL; // Couldn't find the element -} - -void *linkedlist_remove(LinkedList *ll, LinkedListNode *node) { - void *elem = node->data; - - if (node->prev) node->prev->next = node->next; - else ll->head = node->next; - - if (node->next) node->next->prev = node->prev; - else ll->tail = node->prev; - - free(node); - ll->size--; - return elem; -} diff --git a/src/LinkedList.h b/src/LinkedList.h deleted file mode 100644 index 363fb21..0000000 --- a/src/LinkedList.h +++ /dev/null @@ -1,50 +0,0 @@ -#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 deleted file mode 100644 index e1b62e0..0000000 --- a/src/cycleDetection.h +++ /dev/null @@ -1,13 +0,0 @@ -#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/cycle_detection.h b/src/cycle_detection.h new file mode 100644 index 0000000..df9607e --- /dev/null +++ b/src/cycle_detection.h @@ -0,0 +1,13 @@ +#ifndef CYCLE_DETECTION_H +#define CYCLE_DETECTION_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 cycle_detection(Graph *g); + +#endif // CYCLE_DETECTION_H diff --git a/src/graph.c b/src/graph.c new file mode 100644 index 0000000..4be2b44 --- /dev/null +++ b/src/graph.c @@ -0,0 +1,16 @@ +#include "graph.h" +#include + +Graph *graph_new(int n) { + Graph *graph = malloc(sizeof(Graph)); + if (!graph) return NULL; + + graph->numEdges = n; + graph->numVertices = 0; + graph->vertices = malloc(sizeof(Vertex[n])); + + return graph; +} + +void graph_add_edge(Graph *g, int i, int j) { +} diff --git a/src/graph.h b/src/graph.h new file mode 100644 index 0000000..ca90bbe --- /dev/null +++ b/src/graph.h @@ -0,0 +1,40 @@ +#ifndef GRAPH_H +#define GRAPH_H + +#include "linked_list.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_add_edge(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/linked_list.c b/src/linked_list.c new file mode 100644 index 0000000..c655fe4 --- /dev/null +++ b/src/linked_list.c @@ -0,0 +1,86 @@ +#include "linked_list.h" +#include + +LinkedList *linked_list_new(void) { + LinkedList *ll = malloc(sizeof(LinkedList)); + if (!ll) return NULL; + + ll->head = NULL; + ll->tail = NULL; + ll->size = 0; + + return ll; +} + +void linked_list_delete(LinkedList *ll) { + LinkedListNode *node = ll->head; + LinkedListNode *next; + + while (node) { + next = node->next; + free(node); + node = next; + } + + free(ll); +} + +LinkedListNode *linked_list_append(LinkedList *ll, void *elem) { + LinkedListNode *new_node = malloc(sizeof(LinkedListNode)); + if (!new_node) return NULL; + + new_node->data = elem; + new_node->next = NULL; + if (!ll->head) { + new_node->prev = NULL; + ll->head = new_node; + ll->tail = new_node; + } else { + ll->tail->next = new_node; + new_node->prev = ll->tail; + ll->tail = new_node; + } + + ll->size++; + return new_node; +} + +void *linked_list_popfront(LinkedList *ll) { + if (!ll->head) return NULL; + + void *elem = ll->head->data; + LinkedListNode *node = ll->head; + ll->head = ll->head->next; + + ll->size--; + free(node); + return elem; +} + +LinkedListNode *linked_list_find(LinkedList *ll, void *elem) { + if (!ll->head) return NULL; + + LinkedListNode *node = ll->head; + while (node) { + /* !NOTE should use a given comparator function + * instead of '==' operator */ + if (node->data == elem) return node; + node = node->next; + } + + return NULL; // Couldn't find the element +} + +void *linked_list_remove(LinkedList *ll, LinkedListNode *node) { + void *elem = node->data; + + if (node->prev) node->prev->next = node->next; + else ll->head = node->next; + + if (node->next) node->next->prev = node->prev; + else ll->tail = node->prev; + + free(node); + ll->size--; + return elem; +} diff --git a/src/linked_list.h b/src/linked_list.h new file mode 100644 index 0000000..4e6dadf --- /dev/null +++ b/src/linked_list.h @@ -0,0 +1,50 @@ +#ifndef LINKED_LIST_H +#define LINKED_LIST_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 *linked_list_new(); + +// Deallocate the given linked list, including all nodes +// (but _not_ the data they point to, the user owns that). +void linked_list_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 *linked_list_append(LinkedList *ll, void *elem); + +// Remove and return the first element from the given list. +// Pre: ll->size != 0 +void *linked_list_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 *linked_list_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 *linked_list_remove(LinkedList *ll, LinkedListNode *node); + +#endif // LINKED_LIST_H diff --git a/src/main.c b/src/main.c index e347552..2d0fdf7 100644 --- a/src/main.c +++ b/src/main.c @@ -1,4 +1,4 @@ -#include "cycleDetection.h" +#include "cycle_detection.h" #include #include @@ -11,9 +11,9 @@ int main(int argc, char **argv) { return 1; } - Graph *g = Graph_read(argv[1]); + Graph *g = graph_read(argv[1]); if(!g) return 2; - cycleDetection(g); - Graph_delete(g); + cycle_detection(g); + graph_delete(g); return 0; } -- cgit v1.2.3-70-g09d2