Nothing Particularly Magnificent

    bfs-as-promised

    1.0.4 • Public • Published

    BFS as Promised — Promisified Breadth-First Search.

    NPM Version Build Status Test Coverage Dependencies js-standard-style

    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

    Install

    npm i bfs-as-promised

    DownloadsWeekly Downloads

    6

    Version

    1.0.4

    License

    MIT

    Last publish

    Collaborators

    • oronnadiv