Depth-first graph traversal (DFS)

depth-first graph traversal.js

/**
 * General implementation of depth-first graph traversal (OK to have loops),
 * no recursion.
 */
function depthFirstTraverse(connections, i=0) {
    let visited = {};
    let traverseStack = [[-1, i]]; // edge from A to B vertex
    let revisit = false;
        
    while (traverseStack.length) {
        let [last, j] = traverseStack[traverseStack.length - 1];
        visited[j] = 'in progress';
        let foundNext = false;
        
        log(revisit ? `Re-visit ${j}` : `Visit ${j}`);

        for (let k = 0; k < connections[j].length; k++) {
            // Check if there's connection available
            if (connections[j][k] === 0)
                continue;
            
            // Don't go back to direct ancestor
            if (k === last) {
                log(`Not going from ${j} to ${k} (came from there)`, 'Stack:', traverseStack, 'Visited:', visited);
                continue;
            }

            if (visited[k]) {
                log(`Not going from ${j} to ${k} (already visited)`, 'Stack:', traverseStack, 'Visited:', visited);

                if (visited[k] === 'in progress')
                    log(`Loop found at ${j} - ${k}`);
            } else {
                traverseStack.push([j, k]);
                foundNext = true;
                revisit = false;
                log(`Going from ${j} to ${k}.`, 'Stack:', traverseStack, 'Visited:', visited);
                break;
            }
        }

        if (!foundNext) {
            traverseStack.pop();
            visited[j] = 'complete';
            revisit = true;
            log(`Finished with ${j}, look up through stack`, traverseStack);
        }
    }
}

/**
 * General implementation of depth-first graph traversal (OK to have loops)
 * with recusrion.
 */
function depthFirstTraverseRecursion(connections, current=0, last=-1, visited={}) {
    log(`Visit ${current}`);
    visited[current] = 'in-progress';

    for (let k = 0; k < connections[current].length; k++) {
        // Check if there's connection available
        if (connections[current][k] === 0)
            continue;
        
        // Don't go back to direct ancestor
        if (k === last) {
            log(`Not going from ${current} to ${k} (came from there)`, 'Visited:', visited);
            continue;
        }

        if (visited[k]) {
            log(`Not going from ${current} to ${k} (already visited)`, 'Visited:', visited);

            if (visited[k] === 'in progress')
                log(`Loop found at ${current} - ${k}`);
        } else {
            log(`Going from ${current} to ${k}.`, 'Visited:', visited);
            depthFirstTraverseRecursion(connections, k, last=current, visited);
        }
    }

    visited[current] = 'complete';
    log(`Finished with ${current}`);
}

/**
 * General implementation of depth-first graph traversal (OK to have loops)
 * with recusrion. Modification with path and without loop detection.
 */
function depthFirstTraverse({connections, current=0, path=[], visited=new Set}) {
    log(`Visit ${current} from path:`, path);
    visited.add(current);
    path = [...path, current];
    log('Current path:', path);

    for (let i = 0; i < connections[current].length; i++) {
        if (connections[current][i] === 0) {
            continue;
        }
        
        if (i === path[path.length - 1]) {
            log(`Not going from ${current} to ${i} (came from there)`);
            continue;
        }

        if (visited.has(i)) {
            log(`Not going from ${current} to ${i} (already visited):`, visited);
            continue;
        }
        
        log(`Check compatibility of ${i} with current path:`, path);
        let compatible = true;
        
        for (let j of path) {
            compatible &= connections[i][j] === 1;
        }
        
        if (compatible) {
            log('Compatible.');
        } else {
            log(`Not compatible.\nNot going from ${current} to ${i}.`);
            continue;
        }
        
        log(`Going from ${current} to ${i}.`);
        depthFirstTraverse({connections, current: i, path, visited});
    }

    log(`Finished with ${current}.`);
}

function log(...args) {
    if (log.enabled)
        console.log(...args);
}

log.enabled = true;