IDDFS
Iterative deepening depth-first search (IDDFS) for JavaScript
Install
npm i iddfs
Requirement
- Node.js
- 8+
- Browser support
- TODO
Usage
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%A2const 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 console // => true
To find shortest path
const path = await console // => ['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
- Fork this repo
- Create your branch like
fix-hoge-foo-bar
add-hige
- Write your code
- Pass all checks (
npm run lint && npm run flow && npm test
) - Commit with gitmoji
- Submit pull request to
master
branch
License
This package under MIT license.