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?

• Zwibbler: A simple drawing program using Javascript and Canvas
• Make Windows XP look like Ubuntu, with Spinning Cube Effect
• Free, Raw Stock Data
• Is 2009 the year of Linux malware?
• What does your phone number spell?

Want more programming tech talk?
Add to Circles on Google Plus
Subscribe to posts