Depth first graph search with history

dfs.c

#include <stdio.h>
#include <stdlib.h>

typedef struct edge_s {
  struct edge_s *next;
  int to;
} Edge;

typedef struct vertex_s {
  Edge *edges;
  int label;
} Vertex;

void init_vertex(Vertex *v, int label) {
  v->edges = NULL;
  v->label = label;
}

#define MAX_VERTICES 1000

typedef struct graph_s {
  Vertex vertices[MAX_VERTICES];
  int n_vertices;
} Graph;

void init_graph(Graph *g) {
  for (int i = 0; i < MAX_VERTICES; ++i) init_vertex(g->vertices + i, i);
  g->n_vertices = 0;
}

void use_vertex(Graph *g, int i) {
  if (i > g->n_vertices - 1) g->n_vertices = i + 1;
}

void add_directed(Graph *g, int from, int to) {
  use_vertex(g, from);
  use_vertex(g, to);
  Edge *e = malloc(sizeof *e);
  e->next = g->vertices[from].edges;
  e->to = to;
  g->vertices[from].edges = e;
}

void add_undirected(Graph *g, int from, int to) {
  add_directed(g, from, to);
  add_directed(g, to, from);
}

void print(Graph *g) {
  for (int i = 0; i < g->n_vertices; ++i) {
    printf("%d:", i);
    for (Edge *e = g->vertices[i].edges; e; e = e->next)
      printf(" %d", e->to);
    printf("\n");
  }
}

typedef struct dfs_step_s {
  int arrived; // > 0 implies gray
  int departed; // > 0 implies black
  int parent; // valid when gray or black
} DfsStep;

void init_dfs_step(DfsStep *s) {
  s->arrived = s->departed = 0;
  s->parent = -1;
}

typedef struct dfs_history_s {
  DfsStep steps[MAX_VERTICES];
  int time;
} DfsHistory;

void init_dfs_history(DfsHistory *h) {
  for (int i = 0; i < MAX_VERTICES; ++i)
    init_dfs_step(h->steps + i);
  h->time = 0;
}

void print_dfs_history(Graph *g, DfsHistory *h) {
  for (int i = 0; i < g->n_vertices; ++i) {
    DfsStep *s = h->steps + i;
    printf("%d: [%d..%d] %d\n", i, s->arrived, s->departed, s->parent);
  }
  printf("end time: %d\n", h->time);
}

void traverse(Graph *g, DfsHistory *h, int from, int parent) {
  DfsStep *s = h->steps + from;
  if (s->arrived > 0) return;
  printf("traverse: %d\n", from);
  s->arrived = ++h->time;
  s->parent = parent;
  for (Edge *e = g->vertices[from].edges; e; e = e->next)
    traverse(g, h, e->to, from);
  s->departed = ++h->time;
}

void dfs_visit(Graph *g, DfsHistory *h) {
  init_dfs_history(h);
  for (int i = 0; i < g->n_vertices; ++i) traverse(g, h, i, -1);
}

int main(void) {
  Graph g[1];
  init_graph(g);
  add_undirected(g, 0, 1);
  add_undirected(g, 1, 2);
  add_undirected(g, 1, 3);
  add_undirected(g, 2, 3);
  add_undirected(g, 2, 4);
  add_undirected(g, 4, 0);
  print(g);
  DfsHistory h[1];
  dfs_visit(g, h);
  return 0;
}