From 58f8a9ecde2cd513e652fe59f78dcde6a13ee8f7 Mon Sep 17 00:00:00 2001 From: Quentin Young Date: Thu, 19 Apr 2018 11:35:16 -0400 Subject: [PATCH] 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 --- lib/graph.c | 71 ++++++++++++++++++++++++++++++++++ lib/graph.h | 53 +++++++++++++++++++++++++ lib/subdir.am | 3 +- tests/.gitignore | 2 + tests/Makefile.am | 4 ++ tests/lib/test_graph.c | 77 +++++++++++++++++++++++++++++++++++++ tests/lib/test_graph.py | 4 ++ tests/lib/test_graph.refout | 64 ++++++++++++++++++++++++++++++ 8 files changed, 277 insertions(+), 1 deletion(-) create mode 100644 tests/lib/test_graph.c create mode 100644 tests/lib/test_graph.py create mode 100644 tests/lib/test_graph.refout diff --git a/lib/graph.c b/lib/graph.c index a9cc43f7c1..a9e35b46ff 100644 --- a/lib/graph.c +++ b/lib/graph.c @@ -23,6 +23,7 @@ #include #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 d6dfef5a63..87262a07b8 100644 --- a/lib/graph.h +++ b/lib/graph.h @@ -26,6 +26,7 @@ #include #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 0319f7764e..d2d18df074 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -170,6 +170,7 @@ pkginclude_HEADERS += \ lib/pbr.h \ # end + nodist_pkginclude_HEADERS += \ lib/route_types.h \ lib/version.h \ @@ -231,7 +232,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 = \ diff --git a/tests/.gitignore b/tests/.gitignore index c2fe9c8890..1708a4b7b0 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -50,5 +50,7 @@ __pycache__ /lib/test_timer_performance /lib/test_ttable /lib/test_zmq +/lib/test_zlog +/lib/test_graph /ospf6d/test_lsdb /ospf6d/test_lsdb_clippy.c diff --git a/tests/Makefile.am b/tests/Makefile.am index 0c9a5684da..703c1d05fc 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -74,6 +74,7 @@ check_PROGRAMS = \ lib/test_timer_performance \ lib/test_ttable \ lib/test_zlog \ + lib/test_graph \ lib/cli/test_cli \ lib/cli/test_commands \ $(TESTS_BGPD) \ @@ -129,6 +130,7 @@ lib_test_timer_performance_SOURCES = lib/test_timer_performance.c \ helpers/c/prng.c lib_test_ttable_SOURCES = lib/test_ttable.c lib_test_zlog_SOURCES = lib/test_zlog.c +lib_test_graph_SOURCES = lib/test_graph.c lib_test_zmq_SOURCES = lib/test_zmq.c lib_test_zmq_CFLAGS = $(AM_CFLAGS) $(ZEROMQ_CFLAGS) lib_cli_test_cli_SOURCES = lib/cli/test_cli.c lib/cli/common_cli.c @@ -170,6 +172,7 @@ lib_test_timer_correctness_LDADD = $(ALL_TESTS_LDADD) lib_test_timer_performance_LDADD = $(ALL_TESTS_LDADD) lib_test_ttable_LDADD = $(ALL_TESTS_LDADD) lib_test_zlog_LDADD = $(ALL_TESTS_LDADD) +lib_test_graph_LDADD = $(ALL_TESTS_LDADD) lib_test_zmq_LDADD = ../lib/libfrrzmq.la $(ALL_TESTS_LDADD) $(ZEROMQ_LIBS) lib_cli_test_cli_LDADD = $(ALL_TESTS_LDADD) lib_cli_test_commands_LDADD = $(ALL_TESTS_LDADD) @@ -211,6 +214,7 @@ EXTRA_DIST = \ lib/test_ttable.py \ lib/test_ttable.refout \ lib/test_zlog.py \ + lib/test_graph.py \ ospf6d/test_lsdb.py \ ospf6d/test_lsdb.in \ ospf6d/test_lsdb.refout \ diff --git a/tests/lib/test_graph.c b/tests/lib/test_graph.c new file mode 100644 index 0000000000..f21f8b793c --- /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 +#include +#include +#include + +#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 0000000000..697e56c149 --- /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 0000000000..955f55293a --- /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; +} -- 2.39.5