Deep clone node graph with pointer mapping

Challenge

Deep-cloning complex linked structures containing cycles (e.g. directed graphs) requires maintaining a mapping from old pointers to newly allocated clones to prevent infinite recursion and duplicate node creations.

Your Task

Implement:

struct gnode {
    int val;
    size_t num_neighbors;
    struct gnode *neighbors[4];
};

struct gnode *clone_graph(const struct gnode *start, struct gnode *pool, size_t pool_cap, size_t *pool_used);

Clone the connected graph component reachable from start into nodes allocated from pool.

Rules

1. If start == NULL, pool == NULL, pool_used == NULL, or pool_cap == 0, return NULL.
2. Initialize *pool_used = 0.
3. Allocate each new node from pool[(*pool_used)++]. If *pool_used > pool_cap, fail and return NULL.
4. Maintain a lookup table of (old_pointer -> new_pointer) to ensure each original node is cloned exactly once.
5. Rewire all neighbors in cloned nodes to point to their corresponding cloned neighbors.
6. Return the cloned node corresponding to start.

Input format

start: root node pointer; pool: pre-allocated node slab; pool_cap: pool capacity; pool_used: allocation counter.

Output format

Returns pointer to cloned root node, or NULL on error.

Constraints

C11 freestanding. Support cycles without infinite loops.

Starter code

#include <stddef.h>

/* The harness provides:
struct gnode {
    int val;
    size_t num_neighbors;
    struct gnode *neighbors[4];
};
*/

struct gnode *clone_graph(const struct gnode *start, struct gnode *pool, size_t pool_cap, size_t *pool_used) {
    (void)start; (void)pool; (void)pool_cap; (void)pool_used;
    return NULL;
}

Common mistakes

Infinite recursion on cycles; allocating duplicate nodes for the same original pointer.

Edge cases to handle

Self-referencing node (cycle of length 1); mutual cycles; linear graph; NULL input.

Background lessons

• malloc and the heap
• free and ownership