Created
August 16, 2024 11:39
-
-
Save llllvvuu/b1970123087707538c76db860336f648 to your computer and use it in GitHub Desktop.
topo.c
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stddef.h> | |
| #include <stdint.h> | |
| #include <stdio.h> | |
| #include <string.h> | |
| typedef struct { | |
| uint32_t u, v; | |
| } Edge; | |
| /** | |
| * Non-allocating topological sort. Time complexity: O(V + E). | |
| * @param[in] graph: array of edges, where vertices are numbered 0 to V - 1 | |
| * @param V: number of vertices | |
| * @param E: number of edges | |
| * @param[out] order: topological order | |
| * @param[out] levels: levels[v] > levels[u] if there is a path from u to v | |
| * @param[out] adj: length V array of pointers to adjacency lists | |
| * @param[out] adjBuf: buffer of length E backing `adj` | |
| * @param[out] inDegree: in-degree of each vertex | |
| * @param[out] outDegree: out-degree of each vertex | |
| */ | |
| void topo(Edge *graph, uint32_t V, size_t E, uint32_t *order, uint32_t *levels, | |
| uint32_t **adj, void *adjBuf, uint32_t *inDegree, | |
| uint32_t *outDegree) { | |
| memset(inDegree, 0, V * sizeof(uint32_t)); | |
| memset(outDegree, 0, V * sizeof(uint32_t)); | |
| for (size_t i = 0; i < E; i++) { | |
| outDegree[graph[i].u]++; | |
| inDegree[graph[i].v]++; | |
| } | |
| uint32_t *adjIdx = order; | |
| memset(adjIdx, 0, V * sizeof(uint32_t)); | |
| adj[0] = adjBuf; | |
| for (uint32_t i = 1; i < V; i++) { | |
| adj[i] = adj[i - 1] + outDegree[i - 1]; | |
| } | |
| for (size_t i = 0; i < E; i++) { | |
| adj[graph[i].u][adjIdx[graph[i].u]++] = graph[i].v; | |
| } | |
| uint32_t *queue = (uint32_t *)order; | |
| size_t queueSize = 0; | |
| for (uint32_t i = 0; i < V; i++) { | |
| if (inDegree[i] == 0) { | |
| levels[i] = 0; | |
| queue[queueSize++] = i; | |
| } | |
| } | |
| for (uint32_t i = 0; i < V; i++) { | |
| uint32_t u = queue[i]; | |
| for (uint32_t j = 0; j < outDegree[queue[i]]; j++) { | |
| uint32_t v = adj[u][j]; | |
| if (--inDegree[v] == 0) { | |
| levels[v] = levels[u] + 1; | |
| queue[queueSize++] = v; | |
| } | |
| } | |
| } | |
| } | |
| int main() { | |
| Edge graph[] = {{5, 11}, {7, 11}, {7, 8}, {3, 8}, {3, 10}, | |
| {11, 2}, {11, 9}, {11, 10}, {8, 9}}; | |
| uint32_t order[12]; | |
| uint32_t levels[12]; | |
| uint32_t *adj[12]; | |
| uint32_t adjBuf[9]; | |
| uint32_t inDegree[12]; | |
| uint32_t outDegree[12]; | |
| topo(graph, 12, 9, order, levels, adj, adjBuf, inDegree, outDegree); | |
| for (int i = 0; i < 12; i++) { | |
| printf("%d ", order[i]); | |
| } | |
| printf("\n"); | |
| for (int i = 0; i < 12; i++) { | |
| printf("%d: %d, ", i, levels[i]); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment