From 9428e08906c415d538dc22104a70889f3152a074 Mon Sep 17 00:00:00 2001 From: Quentin Young Date: Fri, 6 Apr 2018 17:58:00 -0400 Subject: lib: add graph_find_node Allows finding a graph node by its data pointer. Signed-off-by: Quentin Young --- lib/graph.c | 33 +++++++++++++++++++++++++++------ lib/graph.h | 20 ++++++++++++++++++++ 2 files changed, 47 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/graph.c b/lib/graph.c index 945a58e68..a9cc43f7c 100644 --- a/lib/graph.c +++ b/lib/graph.c @@ -34,6 +34,15 @@ struct graph *graph_new() return graph; } +void graph_delete_graph(struct graph *graph) +{ + for (unsigned int i = vector_active(graph->nodes); i--; /**/) + graph_delete_node(graph, vector_slot(graph->nodes, i)); + + vector_free(graph->nodes); + XFREE(MTYPE_GRAPH, graph); +} + struct graph_node *graph_new_node(struct graph *graph, void *data, void (*del)(void *)) { @@ -127,12 +136,24 @@ void graph_remove_edge(struct graph_node *from, struct graph_node *to) } } -void graph_delete_graph(struct graph *graph) +struct graph_node *graph_find_node(struct graph *graph, void *data) { - // delete each node in the graph - for (unsigned int i = vector_active(graph->nodes); i--; /**/) - graph_delete_node(graph, vector_slot(graph->nodes, i)); + struct graph_node *g; - vector_free(graph->nodes); - XFREE(MTYPE_GRAPH, graph); + for (unsigned int i = vector_active(graph->nodes); i--; /**/) { + g = vector_slot(graph->nodes, i); + if (g->data == data) + return g; + } + + return NULL; +} + +bool graph_has_edge(struct graph_node *from, struct graph_node *to) +{ + for (unsigned int i = vector_active(from->to); i--; /**/) + if (vector_slot(from->to, i) == to) + return true; + + return false; } diff --git a/lib/graph.h b/lib/graph.h index 10ee00fed..d6dfef5a6 100644 --- a/lib/graph.h +++ b/lib/graph.h @@ -24,6 +24,7 @@ #ifndef _ZEBRA_COMMAND_GRAPH_H #define _ZEBRA_COMMAND_GRAPH_H +#include #include "vector.h" struct graph { @@ -91,4 +92,23 @@ void graph_remove_edge(struct graph_node *from, struct graph_node *to); */ void graph_delete_graph(struct graph *graph); +/* + * Finds a node in the graph. + * + * @param[in] graph the graph to search in + * @param[in] data the data to key off + * @return the first graph node whose data pointer matches `data` + */ +struct graph_node *graph_find_node(struct graph *graph, void *data); + + +/* + * Determines whether two nodes have a directed edge between them. + * + * @param from + * @param to + * @return whether there is a directed edge from `from` to `to`. + */ +bool graph_has_edge(struct graph_node *from, struct graph_node *to); + #endif /* _ZEBRA_COMMAND_GRAPH_H */ -- cgit v1.2.3