On Tue, Apr 7, 2020 at 5:46 PM Andrzej Ostruszka <a...@semihalf.com> wrote:
> > +int
> > +graph_bfs(struct graph *graph, struct graph_node *start)
> > +{
> > + struct graph_node **queue, *v, *tmp;
> > + uint16_t head = 0, tail = 0;
> > + rte_edge_t i;
> > + size_t sz;
> > +
> > + sz = sizeof(struct graph_node *) * graph_nodes_count(graph);
> > + queue = malloc(sz);
> > + if (queue == NULL)
> > + SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu",
> > + sz);
> > +
> > + /* BFS algorithm */
> > + queue[tail++] = start;
> > + start->visited = true;
> > + while (head != tail) {
> > + v = queue[head++];
> > + for (i = 0; i < v->node->nb_edges; i++) {
> > + tmp = v->adjacency_list[i];
> > + if (tmp->visited == false) {
> > + queue[tail++] = tmp;
> > + tmp->visited = true;
> > + }
> > + }
> > + }
> > +
> > + free(queue);
> > + return 0;
> > +
> > +fail:
> > + return -rte_errno;
> > +}
>
> What is the purpose of this function? It looks like just marking as
> visited. Then maybe change the name to graph_mark_bfs() or something
> like that.
graph_ops.c has all generic graph-related functions.
BFS(Breadth-First Search) is a generic graph operation. The primitive
can be used for various other graph operations.
IMO, It is better to avoid connecting with a marking using case in the
function name.
>
> > +
> > +/* Check whether a node has connected path or parent node */
> > +int
> > +graph_has_isolated_node(struct graph *graph)
> > +{
> > + struct graph_node *graph_node;
> > +
> > + graph_mark_nodes_as_not_visited(graph);
See below,
> > +
> > + STAILQ_FOREACH(graph_node, &graph->node_list, next) {
> > + if (graph_node->node->flags & RTE_NODE_SOURCE_F) {
> > + if (graph_node->node->nb_edges == 0)
> > + SET_ERR_JMP(EINVAL, fail,
> > + "%s node needs minimum one edge",
> > + graph_node->node->name);
> > + if (graph_bfs(graph, graph_node))
> > + goto fail;
> > + }
> > + }
> > +
> > + STAILQ_FOREACH(graph_node, &graph->node_list, next)
> > + if (graph_node->visited == false)
> > + SET_ERR_JMP(EINVAL, fail, "Found isolated node %s",
> > + graph_node->node->name);> +
> > + return 0;
>
> You don't want to clear visited because it will not be used or cleared
> on next call?
See above graph_mark_nodes_as_not_visited() function.
>
> With regards
> Andrzej Ostruszka
