lib/graph.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Graph data structure.
   4  *
   5  * --
   6  * Copyright (C) 2016 Cumulus Networks, Inc.
   7  */
   8
   9 #ifndef _ZEBRA_COMMAND_GRAPH_H
  10 #define _ZEBRA_COMMAND_GRAPH_H
  11
  12 #include <stdbool.h>
  13 #include "vector.h"
  14 #include "buffer.h"
  15
  16 #ifdef __cplusplus
  17 extern "C" {
  18 #endif
  19
  20 struct graph {
  21         vector nodes;
  22 };
  23
  24 struct graph_node {
  25         vector from; // nodes which have edges to this node
  26         vector to;   // nodes which this node has edges to
  27
  28         void *data;              // node data
  29         void (*del)(void *data); // deletion callback
  30 };
  31
  32 struct graph *graph_new(void);
  33
  34 /**
  35  * Creates a new node.
  36  *
  37  * @struct graph the graph this node exists in
  38  * @param[in] data this node's data
  39  * @param[in] del data deletion callback
  40  * @return the new node
  41  */
  42 struct graph_node *graph_new_node(struct graph *graph, void *data,
  43                                   void (*del)(void *));
  44
  45 /**
  46  * Deletes a node.
  47  *
  48  * Before deletion, this function removes all edges to and from this node from
  49  * any neighbor nodes.
  50  *
  51  * If *data and *del are non-null, the following call is made:
  52  *   (*node->del) (node->data);
  53  *
  54  * @param[in] graph the graph this node belongs to
  55  * @param[out] node pointer to node to delete
  56  */
  57 void graph_delete_node(struct graph *graph, struct graph_node *node);
  58
  59 /**
  60  * Makes a directed edge between two nodes.
  61  *
  62  * @param[in] from
  63  * @param[in] to
  64  * @return to
  65  */
  66 struct graph_node *graph_add_edge(struct graph_node *from,
  67                                   struct graph_node *to);
  68
  69 /**
  70  * Removes a directed edge between two nodes.
  71  *
  72  * @param[in] from
  73  * @param[in] to
  74  */
  75 void graph_remove_edge(struct graph_node *from, struct graph_node *to);
  76
  77 /**
  78  * Deletes a graph.
  79  * Calls graph_delete_node on each node before freeing the graph struct itself.
  80  *
  81  * @param graph the graph to delete
  82  */
  83 void graph_delete_graph(struct graph *graph);
  84
  85 /*
  86  * Finds a node in the graph.
  87  *
  88  * @param[in] graph the graph to search in
  89  * @param[in] data the data to key off
  90  * @return the first graph node whose data pointer matches `data`
  91  */
  92 struct graph_node *graph_find_node(struct graph *graph, void *data);
  93
  94
  95 /*
  96  * Determines whether two nodes have a directed edge between them.
  97  *
  98  * @param from
  99  * @param to
 100  * @return whether there is a directed edge from `from` to `to`.
 101  */
 102 bool graph_has_edge(struct graph_node *from, struct graph_node *to);
 103
 104 /*
 105  * Depth-first search.
 106  *
 107  * Performs a depth-first traversal of the given graph, visiting each node
 108  * exactly once and calling the user-provided callback for each visit.
 109  *
 110  * @param graph the graph to operate on
 111  * @param start the node to take as the root
 112  * @param dfs_cb callback called for each node visited in the traversal
 113  * @param arg argument to provide to dfs_cb
 114  */
 115 void graph_dfs(struct graph *graph, struct graph_node *start,
 116                void (*dfs_cb)(struct graph_node *, void *), void *arg);
 117
 118 #ifndef BUILDING_CLIPPY
 119 /*
 120  * Clippy relies on a small subset of sources in lib/, but it cannot link
 121  * libfrr since clippy itself is required to build libfrr. Instead it directly
 122  * includes the sources it needs. One of these is the command graph
 123  * implementation, which wraps this graph implementation. Since we need to use
 124  * the buffer.[ch] sources here, which indirectly rely on most of libfrr, we
 125  * have to ignore them when compiling clippy to avoid build dependency issues.
 126  *
 127  * TODO: Fix clippy build.
 128  */
 129
 130 /*
 131  * Default node printer for use with graph_dump_dot.
 132  *
 133  * @param gn the node to print
 134  * @param buf the buffer to print into
 135  */
 136 void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf);
 137
 138 /*
 139  * Prints a graph in the DOT language.
 140  *
 141  * The generated output is produced from a depth-first traversal of the graph.
 142  *
 143  * @param graph the graph to print
 144  * @param start the node to take as the root
 145  * @param pcb callback called for each node in the traversal that should
 146  *        print the node in the DOT language. Passing NULL for this argument
 147  *        will use the default printer. See graph_dump_dot_default_print_cb for
 148  *        an example.
 149  * @return representation of graph in DOT language, allocated with MTYPE_TMP.
 150  *         Caller is responsible for freeing this string.
 151  */
 152 char *graph_dump_dot(struct graph *graph, struct graph_node *start,
 153                      void (*pcb)(struct graph_node *, struct buffer *buf));
 154
 155 #endif /* BUILDING_CLIPPY */
 156
 157 #ifdef __cplusplus
 158 }
 159 #endif
 160
 161 #endif /* _ZEBRA_COMMAND_GRAPH_H */