lib/graph.c

   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 #include <zebra.h>
   9 #include "graph.h"
  10 #include "memory.h"
  11 #include "buffer.h"
  12
  13 DEFINE_MTYPE_STATIC(LIB, GRAPH, "Graph");
  14 DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node");
  15 struct graph *graph_new(void)
  16 {
  17         struct graph *graph = XCALLOC(MTYPE_GRAPH, sizeof(struct graph));
  18         graph->nodes = vector_init(VECTOR_MIN_SIZE);
  19
  20         return graph;
  21 }
  22
  23 void graph_delete_graph(struct graph *graph)
  24 {
  25         for (unsigned int i = vector_active(graph->nodes); i--; /**/)
  26                 graph_delete_node(graph, vector_slot(graph->nodes, i));
  27
  28         vector_free(graph->nodes);
  29         XFREE(MTYPE_GRAPH, graph);
  30 }
  31
  32 struct graph_node *graph_new_node(struct graph *graph, void *data,
  33                                   void (*del)(void *))
  34 {
  35         struct graph_node *node =
  36                 XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node));
  37
  38         node->from = vector_init(VECTOR_MIN_SIZE);
  39         node->to = vector_init(VECTOR_MIN_SIZE);
  40         node->data = data;
  41         node->del = del;
  42
  43         vector_set(graph->nodes, node);
  44
  45         return node;
  46 }
  47
  48 static void graph_vector_remove(vector v, unsigned int ix)
  49 {
  50         if (ix >= v->active)
  51                 return;
  52
  53         /* v->active is guaranteed >= 1 because ix can't be lower than 0
  54          * and v->active is > ix. */
  55         v->active--;
  56         /* if ix == v->active--, we set the item to itself, then to NULL...
  57          * still correct, no check necessary. */
  58         v->index[ix] = v->index[v->active];
  59         v->index[v->active] = NULL;
  60 }
  61
  62 void graph_delete_node(struct graph *graph, struct graph_node *node)
  63 {
  64         if (!node)
  65                 return;
  66
  67         // an adjacent node
  68         struct graph_node *adj;
  69
  70         // remove all edges from other nodes to us
  71         for (unsigned int i = vector_active(node->from); i--; /**/) {
  72                 adj = vector_slot(node->from, i);
  73                 graph_remove_edge(adj, node);
  74         }
  75
  76         // remove all edges from us to other nodes
  77         for (unsigned int i = vector_active(node->to); i--; /**/) {
  78                 adj = vector_slot(node->to, i);
  79                 graph_remove_edge(node, adj);
  80         }
  81
  82         // if there is a deletion callback, call it
  83         if (node->del && node->data)
  84                 (*node->del)(node->data);
  85
  86         // free adjacency lists
  87         vector_free(node->to);
  88         vector_free(node->from);
  89
  90         // remove node from graph->nodes
  91         for (unsigned int i = vector_active(graph->nodes); i--; /**/)
  92                 if (vector_slot(graph->nodes, i) == node) {
  93                         graph_vector_remove(graph->nodes, i);
  94                         break;
  95                 }
  96
  97         // free the node itself
  98         XFREE(MTYPE_GRAPH_NODE, node);
  99 }
 100
 101 struct graph_node *graph_add_edge(struct graph_node *from,
 102                                   struct graph_node *to)
 103 {
 104         vector_set(from->to, to);
 105         vector_set(to->from, from);
 106         return to;
 107 }
 108
 109 void graph_remove_edge(struct graph_node *from, struct graph_node *to)
 110 {
 111         // remove from from to->from
 112         for (unsigned int i = vector_active(to->from); i--; /**/)
 113                 if (vector_slot(to->from, i) == from) {
 114                         graph_vector_remove(to->from, i);
 115                         break;
 116                 }
 117         // remove to from from->to
 118         for (unsigned int i = vector_active(from->to); i--; /**/)
 119                 if (vector_slot(from->to, i) == to) {
 120                         graph_vector_remove(from->to, i);
 121                         break;
 122                 }
 123 }
 124
 125 struct graph_node *graph_find_node(struct graph *graph, void *data)
 126 {
 127         struct graph_node *g;
 128
 129         for (unsigned int i = vector_active(graph->nodes); i--; /**/) {
 130                 g = vector_slot(graph->nodes, i);
 131                 if (g->data == data)
 132                         return g;
 133         }
 134
 135         return NULL;
 136 }
 137
 138 bool graph_has_edge(struct graph_node *from, struct graph_node *to)
 139 {
 140         for (unsigned int i = vector_active(from->to); i--; /**/)
 141                 if (vector_slot(from->to, i) == to)
 142                         return true;
 143
 144         return false;
 145 }
 146
 147 static void _graph_dfs(struct graph *graph, struct graph_node *start,
 148                        vector visited,
 149                        void (*dfs_cb)(struct graph_node *, void *), void *arg)
 150 {
 151         /* check that we have not visited this node */
 152         for (unsigned int i = 0; i < vector_active(visited); i++) {
 153                 if (start == vector_slot(visited, i))
 154                         return;
 155         }
 156
 157         /* put this node in visited stack */
 158         vector_ensure(visited, vector_active(visited));
 159         vector_set_index(visited, vector_active(visited), start);
 160
 161         /* callback */
 162         dfs_cb(start, arg);
 163
 164         /* recurse into children */
 165         for (unsigned int i = vector_active(start->to); i--; /**/) {
 166                 struct graph_node *c = vector_slot(start->to, i);
 167
 168                 _graph_dfs(graph, c, visited, dfs_cb, arg);
 169         }
 170 }
 171
 172 void graph_dfs(struct graph *graph, struct graph_node *start,
 173                void (*dfs_cb)(struct graph_node *, void *), void *arg)
 174 {
 175         vector visited = vector_init(VECTOR_MIN_SIZE);
 176
 177         _graph_dfs(graph, start, visited, dfs_cb, arg);
 178         vector_free(visited);
 179 }
 180
 181 #ifndef BUILDING_CLIPPY
 182
 183 void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf)
 184 {
 185         char nbuf[64];
 186
 187         for (unsigned int i = 0; i < vector_active(gn->to); i++) {
 188                 struct graph_node *adj = vector_slot(gn->to, i);
 189
 190                 snprintf(nbuf, sizeof(nbuf), "    n%p -> n%p;\n", gn, adj);
 191                 buffer_putstr(buf, nbuf);
 192         }
 193 }
 194
 195 char *graph_dump_dot(struct graph *graph, struct graph_node *start,
 196                      void (*pcb)(struct graph_node *, struct buffer *))
 197 {
 198         struct buffer *buf = buffer_new(0);
 199         char *ret;
 200
 201         pcb = (pcb) ? pcb : graph_dump_dot_default_print_cb;
 202         buffer_putstr(buf, "digraph {\n");
 203
 204         graph_dfs(graph, start, (void (*)(struct graph_node *, void *))pcb,
 205                   buf);
 206
 207         buffer_putstr(buf, "}\n");
 208
 209         ret = buffer_getstr(buf);
 210         buffer_free(buf);
 211
 212         return ret;
 213 }
 214
 215 #endif /* BUILDING_CLIPPY */