diff options
| author | Mikkel Thestrup <mithe24@student.sdu.dk> | 2025-12-04 16:14:30 +0100 |
|---|---|---|
| committer | Mikkel Thestrup <mithe24@student.sdu.dk> | 2025-12-04 16:14:30 +0100 |
| commit | 51d1da5bd095fd1b5efdeeda8210651271604427 (patch) | |
| tree | a31de012c04b837e0fdb8cc67797bbd49cb661e6 /src | |
| parent | eedea9591acf4936d4a2a8eaca289b3311e130b0 (diff) | |
| download | cycle-detector-51d1da5bd095fd1b5efdeeda8210651271604427.tar.gz cycle-detector-51d1da5bd095fd1b5efdeeda8210651271604427.zip | |
Added and changed current docstrings in format that doxygen expects
Diffstat (limited to 'src')
| -rw-r--r-- | src/cycle_detection.h | 33 | ||||
| -rw-r--r-- | src/graph.h | 138 | ||||
| -rw-r--r-- | src/linked_list.h | 142 | ||||
| -rw-r--r-- | src/vector.h | 143 |
4 files changed, 414 insertions, 42 deletions
diff --git a/src/cycle_detection.h b/src/cycle_detection.h index df9607e..e5e0220 100644 --- a/src/cycle_detection.h +++ b/src/cycle_detection.h @@ -1,13 +1,34 @@ +/** + * @file cycle_detection.h + * @brief Cycle detection and topological sorting for directed graphs. + * @details This module implements Kahn's algorithm to detect cycles in + * directed graphs and perform topological sorting. A topological + * sort is only possible for acyclic graphs (DAGs). + */ + #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. +/** + * @brief Detects cycles in a directed graph and performs topological sorting. + * + * @param g Pointer to the directed graph to analyze. + * Must not be NULL. + * + * @details Prints to stdout whether the given graph has a cycle. In that case + * in prints 'CYCLE DETECTED!', else it prints the graph in + * topological sorting i.e. '4, 0, 1, 3, 2'. + * + * @note The input graph @p g may be modified during execution. The function + * alters vertex in-degree counts and neighbor lists as part of the + * algorithm. If the original graph structure must be preserved, the + * caller should provide a copy. + * + * @see Graph + * @see Vertex + */ void cycle_detection(Graph *g); -#endif // CYCLE_DETECTION_H +#endif // !CYCLE_DETECTION_H diff --git a/src/graph.h b/src/graph.h index 54d4f7a..6461cc7 100644 --- a/src/graph.h +++ b/src/graph.h @@ -1,41 +1,147 @@ +/** + * @file graph.h + * @brief Directed graph implementation using adjacency lists. + * @details This module provides a directed graph data structure where each + * vertex maintains separate lists of outgoing and incoming neighbors, + * enabling efficient navigation in both directions. + */ + #ifndef GRAPH_H #define GRAPH_H #include "linked_list.h" +/** + * @struct Vertex + * @brief A single vertex in a directed graph. + * @details Each vertex is identified by a unique ID and maintains lists of + * vertices it points to and vertices that point to it. + */ typedef struct Vertex Vertex; + +/** + * @struct Graph + * @brief A directed graph container. + * @details Maintains an array of all vertices and tracks the total number + * of vertices and edges in the graph. + */ typedef struct Graph Graph; + +/** + * @struct Vertex + * @brief Represents a single vertex in a directed graph. + */ struct Vertex { - int id; // a number in [0; numVertices[ - LinkedList *out_neighbours; // A linked list of vertices. - LinkedList *in_neighbours; // A linked list of vertices + /** + * @brief Unique identifier for this vertex. + * @details A value in the range [0, num_vertices) where num_vertices + * is the total number of vertices in the graph. + */ + int id; + + /** + * @brief List of outgoing neighbors (successors). + * @details A LinkedList containing pointers to Vertex structures that + * this vertex points to (outgoing edges). Each element in the + * list is of type (Vertex*). + */ + LinkedList *out_neighbours; + + /** + * @brief List of incoming neighbors (predecessors). + * @details A LinkedList containing pointers to Vertex structures that + * point to this vertex (incoming edges). Each element in the + * list is of type (Vertex*). + */ + LinkedList *in_neighbours; }; +/** + * @struct Graph + * @brief A directed graph container structure. + * @details The graph is represented using an adjacency list model where + * both incoming and outgoing edges are tracked for each vertex. + */ struct Graph { + /** + * @brief The total number of vertices in the graph. + * @details Vertices are indexed from 0 to (num_vertices - 1). + */ int num_vertices; + + /** + * @brief The total number of edges in the graph. + * @details This count includes all directed edges. An edge from vertex + * A to vertex B is counted as a single edge. + */ int num_edges; - Vertex *vertices; // An array of numVertices vertices + + /** + * @brief Array of all vertices in the graph. + * @details An array of size num_vertices containing Vertex structures. + * Index i contains the vertex with id = i. The array is + * dynamically allocated and should be freed by the caller + * when the graph is no longer needed. + */ + Vertex *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. +/** + * @brief Allocates and constructs a new graph with n vertices. + * + * @param n The number of vertices in the graph. + * + * @return A pointer to the newly created graph, + * or NULL if memory allocation fails. + * + * @note The caller is responsible for freeing the returned graph + * using graph_delete(). + */ Graph *graph_new(int n); -// Adds an edge from the i'th to the j'th vertex (0-indexed). +/** + * @brief Adds a directed edge from vertex i to vertex j. + * + * @param g Pointer to the graph. + * @param i The source vertex (0-indexed). + * @param j The destination 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); +/** + * @brief Removes the directed edge from vertex i to vertex j. + * + * @param g Pointer to the graph. + * @param i The source vertex (0-indexed). + * @param j The destination vertex (0-indexed). + */ void graph_remove_edge(Graph *g, int i, int j); -// Deallocates the given graph and all its associated memory. +/** + * @brief Reads a graph from a file and constructs a Graph object. + * + * @param filename The path to the file containing the graph data. + * @return A pointer to the newly constructed graph, + * or NULL if the file cannot be read or memory allocation fails. + * + * @note The caller is responsible for freeing the returned graph + * using graph_delete(). + */ +Graph *graph_read(const char *filename); + +/** + * @brief Deallocates the given graph and all its associated memory. + * + * @param g Pointer to the graph to delete. + * If NULL, this function does nothing. + */ void graph_delete(Graph *g); -// Prints some useful information about the given graph. +/** + * @brief Prints information about the given graph to standard output. + * + * @param g Pointer to the graph to print. + */ void graph_print(Graph *g); -#endif // GRAPH_H +#endif // !GRAPH_H diff --git a/src/linked_list.h b/src/linked_list.h index 4e6dadf..0da0c25 100644 --- a/src/linked_list.h +++ b/src/linked_list.h @@ -1,50 +1,152 @@ +/** + * @file linked_list.h + * @brief Doubly-linked list implementation. + * @details This module provides a generic doubly-linked list data structure + * that can store pointers to any data type. The list maintains both + * head and tail pointers for efficient operations at both ends. + */ + #ifndef LINKED_LIST_H #define LINKED_LIST_H -// A linked list containing any type of pointer. -// The linked list does _not_ own its elements. - +/** + * @struct LinkedList + * @brief A doubly-linked list container. + * @details Maintains references to the first and last nodes in the list, + * as well as the current number of elements. + */ typedef struct LinkedList LinkedList; + +/** + * @struct LinkedListNode + * @brief A node within a doubly-linked list. + * @details Each node contains pointers to the next and previous nodes, + * allowing bidirectional traversal, and a generic data pointer. + */ typedef struct LinkedListNode LinkedListNode; +/** + * @struct LinkedList + * @brief A doubly-linked list container structure. + */ struct LinkedList { + /** + * @brief Pointer to the first node in the list. + * @details NULL if the list is empty. + */ LinkedListNode *head; + + /** + * @brief Pointer to the last node in the list. + * @details NULL if the list is empty. + */ LinkedListNode *tail; + + /** + * @brief The number of nodes currently in the list. + * @details Updated whenever nodes are added or removed. + */ int size; }; +/** + * @struct LinkedListNode + * @brief A single node in a doubly-linked list structure. + */ struct LinkedListNode { + /** + * @brief Pointer to the next node in the list. + * @details NULL if this is the last node. + */ LinkedListNode *next; + + /** + * @brief Pointer to the previous node in the list. + * @details NULL if this is the first node (head). + */ LinkedListNode *prev; + + /** + * @brief Generic pointer to the node's data. + * @details The caller is responsible for managing the memory + * pointed to by this pointer. This pointer can store any + * data type (int*, char*, struct*, etc.). + */ 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. +/** + * @brief Allocates and initializes an empty linked list. + * + * @return A pointer to the newly created linked list, or NULL if memory + * allocation fails. + * + * @note The caller is responsible for freeing the returned linked list + * using linked_list_delete(). + */ LinkedList *linked_list_new(); -// Deallocate the given linked list, including all nodes -// (but _not_ the data they point to, the user owns that). +/** + * @brief Deallocates the given linked list and all its nodes. + * + * @param ll Pointer to the linked list to delete. If NULL, this function + * does nothing. + * + * @note This function deallocates only the list structure and nodes, not + * the data they point to. The caller retains ownership of the data. + */ 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. +/** + * @brief Appends an element to the end of the linked list. + * + * @param ll Pointer to the linked list. + * @param elem Pointer to the element to append. + * + * @return A pointer to the newly created node containing the element, + * or NULL if memory allocation fails. + * + * @note The linked list does not take ownership of the element itself, + * only the node structure. The caller retains ownership of the + * data. + */ LinkedListNode *linked_list_append(LinkedList *ll, void *elem); -// Remove and return the first element from the given list. -// Pre: ll->size != 0 +/** + * @brief Removes and returns the first element from the linked list. + * + * @param ll Pointer to the linked list. + * + * @return The data pointer of the removed first element. + * + * @pre The list must not be empty (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. +/** + * @brief Finds the linked list node containing the given element. + * + * @param ll Pointer to the linked list. + * @param elem Pointer to the element to search for. + * + * @return A pointer to the node containing the element, or NULL if the + * element was not found in the list. + */ 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 +/** + * @brief Removes the given node from the linked list and deallocates it. + * + * @param ll Pointer to the linked list. + * @param node Pointer to the node to remove. + * + * @return The data pointer stored in the removed node. + * + * @pre The node must belong to the linked list ll. + * + * @note The node structure is deallocated, but the data is not. The + * caller retains ownership of the returned data. + */ void *linked_list_remove(LinkedList *ll, LinkedListNode *node); -#endif // LINKED_LIST_H +#endif // !LINKED_LIST_H diff --git a/src/vector.h b/src/vector.h index b329192..271fcff 100644 --- a/src/vector.h +++ b/src/vector.h @@ -1,26 +1,169 @@ +/** + * @file vector.h + * @brief Dynamic array (vector) implementation. + * @details This module provides a generic resizable array data structure + * that can store pointers to any data type. The vector automatically + * grows as elements are added, using a growth factor to amortize + * reallocation costs. + */ + #ifndef VECTOR_H #define VECTOR_H #include <stddef.h> +/** + * @def INITAL_CAPACITY + * @brief Initial capacity of a newly created vector. + * @details The vector will be allocated with space for this many elements + * when first created. This value is chosen to balance memory usage + * and the number of early reallocations. + */ #define INITAL_CAPACITY 10 + +/** + * @def GROWTH_FACTOR + * @brief Multiplicative factor for vector capacity growth. + * @details When the vector reaches capacity and needs to grow, the new + * capacity is calculated as (current_capacity * GROWTH_FACTOR). + * A factor of 2 provides good amortized performance. + */ #define GROWTH_FACTOR 2 +/** + * @struct Vector + * @brief A dynamic resizable array (vector) of generic pointers. + * @details The vector maintains an underlying array that grows dynamically + * as elements are added. It tracks both the number of elements + * currently stored (size) and the total allocated space (capacity). + */ typedef struct Vector Vector; + +/** + * @struct Vector + * @brief A dynamic array container structure. + */ struct Vector { + /** + * @brief Array of generic data pointers. + * @details A dynamically allocated array of (void*) pointers, + * referencing to the actual data. The array has space for + * at least @p capacity elements. The caller is responsible + * for managing the memory that these pointers reference. + */ void **data; + + /** + * @brief The number of elements currently stored in the vector. + * @details Valid indices range from 0 to (size - 1). This value is + * incremented when elements are added and decremented when + * elements are removed. + */ size_t size; + + /** + * @brief The total allocated space (in number of elements). + * @details The underlying @p data array has space for this many pointers. + * When size reaches capacity, the vector is reallocated with + * a new capacity of (capacity * GROWTH_FACTOR). Always + * capacity >= size. + */ size_t capacity; }; +/** + * @brief Allocates and initializes an empty vector. + * + * @return A pointer to the newly created vector, or NULL if memory + * allocation fails. + * + * @note The caller is responsible for freeing the returned vector + * using vector_delete(). + */ Vector *vector_new(void); + +/** + * @brief Deallocates the given vector. + * + * @param v Pointer to the vector to delete. If NULL, this function + * does nothing. + * + * @note This function deallocates only the vector structure, not the + * data it contains. The caller retains ownership of the data. + */ void vector_delete(Vector *v); + +/** + * @brief Appends an element to the end of the vector. + * + * @param v Pointer to the vector. + * @param element Pointer to the element to append. + * + * @note The vector does not take ownership of the element, only stores + * a pointer to it. + */ void vector_push(Vector *v, void *element); + +/** + * @brief Removes and returns the last element from the vector. + * + * @param v Pointer to the vector. + * + * @return The data pointer of the removed last element. + * + * @pre The vector must not be empty. + */ void *vector_pop(Vector *v); + +/** + * @brief Returns the element at the given index in the vector. + * + * @param v Pointer to the vector. + * @param index The index of the element to retrieve. + * + * @return The data pointer at the given index. + * + * @pre The index must be valid (0 <= index < vector_size(v)). + */ void *vector_get(Vector *v, size_t index); + +/** + * @brief Sets the element at the given index in the vector. + * + * @param v Pointer to the vector. + * @param index The index of the element to set. + * @param element Pointer to the new element. + * + * @pre The index must be valid (0 <= index < vector_size(v)). + */ void vector_set(Vector *v, size_t index, void *element); + +/** + * @brief Returns the number of elements in the vector. + * + * @param v Pointer to the vector. + * + * @return The number of elements currently in the vector. + */ size_t vector_size(Vector *v); + +/** + * @brief Checks if the vector is empty. + * + * @param v Pointer to the vector. + * + * @return Non-zero if the vector is empty, 0 otherwise. + */ int vector_is_empty(Vector *v); + +/** + * @brief Removes all elements from the vector. + * + * @param v Pointer to the vector. + * + * @note This function only clears the vector structure, not the data + * it contained. The caller retains ownership of the data. + */ void vector_clear(Vector *v); #endif // !VECTOR_H |