Need private packages and team management tools?Check out npm Teams »

traversals

1.0.15 • Public • Published

traversals

Coveralls Status Build Status Dependency Status npm version License Known Vulnerabilities david-dm

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

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

Install

npm i traversals

DownloadsWeekly Downloads

7

Version

1.0.15

License

MIT

Last publish

Collaborators

  • avatar