Function Proc_BFS_Step

src/procedures/proc_bfs.c:143–218

}

static SIValue *Proc_BFS_Step
(
	ProcedureCtx *ctx
) {
	ASSERT(ctx->privateData);

	BFSCtx *bfs_ctx = (BFSCtx *)ctx->privateData;

	// return NULL if the BFS for this source has already been emitted
	// or there are no connected nodes
	if(bfs_ctx->depleted || bfs_ctx->n == 0) return NULL;

	bool yield_nodes = (bfs_ctx->yield_nodes != NULL);
	bool yield_edges = (bfs_ctx->yield_edges != NULL);

	// build arrays for the outputs the user has requested
	uint n = bfs_ctx->n;
	SIValue nodes, edges;
	if(yield_nodes) nodes = SI_Array(n);
	if(yield_edges) edges = SI_Array(n);
	Edge *edge = array_new(Edge, 1);

	// setup result iterator
	NodeID               id;
	GrB_Info             res;
	GxB_Iterator         iter;

	UNUSED(res);
	res = GxB_Iterator_new(&iter);
	ASSERT(res == GrB_SUCCESS);
	res = GxB_Vector_Iterator_attach(iter, bfs_ctx->nodes, NULL);
	ASSERT(res == GrB_SUCCESS);
	res = GxB_Vector_Iterator_seek(iter, 0);

	while(res == GrB_SUCCESS) {
		id = GxB_Vector_Iterator_getIndex(iter);

		// get the reached node
		if(yield_nodes) {
			// append each reachable node to the nodes output array
			Node n = GE_NEW_NODE();
			Graph_GetNode(bfs_ctx->g, id, &n);
			SIArray_Append(&nodes, SI_Node(&n));
		}

		if(yield_edges) {
			array_clear(edge);
			GrB_Index parent_id;
			// find the parent of the reached node
			GrB_Info res = GrB_Vector_extractElement(&parent_id,
					bfs_ctx->parents, id);
			ASSERT(res == GrB_SUCCESS);
			// retrieve edges connecting the parent node to the current node
			// TODO: we only require a single edge
			// `Graph_GetEdgesConnectingNodes` can return multiple edges
			Graph_GetEdgesConnectingNodes(bfs_ctx->g, parent_id, id, bfs_ctx->reltype_id, &edge);
			// append one edge to the edges output array
			SIArray_Append(&edges, SI_Edge(edge));