]> git.proxmox.com Git - mirror_frr.git/blob - lib/graph.c
Merge pull request #13278 from FRRouting/mergify/bp/stable/8.5/pr-13269
[mirror_frr.git] / 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 */