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 gh-rajat1433)

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 gh-rajat1433

  • 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 git

  • Commit set to 82b8482d0f0f9ad32fff0537652d544f3bc6e873

Branch pushed to git repo; I updated commit sha1. New commits:

82b8482bug fix

comment:3 Changed 12 months ago by dcoudert

can you give an example raising an error ?

comment:4 Changed 12 months ago by gh-rajat1433

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 dcoudert

Yes, you must explain what's going on and why is this change needed.

comment:6 Changed 12 months ago by gh-rajat1433

  • Description modified (diff)
  • Status changed from new to needs_review
Note: See TracTickets for help on using tickets.