static bool dfs_find_a_path_between()

in src/backend/utils/adt/age_vle.c [929:1045]

• 65 lines of code
• 15 McCabe index (conditional complexity)

static bool dfs_find_a_path_between(VLE_local_context *vlelctx)
{
    ListGraphId *vertex_stack = NULL;
    ListGraphId *edge_stack = NULL;
    ListGraphId *path_stack = NULL;
    graphid end_vertex_id;

    Assert(vlelctx != NULL);

    /* for ease of reading */
    vertex_stack = vlelctx->dfs_vertex_stack;
    edge_stack = vlelctx->dfs_edge_stack;
    path_stack = vlelctx->dfs_path_stack;
    end_vertex_id = vlelctx->veid;

    /* while we have edges to process */
    while (!(IS_GRAPHID_STACK_EMPTY(edge_stack)))
    {
        graphid edge_id;
        graphid next_vertex_id;
        edge_state_entry *ese = NULL;
        edge_entry *ee = NULL;
        bool found = false;

        /* get an edge, but leave it on the stack for now */
        edge_id = PEEK_GRAPHID_STACK(edge_stack);
        /* get the edge's state */
        ese = get_edge_state(vlelctx, edge_id);
        /*
         * If the edge is already in use, it means that the edge is in the path.
         * So, we need to see if it is the last path entry (we are backing up -
         * we need to remove the edge from the path stack and reset its state
         * and from the edge stack as we are done with it) or an interior edge
         * in the path (loop - we need to remove the edge from the edge stack
         * and start with the next edge).
         */
        if (ese->used_in_path)
        {
            graphid path_edge_id;

            /* get the edge id on the top of the path stack (last edge) */
            path_edge_id = PEEK_GRAPHID_STACK(path_stack);
            /*
             * If the ids are the same, we're backing up. So, remove it from the
             * path stack and reset used_in_path.
             */
            if (edge_id == path_edge_id)
            {
                pop_graphid_stack(path_stack);
                ese->used_in_path = false;
            }
            /* now remove it from the edge stack */
            pop_graphid_stack(edge_stack);
            /*
             * Remove its source vertex, if we are looking at edges as
             * un-directional. We only maintain the vertex stack when the
             * edge_direction is CYPHER_REL_DIR_NONE. This is to save space
             * and time.
             */
            if (vlelctx->edge_direction == CYPHER_REL_DIR_NONE)
            {
                pop_graphid_stack(vertex_stack);
            }
            /* move to the next edge */
            continue;
        }

        /*
         * Mark it and push it on the path stack. There is no need to push it on
         * the edge stack as it is already there.
         */
        ese->used_in_path = true;
        push_graphid_stack(path_stack, edge_id);

        /* now get the edge entry so we can get the next vertex to move to */
        ee = get_edge_entry(vlelctx->ggctx, edge_id);
        next_vertex_id = get_next_vertex(vlelctx, ee);

        /*
         * Is this the end of a path that meets our requirements? Is its length
         * within the bounds specified?
         */
        if (next_vertex_id == end_vertex_id &&
            get_stack_size(path_stack) >= vlelctx->lidx &&
            (vlelctx->uidx_infinite ||
             get_stack_size(path_stack) <= vlelctx->uidx))
        {
            /* we found one */
            found = true;
        }
        /*
         * If we have found the end vertex but, we are not within our upper
         * bounds, we need to back up. We still need to continue traversing
         * the graph if we aren't within our lower bounds, though.
         */
        if (next_vertex_id == end_vertex_id &&
            !vlelctx->uidx_infinite &&
            get_stack_size(path_stack) > vlelctx->uidx)
        {
            continue;
        }

        /* add in the edges for the next vertex if we won't exceed the bounds */
        if (vlelctx->uidx_infinite ||
            get_stack_size(path_stack) < vlelctx->uidx)
        {
            add_valid_vertex_edges(vlelctx, next_vertex_id);
        }

        if (found)
        {
            return true;
        }
    }

    return false;
}