Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Walk: add breadth-first option #61

Open
schomatis opened this issue Feb 5, 2021 · 1 comment · May be fixed by #63
Open

Walk: add breadth-first option #61

schomatis opened this issue Feb 5, 2021 · 1 comment · May be fixed by #63
Labels
need/triage Needs initial labeling and prioritization

Comments

@schomatis
Copy link
Contributor

Currently Walk() only has a WalkDepth() implementation. I would like to add a WalkBreadth() one. It seems straight-forward enough:

  • Add an option in walkOptions (and process it in Walk() instead of its WalkDepth() callee).
  • Implement a basic (sequential) BFS leveraging the same GetLinks() and visit callbacks.

Before taking a stab at it I need confirmation that this is the right path. Particularly, I see that a BFS search is already implemented in the traverse package which overlaps substantially with the logic in Walk().

@schomatis schomatis added the need/triage Needs initial labeling and prioritization label Feb 5, 2021
@schomatis
Copy link
Contributor Author

I have a first draft in https://github.com/ipfs/go-merkledag/compare/schomatis/walk/breadth-first?expand=1 but now I'm told the best option would be to drop the Walk API of this repo altogether and go with https://pkg.go.dev/github.com/ipld/go-ipld-prime/traversal#WalkMatching (see #62).

I don't have a clear example of how to use the proposed alternative and since porting to it would demand an unknown amount of time/effort I'm pushing ahead with my implementation here, but this is clearly wrong as I'm duplicating functionality already available.

@schomatis schomatis linked a pull request Feb 5, 2021 that will close this issue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
need/triage Needs initial labeling and prioritization
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant