graph.h (2886B)
1 #ifndef GRAPH_H 2 #define GRAPH_H 3 4 #include <sys/queue.h> 5 #include "stack_u64.h" 6 7 typedef struct { 8 size_t n; 9 stack_u64_t *nbrs; 10 } graph_t; 11 12 typedef SIMPLEQ_HEAD(bfs_listhead, bfs_list_entry) bfs_queue_head_t; 13 14 typedef struct bfs_list_entry { 15 size_t x; 16 SIMPLEQ_ENTRY(bfs_list_entry) entries; 17 } bfs_list_entry_t; 18 19 typedef struct { 20 uint8_t *queued; 21 bfs_queue_head_t queue; 22 } graph_bfs_t; 23 24 /** 25 * Intialises a BFS struct 26 * 27 * Initialises a BFS struct which can be used for traversing the 28 * graph in BFS order, starting from the vertex v. This function 29 * allocates memory that needs to be cleared and freed. 30 * 31 * @param bfs pointer to the bfs struct that stores the state 32 * @param g the graph to preform BFS on 33 * @param v the vertex to start at 34 */ 35 void graph_bfs_init(graph_bfs_t *bfs, graph_t *g, const uint64_t v); 36 37 /** 38 * Clears a BFS struct 39 * 40 * @param bfs pointer to the BFS struct to clear 41 */ 42 void graph_bfs_clear(graph_bfs_t *bfs); 43 44 /** 45 * Get the next element in BFS search 46 * 47 * Function for getting the next vertex from a graph ordered by some BFS 48 * order, represented by an graph_bfs_t. This removes an element from 49 * the stored queue, and returns it (and updates the queue as needed). 50 * If there are no more vertices to visit this function returns 51 * UINT64_MAX. Note that the BFS struct is not cleared by this function, 52 * so this has to be done manually. 53 * 54 * @param bfs 55 * a bfs search struct representing the current state of a bfs search 56 * @param g 57 * the graph to traverse 58 */ 59 uint64_t graph_bfs_next(graph_bfs_t *bfs, const graph_t *g); 60 61 /** 62 * Initialise a new graph 63 * 64 * Initialises a new graph on n vertices. The vertex set will be [n], 65 * and the graph is initialised without any edges. The graph is 66 * represented in terms of neighbour lists. Graph is always considered 67 * to be undirected, but multiple edges and loops are allowed (i.e. more 68 * properly it is a multigraph). 69 * 70 * @param g pointer to the graph to inialise 71 * @param n the size (number of vertices) of the graph to initialise 72 */ 73 void graph_init(graph_t *g, const size_t n); 74 75 /** 76 * Clear a graph 77 * 78 * This assumes that g points to a graph that has been initialized. 79 * 80 * @param g pointer to the graph to clear 81 */ 82 void graph_clear(graph_t *g); 83 84 /** 85 * Add an edge to a graph 86 * 87 * This function adds an edge between vertices v and w in the graph g. 88 * The vertex v is added to the neighbour list of w and the vertex w is 89 * added to the neighbour list of v. This function can be called 90 * multiple times with the same arguments to add multiple edges between 91 * the same pair of vertices. If v == w we add a loop to the graph at 92 * vertex v. 93 * 94 * @param g pointer to the graph in which we add the edge 95 * @param v one of the vertices 96 * @param w the other of the vertices (may be same as v) 97 */ 98 void graph_add_edge(graph_t *g, const size_t v, const size_t w); 99 100 #endif