1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
/*
* Graph data structure.
*
* --
* Copyright (C) 2016 Cumulus Networks, Inc.
*
* This file is part of GNU Zebra.
*
* GNU Zebra is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation; either version 2, or (at your option) any
* later version.
*
* GNU Zebra is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; see the file COPYING; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef _ZEBRA_COMMAND_GRAPH_H
#define _ZEBRA_COMMAND_GRAPH_H
#include <stdbool.h>
#include "vector.h"
#include "buffer.h"
#ifdef __cplusplus
extern "C" {
#endif
struct graph {
vector nodes;
};
struct graph_node {
vector from; // nodes which have edges to this node
vector to; // nodes which this node has edges to
void *data; // node data
void (*del)(void *data); // deletion callback
};
struct graph *graph_new(void);
/**
* Creates a new node.
*
* @struct graph the graph this node exists in
* @param[in] data this node's data
* @param[in] del data deletion callback
* @return the new node
*/
struct graph_node *graph_new_node(struct graph *graph, void *data,
void (*del)(void *));
/**
* Deletes a node.
*
* Before deletion, this function removes all edges to and from this node from
* any neighbor nodes.
*
* If *data and *del are non-null, the following call is made:
* (*node->del) (node->data);
*
* @param[in] graph the graph this node belongs to
* @param[out] node pointer to node to delete
*/
void graph_delete_node(struct graph *graph, struct graph_node *node);
/**
* Makes a directed edge between two nodes.
*
* @param[in] from
* @param[in] to
* @return to
*/
struct graph_node *graph_add_edge(struct graph_node *from,
struct graph_node *to);
/**
* Removes a directed edge between two nodes.
*
* @param[in] from
* @param[in] to
*/
void graph_remove_edge(struct graph_node *from, struct graph_node *to);
/**
* Deletes a graph.
* Calls graph_delete_node on each node before freeing the graph struct itself.
*
* @param graph the graph to delete
*/
void graph_delete_graph(struct graph *graph);
/*
* Finds a node in the graph.
*
* @param[in] graph the graph to search in
* @param[in] data the data to key off
* @return the first graph node whose data pointer matches `data`
*/
struct graph_node *graph_find_node(struct graph *graph, void *data);
/*
* Determines whether two nodes have a directed edge between them.
*
* @param from
* @param to
* @return whether there is a directed edge from `from` to `to`.
*/
bool graph_has_edge(struct graph_node *from, struct graph_node *to);
/*
* Depth-first search.
*
* Performs a depth-first traversal of the given graph, visiting each node
* exactly once and calling the user-provided callback for each visit.
*
* @param graph the graph to operate on
* @param start the node to take as the root
* @param dfs_cb callback called for each node visited in the traversal
* @param arg argument to provide to dfs_cb
*/
void graph_dfs(struct graph *graph, struct graph_node *start,
void (*dfs_cb)(struct graph_node *, void *), void *arg);
#ifndef BUILDING_CLIPPY
/*
* Clippy relies on a small subset of sources in lib/, but it cannot link
* libfrr since clippy itself is required to build libfrr. Instead it directly
* includes the sources it needs. One of these is the command graph
* implementation, which wraps this graph implementation. Since we need to use
* the buffer.[ch] sources here, which indirectly rely on most of libfrr, we
* have to ignore them when compiling clippy to avoid build dependency issues.
*
* TODO: Fix clippy build.
*/
/*
* Default node printer for use with graph_dump_dot.
*
* @param gn the node to print
* @param buf the buffer to print into
*/
void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf);
/*
* Prints a graph in the DOT language.
*
* The generated output is produced from a depth-first traversal of the graph.
*
* @param graph the graph to print
* @param start the node to take as the root
* @param pcb callback called for each node in the traversal that should
* print the node in the DOT language. Passing NULL for this argument
* will use the default printer. See graph_dump_dot_default_print_cb for
* an example.
* @return representation of graph in DOT language, allocated with MTYPE_TMP.
* Caller is responsible for freeing this string.
*/
char *graph_dump_dot(struct graph *graph, struct graph_node *start,
void (*pcb)(struct graph_node *, struct buffer *buf));
#endif /* BUILDING_CLIPPY */
#ifdef __cplusplus
}
#endif
#endif /* _ZEBRA_COMMAND_GRAPH_H */
|
