lib: add DFS + DOT dumping to graph datastructure

* Add general-purpose DFS traversal code
* Add ability to dump any graph to DOT language
* Add tests for graph datastructure

Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>

3 files changed, 126 insertions, 1 deletions

diff --git a/lib/graph.c b/lib/graph.c
index a9cc43f7c..a9e35b46f 100644
--- a/lib/graph.c
+++ b/lib/graph.c
@@ -23,6 +23,7 @@
 #include <zebra.h>
 #include "graph.h"
 #include "memory.h"
+#include "buffer.h"
 
 DEFINE_MTYPE_STATIC(LIB, GRAPH, "Graph")
 DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node")
@@ -157,3 +158,73 @@ bool graph_has_edge(struct graph_node *from, struct graph_node *to)
 
 	return false;
 }
+
+static void _graph_dfs(struct graph *graph, struct graph_node *start,
+		       vector visited,
+		       void (*dfs_cb)(struct graph_node *, void *), void *arg)
+{
+	/* check that we have not visited this node */
+	for (unsigned int i = 0; i < vector_active(visited); i++) {
+		if (start == vector_slot(visited, i))
+			return;
+	}
+
+	/* put this node in visited stack */
+	vector_ensure(visited, vector_active(visited));
+	vector_set_index(visited, vector_active(visited), start);
+
+	/* callback */
+	dfs_cb(start, arg);
+
+	/* recurse into children */
+	for (unsigned int i = vector_active(start->to); i--; /**/) {
+		struct graph_node *c = vector_slot(start->to, i);
+
+		_graph_dfs(graph, c, visited, dfs_cb, arg);
+	}
+}
+
+void graph_dfs(struct graph *graph, struct graph_node *start,
+	       void (*dfs_cb)(struct graph_node *, void *), void *arg)
+{
+	vector visited = vector_init(VECTOR_MIN_SIZE);
+
+	_graph_dfs(graph, start, visited, dfs_cb, arg);
+	vector_free(visited);
+}
+
+#ifndef BUILDING_CLIPPY
+
+void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf)
+{
+	char nbuf[64];
+
+	for (unsigned int i = 0; i < vector_active(gn->to); i++) {
+		struct graph_node *adj = vector_slot(gn->to, i);
+
+		snprintf(nbuf, sizeof(nbuf), "    n%p -> n%p;\n", gn, adj);
+		buffer_putstr(buf, nbuf);
+	}
+}
+
+char *graph_dump_dot(struct graph *graph, struct graph_node *start,
+		     void (*pcb)(struct graph_node *, struct buffer *))
+{
+	struct buffer *buf = buffer_new(0);
+	char *ret;
+
+	pcb = (pcb) ? pcb : graph_dump_dot_default_print_cb;
+	buffer_putstr(buf, "digraph {\n");
+
+	graph_dfs(graph, start, (void (*)(struct graph_node *, void *))pcb,
+		  buf);
+
+	buffer_putstr(buf, "}\n");
+
+	ret = buffer_getstr(buf);
+	buffer_free(buf);
+
+	return ret;
+}
+
+#endif /* BUILDING_CLIPPY */
diff --git a/lib/graph.h b/lib/graph.h
index d6dfef5a6..87262a07b 100644
--- a/lib/graph.h
+++ b/lib/graph.h
@@ -26,6 +26,7 @@
 
 #include <stdbool.h>
 #include "vector.h"
+#include "buffer.h"
 
 struct graph {
 	vector nodes;
@@ -111,4 +112,56 @@ struct graph_node *graph_find_node(struct graph *graph, void *data);
  */
 bool graph_has_edge(struct graph_node *from, struct graph_node *to);
 
+/*
+ * Depth-first search.
+ *
+ * Performs a depth-first traversal of the given graph, visiting each node
+ * exactly once and calling the user-provided callback for each visit.
+ *
+ * @param graph the graph to operate on
+ * @param start the node to take as the root
+ * @param dfs_cb callback called for each node visited in the traversal
+ * @param arg argument to provide to dfs_cb
+ */
+void graph_dfs(struct graph *graph, struct graph_node *start,
+	       void (*dfs_cb)(struct graph_node *, void *), void *arg);
+
+#ifndef BUILDING_CLIPPY
+/*
+ * Clippy relies on a small subset of sources in lib/, but it cannot link
+ * libfrr since clippy itself is required to build libfrr. Instead it directly
+ * includes the sources it needs. One of these is the command graph
+ * implementation, which wraps this graph implementation. Since we need to use
+ * the buffer.[ch] sources here, which indirectly rely on most of libfrr, we
+ * have to ignore them when compiling clippy to avoid build dependency issues.
+ *
+ * TODO: Fix clippy build.
+ */
+
+/*
+ * Default node printer for use with graph_dump_dot.
+ *
+ * @param gn the node to print
+ * @param buf the buffer to print into
+ */
+void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf);
+
+/*
+ * Prints a graph in the DOT language.
+ *
+ * The generated output is produced from a depth-first traversal of the graph.
+ *
+ * @param graph the graph to print
+ * @param start the node to take as the root
+ * @param pcb callback called for each node in the traversal that should
+ *        print the node in the DOT language. Passing NULL for this argument
+ *        will use the default printer. See graph_dump_dot_default_print_cb for
+ *        an example.
+ * @return representation of graph in DOT language, allocated with MTYPE_TMP.
+ *         Caller is responsible for freeing this string.
+ */
+char *graph_dump_dot(struct graph *graph, struct graph_node *start,
+		     void (*pcb)(struct graph_node *, struct buffer *buf));
+
+#endif /* BUILDING_CLIPPY */
 #endif /* _ZEBRA_COMMAND_GRAPH_H */
diff --git a/lib/subdir.am b/lib/subdir.am
index 3b469d452..c5719786d 100644
--- a/lib/subdir.am
+++ b/lib/subdir.am
@@ -171,6 +171,7 @@ pkginclude_HEADERS += \
 	lib/pbr.h \
 	# end
 
+
 nodist_pkginclude_HEADERS += \
 	lib/route_types.h \
 	lib/version.h \
@@ -232,7 +233,7 @@ lib_grammar_sandbox_SOURCES = \
 lib_grammar_sandbox_LDADD = \
 	lib/libfrr.la
 
-lib_clippy_CPPFLAGS = $(AM_CPPFLAGS) -D_GNU_SOURCE
+lib_clippy_CPPFLAGS = $(AM_CPPFLAGS) -D_GNU_SOURCE -DBUILDING_CLIPPY
 lib_clippy_CFLAGS = $(PYTHON_CFLAGS)
 lib_clippy_LDADD = $(PYTHON_LIBS)
 lib_clippy_SOURCES = \