tree.c

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

// NOTE defer fclose(fp)
FILE* get_filestream(char* path) {
    FILE *fp;
    fp = fopen(path, "rt");
    if (!fp) {
      perror(path);
      exit(1);
    }
    return fp;
}

// Track our walk through the graph
typedef struct {
    int visited_count;
    bool* visited;
    int edges_created;
    int current_vert;
} Traversal;

typedef struct {
    int vert_count;
    int* edges;
    int* edge_counts;
} Graph;

Traversal* init_traversal(Graph* g) {
    Traversal* t = (Traversal*) malloc(sizeof(Traversal));
    t->visited_count = 0;
    t->current_vert = 0;
    t->visited = (bool*) malloc(sizeof(bool) * g->vert_count);
    memset(t->visited, false, g->vert_count);
    t->edges_created = 0;
    return t;
}

// Malloc and zero-fill the graph once we know the vert count
Graph* init_graph(int vert_count, Graph* g) {
    g->vert_count = vert_count;
    g->edges = (int*) malloc(sizeof(int) * vert_count * vert_count);
    memset(g->edges, 0, vert_count * vert_count);
    g->edge_counts = (int*) malloc(sizeof(int) * vert_count);
    memset(g->edges, 0, vert_count);
    return g;
}

void print_traversal(Traversal* t, Graph* g) {
    int visited_count;
    bool* visited;
    int edges_created;
    printf("Edges created: %d\n", t->edges_created);
    printf("Verts visited (%d total):\n", t->visited_count);
    for (int i = 0; i < g->vert_count; i++) {
        if (t->visited[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

void print_graph(Graph* g) {
    printf("Total vertices: %d\n", g->vert_count);
    for (int i = 0; i < g->vert_count; i++) {
        printf("%d -> ", i);
        for (int j = 0; j < g->edge_counts[i]; j++) {
            printf("%d ", g->edges[i * g->vert_count + j]);
        }
        printf("\n");
    }
}

// Recursively visit vertices through the graph
void visit_vertex(Traversal* t, Graph* g) {
    int edge_count = g->edge_counts[t->current_vert];
    t->visited[t->current_vert] = true;
    t->visited_count += 1;
    if (t->visited_count == g->vert_count) {
        return;
    }
    for (int i = 0; i < edge_count; i++) {
        int dest = g->edges[t->current_vert * g->vert_count + i];
        bool visited = t->visited[dest];
        if (!visited) {
            int this_vert = t->current_vert;
            t->current_vert = dest;
            visit_vertex(t, g);
            t->current_vert = this_vert;
        }
    }
}

void traverse(Graph* g) {
    Traversal* t = init_traversal(g);
    int edge_count = -1;
    while (t->visited_count < g->vert_count) {
        edge_count += 1;
        int unvisited;
        for (int i = 0; i < g->vert_count; i++) {
            if (!t->visited[i]) {
                unvisited = i;
                break;
            }
        }
        t->current_vert = unvisited;
        visit_vertex(t, g);
    }
    printf("%d\n", edge_count);
}

Graph* parse_input(FILE* file) {
    int count = 0;
    char c;
    bool parsing_count = true;
    bool parsing_src_vert = false;
    int src_vert = 0;
    bool parsing_dest_vert = false;
    char digits[16];
    int digits_idx = 0;
    Graph* g = (Graph*) malloc(sizeof(Graph));
    while (1) {
        c = fgetc(file);
        if (c == EOF) {
            break;
        }
        if (parsing_count) {
            if (c == '\n') {
                digits[digits_idx] = '\0';
                int count = atoi(digits);
                init_graph(count, g);
                parsing_count = false;
                parsing_src_vert = true;
                digits_idx = 0;
            } else {
                digits[digits_idx] = c;
                digits_idx += 1;
            }
        } else {
            // Parsing edge
            if (c == ' ') {
                digits[digits_idx] = '\0';
                src_vert = atoi(digits) - 1;
                digits_idx = 0;
            } else if (c == '\n') {
                digits[digits_idx] = '\0';
                int dest_vert = atoi(digits) - 1;
                // Assign edge from src to dst
                g->edges[src_vert * g->vert_count + g->edge_counts[src_vert]] = dest_vert;
                g->edge_counts[src_vert] += 1;
                // Assign edge from dest to src
                g->edges[dest_vert * g->vert_count + g->edge_counts[dest_vert]] = src_vert;
                g->edge_counts[dest_vert] += 1;
                digits_idx = 0;
            } else {
                digits[digits_idx] = c;
                digits_idx += 1;
            }
        }
    }
    return g;
}

int main(int argc, char* argv[]) {
    FILE* file = NULL;
    if (argc > 1) {
        file = get_filestream(argv[1]);
    } else {
        // Use tree/input.txt as the default input path
        file = get_filestream("tree/input.txt");
    }
    Graph* g = parse_input(file);
    // print_graph(g);
    traverse(g);
    fclose(file);
}