]>
Commit | Line | Data |
---|---|---|
16d7c050 QY |
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 | * | |
896014f4 DL |
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 | |
16d7c050 QY |
22 | */ |
23 | #include <zebra.h> | |
1eb5e8dc | 24 | #include "graph.h" |
16d7c050 | 25 | #include "memory.h" |
58f8a9ec | 26 | #include "buffer.h" |
16d7c050 | 27 | |
d62a17ae | 28 | DEFINE_MTYPE_STATIC(LIB, GRAPH, "Graph") |
460a7689 | 29 | DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node") |
d62a17ae | 30 | struct graph *graph_new() |
1eb5e8dc | 31 | { |
d62a17ae | 32 | struct graph *graph = XCALLOC(MTYPE_GRAPH, sizeof(struct graph)); |
33 | graph->nodes = vector_init(VECTOR_MIN_SIZE); | |
1eb5e8dc | 34 | |
d62a17ae | 35 | return graph; |
1eb5e8dc | 36 | } |
16d7c050 | 37 | |
9428e089 QY |
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 | ||
d62a17ae | 47 | struct graph_node *graph_new_node(struct graph *graph, void *data, |
48 | void (*del)(void *)) | |
16d7c050 | 49 | { |
d62a17ae | 50 | struct graph_node *node = |
51 | XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node)); | |
16d7c050 | 52 | |
d62a17ae | 53 | node->from = vector_init(VECTOR_MIN_SIZE); |
54 | node->to = vector_init(VECTOR_MIN_SIZE); | |
55 | node->data = data; | |
56 | node->del = del; | |
16d7c050 | 57 | |
d62a17ae | 58 | vector_set(graph->nodes, node); |
16d7c050 | 59 | |
d62a17ae | 60 | return node; |
16d7c050 QY |
61 | } |
62 | ||
62bece44 | 63 | static void graph_vector_remove(vector v, unsigned int ix) |
ba06a3a0 | 64 | { |
d62a17ae | 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 neccessary. */ | |
73 | v->index[ix] = v->index[v->active]; | |
74 | v->index[v->active] = NULL; | |
ba06a3a0 QY |
75 | } |
76 | ||
d62a17ae | 77 | void graph_delete_node(struct graph *graph, struct graph_node *node) |
16d7c050 | 78 | { |
d62a17ae | 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) { | |
62bece44 | 108 | graph_vector_remove(graph->nodes, i); |
d62a17ae | 109 | break; |
110 | } | |
111 | ||
112 | // free the node itself | |
113 | XFREE(MTYPE_GRAPH_NODE, node); | |
16d7c050 QY |
114 | } |
115 | ||
d62a17ae | 116 | struct graph_node *graph_add_edge(struct graph_node *from, |
117 | struct graph_node *to) | |
16d7c050 | 118 | { |
d62a17ae | 119 | vector_set(from->to, to); |
120 | vector_set(to->from, from); | |
121 | return to; | |
16d7c050 QY |
122 | } |
123 | ||
d62a17ae | 124 | void graph_remove_edge(struct graph_node *from, struct graph_node *to) |
ba06a3a0 | 125 | { |
d62a17ae | 126 | // remove from from to->from |
127 | for (unsigned int i = vector_active(to->from); i--; /**/) | |
128 | if (vector_slot(to->from, i) == from) { | |
62bece44 | 129 | graph_vector_remove(to->from, i); |
d62a17ae | 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) { | |
62bece44 | 135 | graph_vector_remove(from->to, i); |
d62a17ae | 136 | break; |
137 | } | |
ba06a3a0 QY |
138 | } |
139 | ||
9428e089 | 140 | struct graph_node *graph_find_node(struct graph *graph, void *data) |
16d7c050 | 141 | { |
9428e089 | 142 | struct graph_node *g; |
16d7c050 | 143 | |
9428e089 QY |
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; | |
16d7c050 | 160 | } |
58f8a9ec QY |
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 */ |