lib/graph.c

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