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