From: Rusty Russell Date: Fri, 2 Dec 2011 03:36:58 +0000 (+1030) Subject: dgraph: new module for directed graphs. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=ed4ee95401575dd314f7ca5b3719e0e22ef0c6e5 dgraph: new module for directed graphs. --- diff --git a/ccan/dgraph/LICENSE b/ccan/dgraph/LICENSE new file mode 120000 index 00000000..dc314eca --- /dev/null +++ b/ccan/dgraph/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/dgraph/_info b/ccan/dgraph/_info new file mode 100644 index 00000000..10c82963 --- /dev/null +++ b/ccan/dgraph/_info @@ -0,0 +1,24 @@ +#include "config.h" +#include + +/** + * dgraph - simple directed graph module + * + * This code implements a simple directed graph, with nodes and edges. + * + * License: LGPL (v2.1 or any later version) + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/tlist\n"); + printf("ccan/typesafe_cb\n"); + return 0; + } + + return 1; +} diff --git a/ccan/dgraph/dgraph.c b/ccan/dgraph/dgraph.c new file mode 100644 index 00000000..9a6f6624 --- /dev/null +++ b/ccan/dgraph/dgraph.c @@ -0,0 +1,80 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ +#include +#include + +void dgraph_init_node(struct dgraph_node *n) +{ + tlist_init(&n->edge[DGRAPH_FROM]); + tlist_init(&n->edge[DGRAPH_TO]); +} + +static void free_edge(struct dgraph_edge *e) +{ + tlist_del_from(&e->n[DGRAPH_FROM]->edge[DGRAPH_FROM], + e, list[DGRAPH_FROM]); + tlist_del_from(&e->n[DGRAPH_TO]->edge[DGRAPH_TO], + e, list[DGRAPH_TO]); + free(e); +} + +void dgraph_clear_node(struct dgraph_node *n) +{ + struct dgraph_edge *e; + unsigned int i; + + for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) { + while ((e = tlist_top(&n->edge[i], list[i])) != NULL) { + assert(e->n[i] == n); + free_edge(e); + } + } +} + +void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to) +{ + struct dgraph_edge *e = malloc(sizeof(*e)); + e->n[DGRAPH_FROM] = from; + e->n[DGRAPH_TO] = to; + tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]); + tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]); +} + +bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to) +{ + struct dgraph_edge *e, *next; + + dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) { + if (e->n[DGRAPH_TO] == to) { + free_edge(e); + return true; + } + } + return false; +} + +static bool traverse_depth_first(struct dgraph_node *n, + enum dgraph_dir dir, + bool (*fn)(struct dgraph_node *, void *), + const void *data) +{ + struct dgraph_edge *e, *next; + + dgraph_for_each_edge_safe(n, e, next, dir) { + if (!traverse_depth_first(e->n[!dir], dir, fn, data)) + return false; + } + return fn(n, (void *)data); +} + +void dgraph_traverse(struct dgraph_node *n, + enum dgraph_dir dir, + bool (*fn)(struct dgraph_node *, void *), + const void *data) +{ + struct dgraph_edge *e, *next; + + dgraph_for_each_edge_safe(n, e, next, dir) { + if (!traverse_depth_first(e->n[!dir], dir, fn, data)) + break; + } +} diff --git a/ccan/dgraph/dgraph.h b/ccan/dgraph/dgraph.h new file mode 100644 index 00000000..dd1723fb --- /dev/null +++ b/ccan/dgraph/dgraph.h @@ -0,0 +1,67 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ +#ifndef CCAN_DGRAPH_H +#define CCAN_DGRAPH_H +#include "config.h" +#include +#include +#include + +enum dgraph_dir { + DGRAPH_FROM, + DGRAPH_TO +}; + +/* strust tlist_dgraph_edge: a list of edges */ +TLIST_TYPE(dgraph_edge, struct dgraph_edge); + +/** + * struct dgraph_node - a node in a directed graph. + * @edge: edges indexed by enum dgraph_dir. + * + * edge[DGRAPH_FROM] edges have n[DGRAPH_FROM] == this. + * edge[DGRAPH_TO] edges have n[DGRAPH_TO] == this. + */ +struct dgraph_node { + struct tlist_dgraph_edge edge[2]; +}; + +/** + * struct dgraph_edge - an edge in a directed graph. + * @list: our nodes's list of edges, indexed by enum dgraph_dir. + * @n: the nodes, indexed by enum dgraph_dir. + */ +struct dgraph_edge { + struct list_node list[2]; + struct dgraph_node *n[2]; +}; + +void dgraph_init_node(struct dgraph_node *n); +void dgraph_clear_node(struct dgraph_node *n); +void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to); +bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to); + +/* You can dgraph_clear_node() the node you're on safely. */ +#define dgraph_traverse_from(n, fn, arg) \ + dgraph_traverse((n), DGRAPH_FROM, \ + typesafe_cb_preargs(bool, void *, (fn), (arg), \ + struct dgraph_node *), \ + (arg)) + +#define dgraph_traverse_to(n, fn, arg) \ + dgraph_traverse((n), DGRAPH_TO, \ + typesafe_cb_preargs(bool, void *, (fn), (arg), \ + struct dgraph_node *), \ + (arg)) + +void dgraph_traverse(struct dgraph_node *n, + enum dgraph_dir dir, + bool (*fn)(struct dgraph_node *from, void *data), + const void *data); + +#define dgraph_for_each_edge(n, i, dir) \ + tlist_for_each(&(n)->edge[dir], i, list[dir]) + +#define dgraph_for_each_edge_safe(n, i, next, dir) \ + tlist_for_each_safe(&(n)->edge[dir], i, next, list[dir]) + +#endif /* CCAN_DGRAPH_H */ diff --git a/ccan/dgraph/test/run.c b/ccan/dgraph/test/run.c new file mode 100644 index 00000000..b868c18a --- /dev/null +++ b/ccan/dgraph/test/run.c @@ -0,0 +1,116 @@ +#include +/* Include the C files directly. */ +#include +#include + +static bool count_nodes(struct dgraph_node *n, unsigned int *count) +{ + (*count)++; + return true; +} + +static bool stop_traverse(struct dgraph_node *n, unsigned int *count) +{ + if (--(*count) == 0) + return false; + return true; +} + +int main(void) +{ + struct dgraph_node n1, n2, n3; + unsigned int count = 0; + + /* This is how many tests you plan to run */ + plan_tests(25); + + dgraph_init_node(&n1); + count = 0; + dgraph_traverse_from(&n1, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_to(&n1, count_nodes, &count); + ok1(count == 0); + + dgraph_init_node(&n2); + dgraph_add_edge(&n1, &n2); + count = 0; + dgraph_traverse_from(&n1, count_nodes, &count); + ok1(count == 1); + count = 0; + dgraph_traverse_to(&n1, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_from(&n2, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_to(&n2, count_nodes, &count); + ok1(count == 1); + + dgraph_init_node(&n3); + dgraph_add_edge(&n2, &n3); + count = 0; + dgraph_traverse_from(&n1, count_nodes, &count); + ok1(count == 2); + count = 0; + dgraph_traverse_to(&n1, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_from(&n2, count_nodes, &count); + ok1(count == 1); + count = 0; + dgraph_traverse_to(&n2, count_nodes, &count); + ok1(count == 1); + count = 0; + dgraph_traverse_from(&n3, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_to(&n3, count_nodes, &count); + ok1(count == 2); + + /* Check stopping traverse. */ + count = 1; + dgraph_traverse_from(&n1, stop_traverse, &count); + ok1(count == 0); + count = 2; + dgraph_traverse_from(&n1, stop_traverse, &count); + ok1(count == 0); + count = 3; + dgraph_traverse_from(&n1, stop_traverse, &count); + ok1(count == 1); + + dgraph_clear_node(&n1); + + count = 0; + dgraph_traverse_from(&n2, count_nodes, &count); + ok1(count == 1); + count = 0; + dgraph_traverse_to(&n2, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_from(&n3, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_to(&n3, count_nodes, &count); + ok1(count == 1); + + ok1(dgraph_del_edge(&n2, &n3)); + count = 0; + dgraph_traverse_from(&n2, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_to(&n2, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_from(&n3, count_nodes, &count); + ok1(count == 0); + count = 0; + dgraph_traverse_to(&n3, count_nodes, &count); + ok1(count == 0); + + ok1(!dgraph_del_edge(&n2, &n3)); + dgraph_clear_node(&n2); + + /* This exits depending on whether all tests passed */ + return exit_status(); +}