Searchs backwards iteratively through a graph from the head nodes to find the set of last common ancestors that all paths pass through and that are reachable from the head nodes.

graph.ts

//
// Search backwards iteratively through a graph from the head nodes to find the set of last common 
// ancestors that all paths pass through and that are reachable from the head nodes.
//
export function findLastCommonAncestor(blockGraph: BlockGraph, blocks: string[]): IBlockNode[] {
    if (blocks.length === 0) {
        return [];
    }

    //
    // Starting the traversal at these nodes.
    //
    const headNodes = blocks.map(block => blockGraph.blockMap.get(block)!);

    //
    // Records the nodes that have been visited from any path during the traversal.
    //
    const visitedFromAnyPath = new Set<IBlockNode>();

    //
    // Records whether each node is reachable from a particular head node.
    // When any given node is reachable from all head nodes then it is a common ancestor.
    //
    const waysReachable = new Map<IBlockNode, Set<IBlockNode>>();    

    //
    // Tracks the set of common ancestors that we know about.
    // That is, the set of nodes that are reachable from all head nodes.
    //
    let commonAncestors = new Set<IBlockNode>();

    //
    // Marks a node as reached.
    //
    function markReachable(node: IBlockNode, headNode: IBlockNode) {
        visitedFromAnyPath.add(node);
        if (waysReachable.get(node) === undefined) {
            waysReachable.set(node, new Set());
        }
        waysReachable.get(node)!.add(headNode);

        if (waysReachable.get(node)!.size >= headNodes.length) {
            //
            // Record that we have found a common ancestor.
            //
            commonAncestors.add(node);
        }
    }

    //
    // Mark the head nodes as reachable.
    //
    for (const headNode of headNodes) {
        markReachable(headNode, headNode);
    }

    //
    // Tracks the current open paths.
    //
    let openPaths = headNodes.map(node => ({ headNode: node, nodes: [ node ] }));

    //
    // While we have paths open continue the travseral.
    //
    while (openPaths.length > 0) {

        const everyPathTouchesCommonAncestor = openPaths.every(path => {
            return path.nodes.some(node => commonAncestors.has(node));
        });

        if (everyPathTouchesCommonAncestor) {
            // When every open path touches a common ancestor we can stop the traversal.
            // The set of blocks after and including the common ancestors is the set of
            // blocks we are interested in.
            break;
        }

        const everyPathHasEnded = 
          openPaths.every(path => path.nodes[path.nodes.length - 1].previousBlocks.length === 0);
        if (everyPathHasEnded) {
            // If all paths through the network have finished it means there is no
            // conclusive common ancestor.
            return [];
        }

        //
        // Expands the current path depending on how many branches we can take at this point.
        //
        const path = openPaths.shift()!;
        const latestNode = path.nodes[path.nodes.length - 1];
        if (latestNode.previousBlocks.length === 0) {
            //
            // This path has reached the end of the network.  
            // Keep this path in play.
            //
            openPaths.push(path);
            continue;
        }

        for (const previousNode of latestNode.previousBlocks) {
            //
            // For each branch, open a new path.
            //
            markReachable(previousNode, path.headNode);
            openPaths.push({ 
                headNode: path.headNode, 
                nodes: [ ...path.nodes, previousNode ],
            });
        }
    }

    return Array.from(commonAncestors);
}