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, 145 insertions, 0 deletions

diff --git a/tests/lib/test_graph.c b/tests/lib/test_graph.c
new file mode 100644
index 000000000..f21f8b793
--- /dev/null
+++ b/tests/lib/test_graph.c
@@ -0,0 +1,77 @@
+/*
+ * Test graph data structure.
+ * Copyright (C) 2018  Cumulus Networks, Inc.
+ *                     Quentin Young
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+#include <zebra.h>
+#include <graph.h>
+#include <memory.h>
+#include <buffer.h>
+
+#define NUMNODES 32
+
+static void graph_custom_print_cb(struct graph_node *gn, struct buffer *buf)
+{
+	char nbuf[64];
+	char *gname = gn->data;
+
+	for (unsigned int i = 0; i < vector_active(gn->to); i++) {
+		struct graph_node *adj = vector_slot(gn->to, i);
+		char *name = adj->data;
+
+		snprintf(nbuf, sizeof(nbuf), "    n%s -> n%s;\n", gname, name);
+		buffer_putstr(buf, nbuf);
+	}
+}
+
+int main(int argc, char **argv)
+{
+	struct graph *g = graph_new();
+	struct graph_node *gn[NUMNODES];
+	char names[NUMNODES][16];
+
+	/* create vertices */
+	for (unsigned int i = 0; i < NUMNODES; i++) {
+		snprintf(names[i], sizeof(names[i]), "%d", i);
+		gn[i] = graph_new_node(g, names[i], NULL);
+	}
+
+	/* create edges */
+	for (unsigned int i = 1; i < NUMNODES - 1; i++) {
+		graph_add_edge(gn[0], gn[i]);
+		graph_add_edge(gn[i], gn[i + 1]);
+	}
+	graph_add_edge(gn[0], gn[NUMNODES - 1]);
+	graph_add_edge(gn[NUMNODES - 1], gn[1]);
+
+	/* print DOT */
+	char *dumped = graph_dump_dot(g, gn[0], graph_custom_print_cb);
+
+	fprintf(stdout, "%s", dumped);
+	XFREE(MTYPE_TMP, dumped);
+
+	/* remove some edges */
+	for (unsigned int i = NUMNODES - 1; i > NUMNODES / 2; --i)
+		for (unsigned int j = 0; j < NUMNODES; j++)
+			graph_remove_edge(gn[i], gn[j]);
+
+	/* remove some nodes */
+	for (unsigned int i = 0; i < NUMNODES / 2; i++)
+		graph_delete_node(g, gn[i]);
+
+	graph_delete_graph(g);
+}
diff --git a/tests/lib/test_graph.py b/tests/lib/test_graph.py
new file mode 100644
index 000000000..697e56c14
--- /dev/null
+++ b/tests/lib/test_graph.py
@@ -0,0 +1,4 @@
+import frrtest
+
+class TestGraph(frrtest.TestRefOut):
+    program = './test_graph'
diff --git a/tests/lib/test_graph.refout b/tests/lib/test_graph.refout
new file mode 100644
index 000000000..955f55293
--- /dev/null
+++ b/tests/lib/test_graph.refout
@@ -0,0 +1,64 @@
+digraph {
+    n0 -> n1;
+    n0 -> n2;
+    n0 -> n3;
+    n0 -> n4;
+    n0 -> n5;
+    n0 -> n6;
+    n0 -> n7;
+    n0 -> n8;
+    n0 -> n9;
+    n0 -> n10;
+    n0 -> n11;
+    n0 -> n12;
+    n0 -> n13;
+    n0 -> n14;
+    n0 -> n15;
+    n0 -> n16;
+    n0 -> n17;
+    n0 -> n18;
+    n0 -> n19;
+    n0 -> n20;
+    n0 -> n21;
+    n0 -> n22;
+    n0 -> n23;
+    n0 -> n24;
+    n0 -> n25;
+    n0 -> n26;
+    n0 -> n27;
+    n0 -> n28;
+    n0 -> n29;
+    n0 -> n30;
+    n0 -> n31;
+    n31 -> n1;
+    n1 -> n2;
+    n2 -> n3;
+    n3 -> n4;
+    n4 -> n5;
+    n5 -> n6;
+    n6 -> n7;
+    n7 -> n8;
+    n8 -> n9;
+    n9 -> n10;
+    n10 -> n11;
+    n11 -> n12;
+    n12 -> n13;
+    n13 -> n14;
+    n14 -> n15;
+    n15 -> n16;
+    n16 -> n17;
+    n17 -> n18;
+    n18 -> n19;
+    n19 -> n20;
+    n20 -> n21;
+    n21 -> n22;
+    n22 -> n23;
+    n23 -> n24;
+    n24 -> n25;
+    n25 -> n26;
+    n26 -> n27;
+    n27 -> n28;
+    n28 -> n29;
+    n29 -> n30;
+    n30 -> n31;
+}