]>
Commit | Line | Data |
---|---|---|
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 */ |