Skip to content

OronNadiv/bfs-as-promised

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

#BFS as Promised — Promisified Breadth-First Search.

NPM Version Build Status Test Coverage Dependencies JavaScript Style Guide

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

About

BFS as Promised — Promisified Breadth-First Search

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published