-
Notifications
You must be signed in to change notification settings - Fork 430
feat: Add dijkstra::with_dynamic_goal #855
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
Conversation
|
Hey, first off thanks for your PR 🌟 I very much like the feature you are adding in your PR and also like the ideas you bring to the table, with the Custom Struct as Return Type, as well as taking closures as function parameters. I will have a closer look in the coming days :) The thing is that there is the desire to convert a lot of the algorithms to return Custom Struct Return Types and possibly take closures as input similar to what Pathfinding does. However, we still need to figure out what the general direction/design of that should look like. Nevertheless, I am not opposed to taking a first step with your PR and possibly changing/adapting it at a later point in time :) Especially since your current change is not a breaking one and a future one would probably be a breaking change. The only thing I could imagine to make sense to do, while we are at it, to not have to break an API in the future is, instead of taking a graph as an input, taking an I would be curious to hear what you think @starovoid |
ab7db4e to
80f9f32
Compare
|
@RaoulLuque Hey, sorry for the long wait First of all, I would like to note that it is a really useful feature. The same thing has been requested for a long time for the A* algorithm.
This approach has already been implemented in places (for example,
It seems to me that this does not correspond well with |
|
Hi @SOF3 , please run |
46601e6 to
7b9520e
Compare
|
Hi @SOF3 , an error occurs when compiling tests for Rust 1.64.0 (our MSRV). Please rewrite these fragment, and I think there will be no further problems. |
5306110 to
2eef9a1
Compare
|
fixed, please run CI again |
Allow the goal node to be dynamically and lazily evaluated. This can be useful in graphs where testing whether a node is the goal is costly (e.g. "a node is a goal if its hash is equal to a list of possible values") <!-- -- Thanks for contributing to `petgraph`! -- -- We require PR titles to follow the Conventional Commits specification, -- https://www.conventionalcommits.org/en/v1.0.0/. This helps us generate -- changelogs and follow semantic versioning. -- -- Start the PR title with one of the following: -- * `feat:` for new features -- * `fix:` for bug fixes -- * `refactor:` for code refactors -- * `docs:` for documentation changes -- * `test:` for test changes -- * `perf:` for performance improvements -- * `revert:` for reverting changes -- * `ci:` for CI/CD changes -- * `chore:` for changes that don't fit in any of the above categories -- The last two categories will not be included in the changelog. -- -- If your PR includes a breaking change, please add a `!` after the type -- and include a `BREAKING CHANGE:` line in the body of the PR describing -- the necessary changes for users to update their code. -- -->
Allow the goal node to be dynamically and lazily evaluated. This can be useful in graphs where testing whether a node is the goal is costly (e.g. "a node is a goal if its hash is equal to a list of possible values") <!-- -- Thanks for contributing to `petgraph`! -- -- We require PR titles to follow the Conventional Commits specification, -- https://www.conventionalcommits.org/en/v1.0.0/. This helps us generate -- changelogs and follow semantic versioning. -- -- Start the PR title with one of the following: -- * `feat:` for new features -- * `fix:` for bug fixes -- * `refactor:` for code refactors -- * `docs:` for documentation changes -- * `test:` for test changes -- * `perf:` for performance improvements -- * `revert:` for reverting changes -- * `ci:` for CI/CD changes -- * `chore:` for changes that don't fit in any of the above categories -- The last two categories will not be included in the changelog. -- -- If your PR includes a breaking change, please add a `!` after the type -- and include a `BREAKING CHANGE:` line in the body of the PR describing -- the necessary changes for users to update their code. -- -->
Allow the goal node to be dynamically and lazily evaluated. This can be useful in graphs where testing whether a node is the goal is costly (e.g. "a node is a goal if its hash is equal to a list of possible values") <!-- -- Thanks for contributing to `petgraph`! -- -- We require PR titles to follow the Conventional Commits specification, -- https://www.conventionalcommits.org/en/v1.0.0/. This helps us generate -- changelogs and follow semantic versioning. -- -- Start the PR title with one of the following: -- * `feat:` for new features -- * `fix:` for bug fixes -- * `refactor:` for code refactors -- * `docs:` for documentation changes -- * `test:` for test changes -- * `perf:` for performance improvements -- * `revert:` for reverting changes -- * `ci:` for CI/CD changes -- * `chore:` for changes that don't fit in any of the above categories -- The last two categories will not be included in the changelog. -- -- If your PR includes a breaking change, please add a `!` after the type -- and include a `BREAKING CHANGE:` line in the body of the PR describing -- the necessary changes for users to update their code. -- -->
## 🤖 New release * `petgraph`: 0.8.2 -> 0.8.3 (✓ API compatible changes) <details><summary><i><b>Changelog</b></i></summary><p> <blockquote> ## [0.8.3](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.2...petgraph@v0.8.3) - 2025-09-28 ### Bug Fixes - Infinite `subgraph_isomorphisms_iter` for empty isomorphisms ([#780](#780)) - Algos don't work on `UndirectedAdaptor` ([#870](#870)) ([#871](#871)) - use a queue for SPFA ([#893](#893)) - `StableGraph::reverse` breaks free lists ([#890](#890)) ### Documentation - Fix examples link in README and unify typesetting of one word ([#823](#823)) - Add link to multigraph definition to isomorphism algos ([#824](#824)) - Fix auxiliary space (and time) complexity of bron-kerbosch ([#825](#825)) - Fix Typo in Operator Module Documentation ([#831](#831)) - Sync the crate feature flags in the README and docs ([#832](#832)) - Remove all \[Generic\] tags from algo docstrings ([#835](#835)) - Fix typos in comments ([#836](#836)) - Revamp CONTRIBUTING.md ([#833](#833)) - Update `GraphMap` link in README ([#857](#857)) - Add doc comment for `Dot::with_attr_getters` ([#850](#850)) - Specify iteration order for neighbors and edges and their variants ([#790](#790)) - Collection of Doc fixes ([#856](#856)) ### New Features - Add `into_nodes_edges_iters` to `StableGraph` ([#841](#841)) - Add methods to reserve & shrink `StableGraph` capacity ([#846](#846)) - Add Dinic's Maximum Flow Algorithm ([#739](#739)) - make Csr::from_sorted_edges generic over edge type and properly increase edge_count in Csr::from_sorted_edges ([#861](#861)) - Add `map_owned` and `filter_map_owned` for `Graph` and `StableGraph` ([#863](#863)) - Add dijkstra::with_dynamic_goal ([#855](#855)) - Fix self-loop bug in all_simple_paths and enable multiple targets ([#865](#865)) - mark petgraph::dot::Dot::graph_fmt as public ([#866](#866)) - Add bidirectional Dijkstra algorithm ([#782](#782)) ### Performance - Make A* tie break on lower h-values ([#882](#882)) ### Refactor - add examples for scc algorithms and reorganize into dedicated module ([#830](#830)) - Remove unnecessary trait bounds from impls/methods ([#828](#828)) - replace uses of 'crate::util::zip' with 'core::iter::zip' ([#849](#849)) - Fix clippy (and other) lints ([#851](#851)) - Cleanup repo ([#854](#854)) - replace crate::util::enumerate with Iterator::enumerate ([#881](#881)) ### Testing - Add dependency list for 'quickcheck' feature ([#822](#822)) - Fix feature cfg capitalization in doctest ([#852](#852)) </blockquote> </p></details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: Egor Starovoitov <52821033+starovoid@users.noreply.github.com>
Allow the goal node to be dynamically and lazily evaluated.
This can be useful in graphs where testing whether a node is the goal is costly (e.g. "a node is a goal if its hash is equal to a list of possible values")