graph.c

graph.c

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

typedef struct graph_node {
    char *name;
    struct graph_node *parent;
    struct graph_node **children;
    size_t children_size;
    size_t children_n;
} node;

typedef struct graph {
    node *root;
} graph;

graph *create_graph(node *root);
node *create_node(const char *name);
void push_node(node *parent, node *n);
void trace_graph(graph *g);
void trace_node(node *n, int depth);
void destroy_graph(graph *g);
void destroy_node(node *n);

int main(void) {
    node *cat = create_node("cat");
    node *paw = create_node("paw");

    graph *g = create_graph(cat);

    push_node(cat, paw);
    push_node(cat, create_node("tail"));
    push_node(cat, create_node("ear"));
    push_node(paw, create_node("claw"));

    trace_graph(g);
    destroy_graph(g);

    return 0;
}

graph *create_graph(node *root) {
    graph *g = malloc(sizeof(graph));

    g->root = root;

    return g;
}

node *create_node(const char *name) {
    node *n = malloc(sizeof(node));

    n->name = malloc(sizeof(name));
    n->parent = NULL;
    n->children = NULL;
    n->children_size = 0;
    n->children_n = 0;

    memcpy(n->name, name, strlen(name) + 1);

    return n;
}

void push_node(node *parent, node *n) {
    n->parent = parent;

    if (parent->children_n == parent->children_size) {
        if (parent->children_size == 0) {
            parent->children_size = 1;
        } else {
            parent->children_size *= 2;
        }

        parent->children = realloc(
            parent->children,
            parent->children_size * sizeof(node));
    }

    parent->children[parent->children_n++] = n;
}

void trace_graph(graph *g) {
    trace_node(g->root, 0);
}

void trace_node(node *n, int depth) {
    if (n == NULL) { return; }

    printf("%*s%s%s\n", depth * 2, "", depth ? "- " : "", n->name);

    for (size_t i = 0; i < n->children_n; ++i) {
        trace_node(n->children[i], depth + 1);
    }
}

void destroy_graph(graph *g) {
    if (g == NULL) { return; }
    destroy_node(g->root);
    free(g);
}

void destroy_node(node *n) {
    if (n == NULL) { return; }

    free(n->name);

    for (size_t i = 0; i < n->children_n; ++i) {
        destroy_node(n->children[i]);
    }

    free(n->children);
    free(n);
}