topo.c

topo.c

#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]);
  }
}