onion-core/dist/lib/util/dfs.js

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.findDFS = void 0;
// Generic depth-first search.
// getNeighbors should return an array of 'outgoing links', where each link is a pair [label, neighboring_element]
// neighbors are visited in the order that getNeighbors returns them, so getNeighbors can be optimized (e.g., via some heuristic) to minimize the number of visits.
// If the element 'searchFor' was reachable from the 'start', returns a PATH, i.e., an array of link-labels to get from start to 'searchFor'.
// If not reachable, returns undefined.
function findDFS(start, searchFor, getNeighbors) {
    const alreadyVisited = new Set([start]); // only visit every 'thing' once
    let recursiveInvocations = 0;
    function findDFSRecursive(current, currentPath) {
        recursiveInvocations++;
        if (current === searchFor) {
            return currentPath;
        }
        const neighbors = getNeighbors(current);
        // console.log("current", current, "neighbors:", neighbors)
        for (const [link, neighbor] of neighbors) {
            if (alreadyVisited.has(neighbor)) {
                continue;
            }
            alreadyVisited.add(neighbor);
            const recursiveResult = findDFSRecursive(neighbor, [...currentPath, link]);
            if (recursiveResult !== undefined) {
                return recursiveResult;
            }
            // continue with next neighbor...
        }
    }
    const result = findDFSRecursive(start, []);
    // console.log("findDFS recursiveInvocations (performance metric, less is better):", recursiveInvocations);
    return result;
}
exports.findDFS = findDFS;
//# sourceMappingURL=dfs.js.map