traversals

Small module for graph traversals, supporting DFS and BFS with niceties added for pre- and post-order, including their reverses.

Install

npm i traversals

Usage

const  
    { DFS, BFS } = require( 'traversals' ),
    someGraph = testGraph          = [
                        [ 1, 8 ],    // start
                        [ 2, 3 ],    // a
                        [ 3 ],       // b
                        [ 4, 5 ],    // c
                        [ 6 ],       // d
                        [ 6 ],       // e
                        [ 7, 2 ],    // f
                        [ 8 ],       // g
                        []           // end
                    ];
 
const { preOrder, postOrder } = DFS( someGraph );
 
// Output the nodes in pre-order
preOrder.forEach( pre => console.log( `We saw node at index ${pre}` ) );
 
// ...alternatively, use a callbacks. You can use some, all, or none of these.
 
function record_any_edge( from, to, type )
{
    console.log( `We have an edge from ${from} to ${to} with type "${type}"` );
}
 
// Use the function as an object. Normally, you would need these
// individually typed callbacks. But, for the sake of completeness...
record_any_edge.tree = ( from, to ) => console.log( `tree edge from ${from} to ${to}` ); 
record_any_edge.forward = ( from, to ) => console.log( `forward edge from ${from} to ${to}` ); 
record_any_edge.back = ( from, to ) => console.log( `back edge from ${from} to ${to}` ); 
record_any_edge.cross = ( from, to ) => console.log( `cross edge from ${from} to ${to}` ); 
 
DFS( someGraph, { 
    pre( n ) { console.log( `pre-order: ${n}` ); }, 
    post( n ) { console.log( `post-order: ${n}` ); }, 
    rpre( n ) { console.log( `reverse pre-order: ${n}` ); }, 
    rpost( n ) { console.log( `reverse post-order: ${n}` ); },
    edge: record_any_edge
} );
 
// Or, if you just wanted, say, tree edges...
 
DFS( someGraph, { edge: { tree: ( from, to ) => console.log( `tree from ${from} to ${to}` ) } } );
 
// The BFS is much the same, except you get levels back but no post-order. Both have pre-order.
// BFS also has no forward edges.

For quick and easy traversals, when you just want to be called in once per node in a particular order, you can use the function shown below. The following shows various uses of the pre-order walk. The other three walks work in an identical manner.

const 
    { preOrder } = require( 'traversals' ); // The other 3 functions
                                                // are: postOrder, 
                                                // rPreOrdder, and
                                                // rPostOrder
 
// For all of these walks, you can abort it at any stage by returning
// or calling the third argument. In the first example, however, we
// just run allthe way through.
 
preOrder( testGraph, ( nodeNum, preNum ) => {
    // preNum just goes from 0 to N - 1
    console.log( `Node index: ${nodeNum}, pre-order index: ${preNum}` );
} );
 
// In this case, we stop the walk and return a result, in this case, the
// returnValue will be 3
let returnValue = preOrder( testGraph, ( nodeNum, index, kill ) => {
    console.log( `Node index: ${nodeNum}, pre-order index: ${preNum}` );
    // Return kill to stop the walk, here we stop on node index 3
    return nodeNum === 3 && kill;
} );
 
const preSeq = [];
 
// Return value here will be 4
returnValue = preOrder( testGraph, ( nodeNum, index, kill ) => {
    // Create a list of node indices in pre-order
    preSeq.push( nodeNum );
    // When we reach node index 4, call kill to stop the walk
    nodeNum === 4 && kill();
}, 0 );
 
let prev, 
    nodeJustBeforeThis = 3;
 
// Here we stop the walk with an arbitrary value of our own choosing
// again by calling the kill function with the value.
returnValue = preOrder( testGraph, ( nodeNum, index, kill ) => {
    nodeNum === nodeJustBeforeThis && kill( prev );
    prev = nodeNum;
} );
 

API

Functions

DFS(list, [opts]) ⇒ DFSTraversalResult

A more involved traversal that's not as efficient as the simple walkers but provide more information. You can use this to generate pre-order, post-order (and their reverses) sequences, as well as edge information, all in a single pass.

It does not provide levels which you need to get from the BFS traversal.

BFS(list, [opts]) ⇒ BFSTraversalResult

Much the same as the DFS function, it provides the same information and capabilities with a few exceptions.

1. It does not provide forward edge information.
2. It does not generate a post-order walk.

It does, however, provides levels.

preOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

postOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

rPreOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

rPostOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

Typedefs

TraversalOptions : object

EdgeCB : EdgeCallback | Object

You can define the edge field as a normal function and it will be called on each discovered edge with the from and to node numbers, as well as the edge type. Alternatively, yuou can also just set the field to an object.

The function or object can have four optional fields, one for each edge type. These will be called on the discovery of their respective types. If you added these fields to a function, the main function will be called, in addition to these.

DFSTraversalResult : object

BFSTraversalResult : object

SimpleWalkerCallback

NodeWalkerCallback

EdgeTypeCallback

EdgeCallback

DFS(list, [opts]) ⇒ DFSTraversalResult

A more involved traversal that's not as efficient as the simple walkers but provide more information. You can use this to generate pre-order, post-order (and their reverses) sequences, as well as edge information, all in a single pass.

It does not provide levels which you need to get from the BFS traversal.

Kind: global function

BFS(list, [opts]) ⇒ BFSTraversalResult

Much the same as the DFS function, it provides the same information and capabilities with a few exceptions.

1. It does not provide forward edge information.
2. It does not generate a post-order walk.

It does, however, provides levels.

Kind: global function

preOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

Kind: global function

postOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

Kind: global function

rPreOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

Kind: global function

rPostOrder(nodes, fn, [root])

Call this with the node list and a callback function. If the graph does not start at index 0 then add the actual start index as the third argument.

Kind: global function

TraversalOptions : object

Kind: global typedef
Properties

EdgeCB : EdgeCallback | Object

You can define the edge field as a normal function and it will be called on each discovered edge with the from and to node numbers, as well as the edge type. Alternatively, yuou can also just set the field to an object.

The function or object can have four optional fields, one for each edge type. These will be called on the discovery of their respective types. If you added these fields to a function, the main function will be called, in addition to these.

Kind: global typedef
Properties

Example

// For each backedge
DFS( nodes, {
    edge: { back: ( from, to ) => console.log( `back edge from ${from} to ${to}` )
    // ...
} );

Example

// For all edges and one just for tree edges
function everyEdge( from, to, type )
{
    console.log( `Discovered ${type} edge from ${from} to ${to}` );
}
 
everyEdge.tree = ( from, to ) => console.log( `Discovered a tree edge from ${from} to ${to}` );
 
DFS( nodes, {
    edge: everyEdge
    // ...
} );

DFSTraversalResult : object

Kind: global typedef
Properties

BFSTraversalResult : object

Kind: global typedef
Properties

SimpleWalkerCallback

Kind: global typedef

NodeWalkerCallback

Kind: global typedef

EdgeTypeCallback

Kind: global typedef
Properties

EdgeCallback

Kind: global typedef