The simple and obvious way to walk through a graph

At some point in your programming career you may have to go through a graph of items and process them all exactly once. If you keep following neighbours, the path might loop back on itself, so you need to keep track of which ones have been processed already.

function process_node( node )
{
    if ( node.processed ) {
        return;
    }

    node.processed = true;

    var i;
    for( i = 0; i < node.neighbours.length; i++ ) {
        process_node( node.neighbours[i] );
    }

    // code to process the node goes here. It is executed only
    // once per node.
}

The code works, but it only works once! The next time you try it, all the nodes will already be marked as processed, so nothing will happen.

Here's a neat trick that elegantly solves the problem. Instead of using a boolean flag in each node, use a generation count.

var CurrentGeneration = 0;
function process_node( node )
{
    if ( node.generation == CurrentGeneration ) {
        return;
    }
    
    node.generation = CurrentGeneration;

    var i;
    for( i = 0; i < node.neighbours.length; i++ ) {
        process_node( node.neighbours[i] );
    }

    // code to process the node goes here. It is executed only
    // once per node.
}

function process_all_nodes( root )
{
    CurrentGeneration += 1;
    process_node( root );
}

It's simple and obvious right? So why didn't I think of it in eight years?