Opened 12 months ago
Last modified 12 months ago
#27669 closed defect
fixing an error in shortest_path in c_graph — at Version 6
Reported by: | gh-rajat1433 | Owned by: | gh-rajat1433 |
---|---|---|---|
Priority: | major | Milestone: | sage-8.8 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | |
Authors: | Rajat Mittal | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | u/gh-rajat1433/27669_fixing_error_in_shortest_paths (Commits) | Commit: | 82b8482d0f0f9ad32fff0537652d544f3bc6e873 |
Dependencies: | Stopgaps: |
Description (last modified by )
The algorithm is behaving as a simple bfs algorithm instead of bidirectional bfs which should explore nodes from both the directions. Following bug is fixed by this ticket: (This is probably a typo as the whole code suggest it is intended to be written for bidirectional bfs)
- next_current.append(v) + next_temporary.append(v)
Change History (6)
comment:1 Changed 12 months ago by
- Branch set to u/gh-rajat1433/27669_fixing_error_in_shortest_paths
- Description modified (diff)
- Owner changed from (none) to gh-rajat1433
comment:2 Changed 12 months ago by
- Commit set to 82b8482d0f0f9ad32fff0537652d544f3bc6e873
comment:3 Changed 12 months ago by
can you give an example raising an error ?
comment:4 Changed 12 months ago by
It will not give wrong results as the next_current list will keep on populating till we reach the target node in bfs but the problem is it will not be the bidirectional bfs as claimed by this method. I used the word broke in ticket description because I was doing some changes and it broke due to this bug. Maybe I will need to modify the ticket description.
comment:5 Changed 12 months ago by
Yes, you must explain what's going on and why is this change needed.
comment:6 Changed 12 months ago by
- Description modified (diff)
- Status changed from new to needs_review
Branch pushed to git repo; I updated commit sha1. New commits:
bug fix