On 4/7/20 2:27 PM, Jerin Jacob wrote:
> 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.
Yes I noticed that and referred to it in the question. My intention was
to ask whether you are fine with graph having visited=true for the rest
of its life, or should we clear them again at the end of this function.
With regards
Andrzej Ostruszka
