Narcissistic Pickle Meister
    Have ideas to improve npm?Join in the discussion! »

    iddfs

    2.0.0 • Public • Published

    IDDFS

    Greenkeeper badge npm license CircleCI codecov

    Iterative deepening depth-first search (IDDFS) for JavaScript

    Install

    npm i iddfs
    

    Requirement

    • Node.js
      • 8+
    • Browser support
      • TODO

    Usage

    import iddfs from 'iddfs'
     
    const A = 'A'
    const B = 'B'
    const C = 'C'
    const D = 'D'
    const E = 'E'
    const F = 'F'
    const G = 'G'
     
    // [A]-[B]-[D]
    //  |\   `-[F]-,
    //  | `[C]-(G) |
    //   `-[E]-----/
    // Expected: A -> C -> G
    // https://ja.wikipedia.org/wiki/%E5%8F%8D%E5%BE%A9%E6%B7%B1%E5%8C%96%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
    const edges: { [Node]Array<Node} = {
      A: [B, C, E],
      B: [A, D, F],
      C: [A, G],
      D: [B],
      E: [A, F],
      F: [B, E],
      G: [C],
    }
     
    const found = await iddfs({
      initialNode: A,
      isGoal: (node) => node === G,
      expand: (node) => edges[node],
      extractId: (node) => node,
      maxDepth: 3,
    })
     
    console.log(found === G) // => true

    To find shortest path

    import { getPath } from 'iddfs'
     
    const path = await getPath({
      initialNode: A,
      isGoal: (node) => node === G,
      expand: (node) => edges[node],
      extractId: (node) => node,
      maxDepth: 3,
    })
     
    console.log(path) // => ['A', 'C', 'G']

    For more details, please refer out tests

    Options

    property required type description
    initialNode Yes any Node visited at first
    isGoal Yes (node: any) => boolean A function returns boolean what wanted node or not
    expand Yes (node: any) => Array<node: any> A function returns array of children node id
    extractId Yes (node: any) => string \| number A function returns identifier of node
    initialDepth - number Initial depth. Defaults is 0
    maxDepth - number Max depth. Defaults is Infinity
    shouldContinue - (node: T, depth: number, depthLimit: number) => boolean Advanced option. It must return boolean that whether it should continue search or not. Defaults returns always true
    isVisited - (node: any, Array<string \| number>) => ?number Advanced option. It must returns visited depth when node already visited. Otherwise, it must returns null

    Contribution

    1. Fork this repo
    2. Create your branch like fix-hoge-foo-bar add-hige
    3. Write your code
    4. Pass all checks (npm run lint && npm run flow && npm test)
    5. Commit with gitmoji
    6. Submit pull request to master branch

    License

    This package under MIT license.

    Install

    npm i iddfs

    DownloadsWeekly Downloads

    176

    Version

    2.0.0

    License

    MIT

    Unpacked Size

    27.2 kB

    Total Files

    19

    Last publish

    Collaborators

    • avatar