bfs-as-promised

BFS as Promised — Promisified Breadth-First Search.

Asynchronous implementation of BFS to find the shortest path. The implementation uses Bluebird's promise.

Example:

const BFS = require('bfs-as-promised');
const graph = new Map([
    [1, [2, 3]],
    [2, [3, 4]],
    [3, []],
    [4, [5]]
])
const getMoves = (fromNodes) => {
    const res = new Map()
    return Promise
        .each(fromNodes, (fromNode) => {
            res.set(fromNode, graph.get(fromNode) || [])
        })
        .return(res)
}
 
const isGoal = (item) => item === 5
const bfs = new BFS(1, getMoves, isGoal)
bfs.find().then((path) => console.log(path)) // [1, 2, 4, 5]

Usage:

const bfs = new BFS(<start>, <getMoves>, <isGoal>)
bfs.find().then((<path>) => ...)

start

Assuming we are trying to find the shortest path from node A to node B. Start parameter will be node A.

getMoves(fromNodes, depth)

The function should returns a map where the key is a value from the array fromNodes and the value is an array of nodes that can be reached from the given key.
The function may also return a promise that once resolved, will return the above map.

E.g. For the following graph:

1 -> 2
1 -> 3
2 -> 3

getMoves([1, 2, 3]) should return a map with the following values:

new Map([
    [1, [2,3]],
    [2, [3]],
    [3, []]
])

isGoal(node)

The function should return a boolean value true/false. Where true means the given node is the "finish" node, otherwise false.
The function may also return a promise that once resolved, will return true/false.

find()

This function returns a promise. The promise, once resolved, will return the shorted BFS path (if exists) or null if such path does not exist.

E.g. for the following graph:

1 -> 2
1 -> 3
2 -> 3
2 -> 4
4 -> 5

Calling find() where start node is 1 and goal node is 5, will return a promise that, once resolved, it will returns [1, 2, 4, 5].
Calling find() where start node is 1 and goal node is -1, will return a promise that, once resolved, it will returns null.

License

MIT