lib/graph.h

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