Skip to content

Conversation

@SOF3
Copy link
Contributor

@SOF3 SOF3 commented Jul 27, 2025

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")

@RaoulLuque RaoulLuque added C-feature-request Category: A feature request A-crate Area: Petgraph crate functionality C-refactor Category: PR/issue with specific code/suggestions for refactoring S-waiting-on-review Status: Awaiting review from the assignee but also other interested parties labels Jul 27, 2025
@RaoulLuque
Copy link
Member

RaoulLuque commented Jul 28, 2025

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 edges or neighbors closure, which would replace graph.edges(node). Thus we would be more flexible 🤔 However, this could also be done at a later point in time, and I don't want to bother you with it if you are simply interested in your desired feature ^^

I would be curious to hear what you think @starovoid

@starovoid
Copy link
Collaborator

starovoid commented Aug 29, 2025

@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.


to return Custom Struct Return Types

This approach has already been implemented in places (for example, bellman_ford::Paths). In theory, we could effectively generalize this approach to all shortest path algorithms. However, any significant change will be breaking, and this should be discussed with the wider community, because we don't want to create unnecessary difficulties for petgraph users pursuit of beauty :)

take closures as input similar to what Pathfinding does

It seems to me that this does not correspond well with petgraph style, because we provide abstraction and generality in a different way.

@starovoid
Copy link
Collaborator

Hi @SOF3 , please run cargo fmt to fix Lints CI.

@starovoid starovoid added S-waiting-on-author Status: Awaiting some action by the PR/Issue author C-feature-accepted Category: A feature request that has been accepted pending implementation and removed C-feature-request Category: A feature request S-waiting-on-review Status: Awaiting review from the assignee but also other interested parties labels Aug 29, 2025
@starovoid starovoid added this to the 0.8.3 milestone Aug 29, 2025
@SOF3 SOF3 force-pushed the dijkstra-dynamic branch from 80f9f32 to 46601e6 Compare August 31, 2025 05:31
@starovoid
Copy link
Collaborator

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.

failures:

---- src/algo/dijkstra.rs - algo::dijkstra::with_dynamic_goal (line 120) stdout ----
error[E0658]: use of unstable library feature 'is_some_with'
  --> src/algo/dijkstra.rs:163:23
   |
46 | assert!(res.goal_node.is_some_and(|n| n == d || n == f));
   |                       ^^^^^^^^^^^
   |
   = note: see issue #93050 <https://github.com/rust-lang/rust/issues/93050> for more information

error[E0277]: can't compare `&petgraph::prelude::NodeIndex` with `petgraph::prelude::NodeIndex`
  --> src/algo/dijkstra.rs:163:41
   |
46 | assert!(res.goal_node.is_some_and(|n| n == d || n == f));
   |                                         ^^ no implementation for `&petgraph::prelude::NodeIndex == petgraph::prelude::NodeIndex`
   |
   = help: the trait `PartialEq<petgraph::prelude::NodeIndex>` is not implemented for `&petgraph::prelude::NodeIndex`
   = help: the trait `PartialEq` is implemented for `petgraph::prelude::NodeIndex<Ix>`

error[E0277]: can't compare `&petgraph::prelude::NodeIndex` with `petgraph::prelude::NodeIndex`
  --> src/algo/dijkstra.rs:163:51
   |
46 | assert!(res.goal_node.is_some_and(|n| n == d || n == f));
   |                                                   ^^ no implementation for `&petgraph::prelude::NodeIndex == petgraph::prelude::NodeIndex`
   |
   = help: the trait `PartialEq<petgraph::prelude::NodeIndex>` is not implemented for `&petgraph::prelude::NodeIndex`
   = help: the trait `PartialEq` is implemented for `petgraph::prelude::NodeIndex<Ix>`

@SOF3 SOF3 force-pushed the dijkstra-dynamic branch 2 times, most recently from 5306110 to 2eef9a1 Compare September 5, 2025 14:31
@SOF3
Copy link
Contributor Author

SOF3 commented Sep 6, 2025

fixed, please run CI again

@starovoid starovoid added this pull request to the merge queue Sep 7, 2025
Merged via the queue into petgraph:master with commit e9b80db Sep 7, 2025
11 checks passed
@github-actions github-actions bot mentioned this pull request Sep 7, 2025
@SOF3 SOF3 deleted the dijkstra-dynamic branch September 7, 2025 11:56
RaoulLuque pushed a commit to RaoulLuque/petgraph that referenced this pull request Sep 21, 2025
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.
  --
  -->
RaoulLuque pushed a commit to cactusdualcore/petgraph that referenced this pull request Sep 21, 2025
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.
  --
  -->
RaoulLuque pushed a commit to RaoulLuque/petgraph that referenced this pull request Sep 21, 2025
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.
  --
  -->
github-merge-queue bot pushed a commit that referenced this pull request Sep 30, 2025
## 🤖 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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

A-crate Area: Petgraph crate functionality C-feature-accepted Category: A feature request that has been accepted pending implementation C-refactor Category: PR/issue with specific code/suggestions for refactoring S-waiting-on-author Status: Awaiting some action by the PR/Issue author

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants