From 8285b08b1ca5d40e691bdc6bcd0e0a6dfd904135 Mon Sep 17 00:00:00 2001 From: phfr24 Date: Sat, 23 May 2026 16:39:17 -0300 Subject: [PATCH] dfs --- .gitignore | 1 + Makefile | 27 ++++++++++ dbg.h | 20 ++++++++ dfs.c | 142 ++++++++++++++++++++++++++++++++++++++++++++++++++++ graph/adj.c | 22 +++++--- graph/adj.h | 8 +-- graph/pr.c | 28 +++++++++++ graph/pr.h | 10 ++++ 8 files changed, 246 insertions(+), 12 deletions(-) create mode 100644 Makefile create mode 100644 dbg.h create mode 100644 dfs.c create mode 100644 graph/pr.c create mode 100644 graph/pr.h diff --git a/.gitignore b/.gitignore index cb4ead0..ff3c331 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,3 @@ .*.swp *.o +dfs diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..90d603b --- /dev/null +++ b/Makefile @@ -0,0 +1,27 @@ +CC := gcc +CFLAGS := -I. \ + -std=gnu90 \ + -g \ + -pedantic \ + -pedantic-errors \ + -Wall \ + -Wextra \ + -Wconversion \ + -Wstrict-prototypes \ + -Wshadow \ + -Wundef \ + -Wdouble-promotion \ + -Wno-variadic-macros + +objs := dfs.o graph/adj.o graph/pr.o +bin := dfs + +all : $(bin) + +clean : + rm -f $(bin) $(objs) + +.PHONY : all clean + +$(bin) : $(objs) + $(CC) $(CFLAGS) $(LDFLAGS) $^ $(LDLIBS) -o $@ diff --git a/dbg.h b/dbg.h new file mode 100644 index 0000000..422c681 --- /dev/null +++ b/dbg.h @@ -0,0 +1,20 @@ +#ifndef DBG_H +#define DBG_H + +#include +#include +#include +#include + +#define dbg(...) fprintf (stderr, __VA_ARGS__) + +#define fatal(x) \ + do \ + { \ + fprintf (stderr, "(%s:%d) %s () failed: %s errno: %s\n", __FILE__, \ + __LINE__, __func__, x, strerror (errno)); \ + exit (EXIT_FAILURE); \ + } \ + while (0) + +#endif /* DBG_H */ diff --git a/dfs.c b/dfs.c new file mode 100644 index 0000000..f189f43 --- /dev/null +++ b/dfs.c @@ -0,0 +1,142 @@ +#include "dbg.h" +#include "graph/adj.h" +#include "graph/pr.h" + +enum color +{ + WHITE = 0, + RED, + BLUE +}; + +struct v_state +{ + enum color c; +}; + +static __inline__ unsigned int +v_idx (struct graph *g, struct vertex *v) +{ + return (unsigned int)(v - g->v); +} + +static void +dfs_ (struct graph *g, struct graph *dt, struct v_state *vs, unsigned int ri) +{ + struct vertex *r, *n; + struct v_state *rs, *ns; + struct edge *e; + unsigned int ni; + + (rs = &vs[ri])->c = RED; + r = &g->v[ri]; + e = r->adj; + + while (e && (n = e->to)) + { + ni = v_idx (g, n); + ns = &vs[ni]; + + if (ns->c == WHITE) + { + if (new_arc (dt, ri, ni)) + fatal ("new_arc ()"); + dfs_ (g, dt, vs, ni); + } + + e = e->next; + } + + rs->c = BLUE; +} + +static struct graph * +dfs (struct graph *g) +{ + struct graph *dt; + struct v_state *vs; + unsigned int vi; + + if (!(dt = new_graph (g->nv))) + fatal ("new_graph ()"); + + if (!(vs = calloc (g->nv, sizeof *vs))) + fatal ("calloc ()"); + + for (vi = 0; vi < g->nv; ++vi) + { + if (vs[vi].c == WHITE) + dfs_ (g, dt, vs, vi); + } + + free (vs); + return dt; +} + +static struct graph * +create_example (int argc, char **argv) +{ + struct graph *g; + unsigned int nv, u, v; + int i; + + if (argc < 2) + { + fprintf (stderr, "Usage: %s [u1 v1 u2 v2 ...]\n", argv[0]); + exit (EXIT_FAILURE); + } + + nv = (unsigned int) atoi (argv[1]); + if (!(g = new_graph (nv))) + fatal ("new_graph ()"); + + /* parse edges in pairs */ + for (i = 2; i < argc - 1; i += 2) + { + u = (unsigned int) atoi (argv[i]); + v = (unsigned int) atoi (argv[i + 1]); + if (new_edge (g, u, v)) + fatal ("new_edge ()"); + } + + return g; +} + +int +main (int argc, char **argv) +{ + struct graph *g, *dt; + unsigned int i; + struct edge *e; + + g = create_example (argc, argv); + + if (!(dt = dfs (g))) + fatal ("dfs ()"); + + printf ("graph g:\n"); + for (i = 0; i < g->nv; ++i) + { + for (e = g->v[i].adj; e; e = e->next) + { + pr_edge (i, v_idx (g, e->to)); + putchar (' '); + } + if (g->v[i].adj) + putchar ('\n'); + } + + printf ("\ndfs tree dt:\n"); + for (i = 0; i < dt->nv; ++i) + { + for (e = dt->v[i].adj; e; e = e->next) + { + pr_arc (i, v_idx (dt, e->to)); + putchar (' '); + } + if (dt->v[i].adj) + putchar ('\n'); + } + + return 0; +} diff --git a/graph/adj.c b/graph/adj.c index ec9cd0c..e44f583 100644 --- a/graph/adj.c +++ b/graph/adj.c @@ -1,14 +1,17 @@ -#include "adj.h" -#include +#include "graph/adj.h" #include +#include struct graph * new_graph (unsigned int nv) { - struct graph *g; + struct graph *g; if (!nv) - return NULL; + { + errno = EINVAL; + return NULL; + } if (!(g = malloc (sizeof *g))) return NULL; @@ -30,10 +33,10 @@ new_arc (struct graph *g, unsigned int vi, unsigned int vj) struct edge *e; if (vi >= g->nv || vj >= g->nv) - return -EINVAL; + return -(errno = EINVAL); if (!(e = malloc (sizeof *e))) - return -ENOMEM; + return -errno; e->to = &g->v[vj]; e->next = g->v[vi].adj; @@ -47,11 +50,14 @@ new_edge (struct graph *g, unsigned int vi, unsigned int vj) { int err; + if (vi == vj) + return -(errno = EINVAL); + if ((err = new_arc (g, vi, vj))) return err; - if (vi != vj && (err = new_arc (g, vj, vi))) - return err; /* should delete the other arc but fuck it we ball */ + if ((err = new_arc (g, vj, vi))) + return err; return 0; } diff --git a/graph/adj.h b/graph/adj.h index 680d6b0..b0ec723 100644 --- a/graph/adj.h +++ b/graph/adj.h @@ -24,10 +24,10 @@ struct graph unsigned int nv; }; -struct graph * -new_graph (unsigned int nv); +struct graph *new_graph (unsigned int nv); -int -new_edge (struct graph *g, unsigned int vi, unsigned int vj); +int new_arc (struct graph *g, unsigned int vi, unsigned int vj); + +int new_edge (struct graph *g, unsigned int vi, unsigned int vj); #endif /* GRAPH_H */ diff --git a/graph/pr.c b/graph/pr.c new file mode 100644 index 0000000..491258c --- /dev/null +++ b/graph/pr.c @@ -0,0 +1,28 @@ +#include "graph/pr.h" +#include + +void +pr_vertex (unsigned int vi) +{ + printf ("%d", vi); +} + +void +pr_edge (unsigned int vi, unsigned int vj) +{ + putchar ('{'); + pr_vertex (vi); + putchar (','); + pr_vertex (vj); + putchar ('}'); +} + +void +pr_arc (unsigned int vi, unsigned int vj) +{ + putchar ('('); + pr_vertex (vi); + putchar (','); + pr_vertex (vj); + putchar (')'); +} diff --git a/graph/pr.h b/graph/pr.h new file mode 100644 index 0000000..8d0ebdd --- /dev/null +++ b/graph/pr.h @@ -0,0 +1,10 @@ +#ifndef GRAPH_PR_H +#define GRAPH_PR_H + +void pr_vertex (unsigned int vi); + +void pr_edge (unsigned int vi, unsigned int vj); + +void pr_arc (unsigned int vi, unsigned int vj); + +#endif /* GRAPH_PR_H */ -- 2.53.0