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

Typedefs

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

| Param | Type | | --- | --- | | list | Array.<Array.<number>> | TraversalOptions | | [opts] | TraversalOptions |

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

| Param | Type | | --- | --- | | list | Array.<Array.<number>> | TraversalOptions | | [opts] | TraversalOptions |

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

| Param | Type | Default | | --- | --- | --- | | nodes | Array.<Array.<number>> | | | fn | SimpleWalkerCallback | | | [root] | number | 0 |

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

| Param | Type | Default | | --- | --- | --- | | nodes | Array.<Array.<number>> | | | fn | SimpleWalkerCallback | | | [root] | number | 0 |

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

| Param | Type | Default | | --- | --- | --- | | nodes | Array.<Array.<number>> | | | fn | SimpleWalkerCallback | | | [root] | number | 0 |

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

| Param | Type | Default | | --- | --- | --- | | nodes | Array.<Array.<number>> | | | fn | SimpleWalkerCallback | | | [root] | number | 0 |

TraversalOptions : object

Kind: global typedef
Properties

| Name | Type | Default | Description | | --- | --- | --- | --- | | nodes | Array.<Array.<number>> | | Optionally, you can put your array of nodes here | | startIndex | number | 0 | Where to start, defaults to zero | | pre | NodeWalkerCallback | | Callback in pre-order | | post | NodeWalkerCallback | | Callback in post-order | | rpre | NodeWalkerCallback | | Callback in reverse pre-order | | rpost | NodeWalkerCallback | | Callback in reverse post-order | | edge | EdgeCB | | Callback for every edge or each type, see EdgeCB below | | spanningTree | boolean | true | A strongly connected graph with all nodes reachable from a common root | | flat | boolean | false | Use an iterative walker, not recursive | | excludeRoot | boolean | false | Do not invoke a callback for the root node | | preOrder | boolean | true | Return an array of node indices in pre-order | | postOrder | boolean | true | Return an array of node indices in post-order | | rPreOrder | boolean | false | Return an array of node indices in reverse pre-order | | rPostOrder | boolean | false | Return an array of node indices in reverse post-order | | edges | boolean | true | Return edge information in the results object | | trusted | boolean | false | Set trusted to true if you know your input is valid, i.e. an array where each element is either a number or an array of numbers. |

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

| Name | Type | Description | | --- | --- | --- | | tree | EdgeTypeCallback | Callback for each tree edge | | forward | EdgeTypeCallback | Callback for each forward edge (not applicable for BFS) | | back | EdgeTypeCallback | Callback for each back edge | | cross | EdgeTypeCallback | Callback for each cross edge |

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

| Name | Type | | --- | --- | | preOrder | Array.<number> | | postOrder | Array.<number> | | rPreOrder | Array.<number> | | rPostOrder | Array.<number> | | edges | DFSEdges |

BFSTraversalResult : object

Kind: global typedef
Properties

| Name | Type | | --- | --- | | preOrder | Array.<number> | | rPreOrder | Array.<number> | | levels | Array.<number> | | edges | BFSEdges |

SimpleWalkerCallback

Kind: global typedef

| Param | Type | Description | | --- | --- | --- | | nodeIndex | number | The index of the node input the input array | | orderedIndex | number | The index into the ordered walk, goes from 0 to N - 1 | | kill | function | Return this or call it, with or without a value, to stop the walk |

NodeWalkerCallback

Kind: global typedef

| Param | Type | Description | | --- | --- | --- | | nodeIndex | number | The index of the node in the original input array | | orderedIndex | number | The sequence number of the node in order, goes 0 to N - 1 | | orderedSequence | Array.<number> | The entire ordered sequence |

EdgeTypeCallback

Kind: global typedef
Properties

| Name | Type | | --- | --- | | from | number | | to | number |

EdgeCallback

Kind: global typedef

| Param | Type | | --- | --- | | from | number | | to | number | | type | string |