[ccan] [PATCH 2/4] aga: Abstract Graph Algorithms
David Gibson
david at gibson.dropbear.id.au
Mon Jul 7 22:51:01 EST 2014
This module implements some standard graph algoriths. Rather than
expecting a specific concrete representation of the graph, it uses
callbacks, so that the calling code can compute the graph edges on the fly.
The graph nodes can also be constructed as they're discovered, although
some information about them does then need to be retained for the life of
the algorithm.
Because the routines rely on a structure embedded within the callers
representation of the graph nodes/states, they're not re-entrant - only
one can be running at a time (per aga_node instance).
For now, the only algorithm we implement is depth first search, pretty
much the simplest there is. I plan to add breadth first search and
Dijkstra's algorithm in future.
Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
ccan/aga/LICENSE | 1 +
ccan/aga/_info | 34 +++++++
ccan/aga/aga.c | 64 +++++++++++++
ccan/aga/aga.h | 41 +++++++++
ccan/aga/test/helper.h | 19 ++++
ccan/aga/test/run-chain.c | 98 ++++++++++++++++++++
ccan/aga/test/run-grid.c | 222 ++++++++++++++++++++++++++++++++++++++++++++++
7 files changed, 479 insertions(+)
create mode 120000 ccan/aga/LICENSE
create mode 100644 ccan/aga/_info
create mode 100644 ccan/aga/aga.c
create mode 100644 ccan/aga/aga.h
create mode 100644 ccan/aga/test/helper.h
create mode 100644 ccan/aga/test/run-chain.c
create mode 100644 ccan/aga/test/run-grid.c
diff --git a/ccan/aga/LICENSE b/ccan/aga/LICENSE
new file mode 120000
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/aga/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/aga/_info b/ccan/aga/_info
new file mode 100644
index 0000000..d8f3957
--- /dev/null
+++ b/ccan/aga/_info
@@ -0,0 +1,34 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * aga - Abstract Graph Algorithms
+ *
+ * This modules contains several standard graph algorithms,
+ * implemented so that they don't rely on a specific represnetation of
+ * the graph structure. Instead, user supplied callbacks can compute
+ * the graph's edges as required. Graph nodes can even be constructed
+ * on the fly as they're discovered by edge traversal.
+ *
+ * License: LGPL (v2.1 or any later version)
+ * Author: David Gibson <david at gibson.dropbear.id.au>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ return 0;
+ }
+
+ if (strcmp(argv[1], "testdepends") == 0) {
+ printf("ccan/array_size\n");
+ printf("ccan/container_of\n");
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/aga/aga.c b/ccan/aga/aga.c
new file mode 100644
index 0000000..d510616
--- /dev/null
+++ b/ccan/aga/aga.c
@@ -0,0 +1,64 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include "config.h"
+
+#include <stdbool.h>
+
+#include <ccan/aga/aga.h>
+
+void aga_init(struct aga_graph *g, aga_edge_fn edge_fn)
+{
+ g->sequence = 0;
+ g->edge_fn = edge_fn;
+}
+
+static bool aga_start(struct aga_graph *g)
+{
+ /* FIXME: Need some atomic magic here to protect against
+ * concurrent entry */
+ g->sequence++;
+ return false;
+}
+
+static void aga_finish(struct aga_graph *g)
+{
+}
+
+static bool update_node(struct aga_graph *g, struct aga_node *node)
+{
+ if (node->sequence == g->sequence)
+ return false;
+
+ node->sequence = g->sequence;
+ return true;
+}
+
+static void dfs(struct aga_graph *g, struct aga_node *node,
+ aga_visit_fn fn, void *opaque)
+{
+ void *p;
+ struct aga_edge edge;
+
+ if (!update_node(g, node))
+ return;
+
+ fn(g, node, opaque);
+
+ p = g->edge_fn(g, node, &edge, NULL);
+ while (p) {
+ dfs(g, edge.to, fn, opaque);
+ p = g->edge_fn(g, node, &edge, p);
+ }
+}
+
+int aga_depth_first_search(struct aga_graph *g, struct aga_node *start,
+ aga_visit_fn fn, void *opaque)
+{
+ if (aga_start(g))
+ return -1;
+
+ dfs(g, start, fn, opaque);
+
+ aga_finish(g);
+
+ return 0;
+}
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
new file mode 100644
index 0000000..cfa9791
--- /dev/null
+++ b/ccan/aga/aga.h
@@ -0,0 +1,41 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_AGA_H
+#define CCAN_AGA_H
+#include "config.h"
+#include <string.h>
+
+/*
+ *
+ */
+
+struct aga_node {
+ int sequence;
+};
+
+struct aga_edge {
+ struct aga_node *to;
+};
+
+struct aga_graph;
+
+typedef void *(*aga_edge_fn)(struct aga_graph *, struct aga_node *,
+ struct aga_edge *, void *);
+
+struct aga_graph {
+ int sequence;
+ aga_edge_fn edge_fn;
+};
+
+void aga_init(struct aga_graph *g, aga_edge_fn edge_fn);
+
+static inline void aga_node_init(struct aga_node *node)
+{
+ memset(node, 0, sizeof(*node));
+}
+
+typedef int(*aga_visit_fn)(struct aga_graph *, struct aga_node *, void *);
+
+int aga_depth_first_search(struct aga_graph *g, struct aga_node *start,
+ aga_visit_fn fn, void *opaque);
+
+#endif /* CCAN_AGA_H */
diff --git a/ccan/aga/test/helper.h b/ccan/aga/test/helper.h
new file mode 100644
index 0000000..e159472
--- /dev/null
+++ b/ccan/aga/test/helper.h
@@ -0,0 +1,19 @@
+#define MAX_TRACE 128
+
+struct tracebuf {
+ int n;
+ int l[MAX_TRACE];
+};
+
+static void add_trace(struct tracebuf *tb, int val)
+{
+ assert(tb->n < MAX_TRACE);
+ tb->l[tb->n++] = val;
+}
+
+#define check_trace(tb, ...) \
+ do { \
+ int cmp[] = { __VA_ARGS__ }; \
+ ok1((ARRAY_SIZE(cmp) == (tb)->n) \
+ && (memcmp(cmp, (tb)->l, sizeof(cmp)) == 0)); \
+ } while (0)
diff --git a/ccan/aga/test/run-chain.c b/ccan/aga/test/run-chain.c
new file mode 100644
index 0000000..55e6e16
--- /dev/null
+++ b/ccan/aga/test/run-chain.c
@@ -0,0 +1,98 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+/* Include the C files directly. */
+#include <ccan/aga/aga.c>
+#include <ccan/tap/tap.h>
+
+#include <ccan/array_size/array_size.h>
+
+#include "helper.h"
+
+#define CHAIN_LENGTH 8
+
+struct aga_node chain[CHAIN_LENGTH];
+struct aga_graph chain_graph;
+
+static void *chain_edge_fn(struct aga_graph *g, struct aga_node *node,
+ struct aga_edge *edge, void *p)
+{
+ int n = node - chain;
+ ptrdiff_t prev = p ? (ptrdiff_t) p : 0;
+ ptrdiff_t next;
+
+ switch (prev) {
+ case 0:
+ next = (n > 0) ? -1 : 1;
+ break;
+
+ case -1:
+ next = (n < (CHAIN_LENGTH - 1)) ? 1 : 0;
+ break;
+
+ case 1:
+ next = 0;
+ break;
+ }
+
+ if (!next)
+ return NULL;
+
+ edge->to = &chain[n + next];
+ return (void *)next;
+}
+
+static void setup(void)
+{
+ int i;
+
+ for (i = 0; i < CHAIN_LENGTH; i++)
+ aga_node_init(&chain[i]);
+
+ aga_init(&chain_graph, chain_edge_fn);
+}
+
+static int visit_fn(struct aga_graph *g, struct aga_node *node, void *opaque)
+{
+ struct tracebuf *tb = (struct tracebuf *)opaque;
+ int index = node - chain;
+
+ diag("Visited %d\n", index);
+
+ add_trace(tb, index);
+
+ return 0;
+}
+
+int main(void)
+{
+ struct tracebuf tb;
+
+ setup();
+
+ /* This is how many tests you plan to run */
+ plan_tests(3);
+
+ /* Depth-first traverse forwards */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&chain_graph, &chain[0], visit_fn, &tb);
+ check_trace(&tb, 0, 1, 2, 3, 4, 5, 6, 7);
+
+ /* Depth-first traverse backwards */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&chain_graph, &chain[CHAIN_LENGTH - 1],
+ visit_fn, &tb);
+ check_trace(&tb, 7, 6, 5, 4, 3, 2, 1, 0);
+
+ /* Depth-first traverse outwards */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&chain_graph, &chain[CHAIN_LENGTH/2],
+ visit_fn, &tb);
+ check_trace(&tb, 4, 3, 2, 1, 0, 5, 6, 7);
+
+ /* This exits depending on whether all tests passed */
+ return exit_status();
+}
diff --git a/ccan/aga/test/run-grid.c b/ccan/aga/test/run-grid.c
new file mode 100644
index 0000000..482b8dd
--- /dev/null
+++ b/ccan/aga/test/run-grid.c
@@ -0,0 +1,222 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+/* Include the C files directly. */
+#include <ccan/aga/aga.c>
+#include <ccan/tap/tap.h>
+
+#include <ccan/array_size/array_size.h>
+#include <ccan/container_of/container_of.h>
+
+#include "helper.h"
+
+#define GRID_X 3
+#define GRID_Y 3
+#define GRID_SIZE (GRID_X * GRID_Y)
+
+struct grid_node {
+ struct aga_node a;
+ struct aga_node b;
+};
+
+struct grid_node grid[GRID_SIZE];
+struct aga_graph grid_graph_a;
+struct aga_graph grid_graph_b;
+
+static void *grid_edge_fn_a(struct aga_graph *g, struct aga_node *node,
+ struct aga_edge *edge, void *p)
+{
+ struct grid_node *gn = container_of(node, struct grid_node, a);
+ int n = gn - grid;
+ int x = n % GRID_X;
+ int y = n / GRID_X;
+ int index = p ? (ptrdiff_t) p : 0;
+ bool done = false;
+
+ do {
+ switch (index) {
+ case 0:
+ if (x < (GRID_X - 1)) {
+ edge->to = &grid[y * GRID_Y + x + 1].a;
+ done = true;
+ }
+ break;
+
+ case 1:
+ if (y < (GRID_Y - 1)) {
+ edge->to = &grid[(y + 1) * GRID_Y + x].a;
+ done = true;
+ }
+ break;
+
+ default:
+ assert(index == 2);
+ return NULL;
+ };
+
+ index++;
+ } while (!done);
+
+ return (void *)((ptrdiff_t)index);
+}
+
+static void *grid_edge_fn_b(struct aga_graph *g, struct aga_node *node,
+ struct aga_edge *edge, void *p)
+{
+ struct grid_node *gn = container_of(node, struct grid_node, b);
+ int n = gn - grid;
+ int x = n % GRID_X;
+ int y = n / GRID_X;
+ int index = p ? (ptrdiff_t) p : 0;
+ bool done = false;
+
+ do {
+ switch (index) {
+ case 0:
+ if (x < (GRID_X - 1)) {
+ edge->to = &grid[y * GRID_Y + x + 1].b;
+ done = true;
+ }
+ break;
+
+ case 1:
+ if (y < (GRID_Y - 1)) {
+ edge->to = &grid[(y + 1) * GRID_Y + x].b;
+ done = true;
+ }
+ break;
+
+ case 2:
+ if (x > 0) {
+ edge->to = &grid[y * GRID_Y + x - 1].b;
+ done = true;
+ }
+ break;
+
+ case 3:
+ if (y > 0) {
+ edge->to = &grid[(y - 1) * GRID_Y + x].b;
+ done = true;
+ }
+ break;
+
+ default:
+ assert(index == 4);
+ return NULL;
+ };
+
+ index++;
+ } while (!done);
+
+ return (void *)((ptrdiff_t)index);
+}
+
+static void setup(void)
+{
+ int i;
+
+ for (i = 0; i < (GRID_SIZE); i++) {
+ aga_node_init(&grid[i].a);
+ aga_node_init(&grid[i].b);
+ }
+
+ aga_init(&grid_graph_a, grid_edge_fn_a);
+ aga_init(&grid_graph_b, grid_edge_fn_b);
+}
+
+static int visit_fn_a(struct aga_graph *g, struct aga_node *node, void *opaque)
+{
+ struct grid_node *gn = container_of(node, struct grid_node, a);
+ int n = gn - grid;
+ int x = n % GRID_X;
+ int y = n / GRID_X;
+ struct tracebuf *tb = (struct tracebuf *)opaque;
+
+ diag("Visited (%d, %d)\n", x, y);
+
+ add_trace(tb, n);
+
+ return 0;
+}
+
+static int visit_fn_b(struct aga_graph *g, struct aga_node *node, void *opaque)
+{
+ struct grid_node *gn = container_of(node, struct grid_node, b);
+ int n = gn - grid;
+ int x = n % GRID_X;
+ int y = n / GRID_X;
+ struct tracebuf *tb = (struct tracebuf *)opaque;
+
+ diag("Visited (%d, %d)\n", x, y);
+
+ add_trace(tb, n);
+
+ return 0;
+}
+
+int main(void)
+{
+ struct tracebuf tb;
+
+ setup();
+
+ /* This is how many tests you plan to run */
+ plan_tests(10);
+
+ /* (A) Depth-first traverse from top-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_a, &grid[0].a, visit_fn_a, &tb);
+ check_trace(&tb, 0, 1, 2, 5, 8, 4, 7, 3, 6);
+
+ /* (A) Depth-first traverse from top-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_a, &grid[2].a, visit_fn_a, &tb);
+ check_trace(&tb, 2, 5, 8);
+
+ /* (A) Depth-first traverse from bottom-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_a, &grid[6].a, visit_fn_a, &tb);
+ check_trace(&tb, 6, 7, 8);
+
+ /* (A) Depth-first traverse from bottom-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_a, &grid[8].a, visit_fn_a, &tb);
+ check_trace(&tb, 8);
+
+ /* (A) Depth-first traverse from centre */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_a, &grid[4].a, visit_fn_a, &tb);
+ check_trace(&tb, 4, 5, 8, 7);
+
+
+ /* (B) Depth-first traverse from top-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_b, &grid[0].b, visit_fn_b, &tb);
+ check_trace(&tb, 0, 1, 2, 5, 8, 7, 6, 3, 4);
+
+ /* (B) Depth-first traverse from top-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_b, &grid[2].b, visit_fn_b, &tb);
+ check_trace(&tb, 2, 5, 8, 7, 6, 3, 4, 1, 0);
+
+ /* (B) Depth-first traverse from bottom-left */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_b, &grid[6].b, visit_fn_b, &tb);
+ check_trace(&tb, 6, 7, 8, 5, 4, 3, 0, 1, 2);
+
+ /* (B) Depth-first traverse from bottom-right */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_b, &grid[8].b, visit_fn_b, &tb);
+ check_trace(&tb, 8, 7, 6, 3, 4, 5, 2, 1, 0);
+
+ /* (B) Depth-first traverse from centre */
+ memset(&tb, 0, sizeof(tb));
+ aga_depth_first_search(&grid_graph_b, &grid[4].b, visit_fn_b, &tb);
+ check_trace(&tb, 4, 5, 8, 7, 6, 3, 0, 1, 2);
+
+ /* This exits depending on whether all tests passed */
+ return exit_status();
+}
--
1.9.3
More information about the ccan
mailing list