Opened 7 months ago
Closed 7 months ago
#27669 closed defect (fixed)
fixing an error in shortest_path in c_graph
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: | 82b8482 (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 (8)
comment:1 Changed 7 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 7 months ago by
- Commit set to 82b8482d0f0f9ad32fff0537652d544f3bc6e873
comment:3 Changed 7 months ago by
can you give an example raising an error ?
comment:4 Changed 7 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 7 months ago by
Yes, you must explain what's going on and why is this change needed.
comment:6 Changed 7 months ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:7 Changed 7 months ago by
- Status changed from needs_review to positive_review
Another issue is that list next_current
is modified inside a for u in next_current:
loop (see copy/paste below). Clearly not good. So I agree with this change.
for u in next_current: if out == 1: neighbors = self._cg.out_neighbors(u) elif self._cg_rev is not None: # Sparse neighbors = self._cg_rev.out_neighbors(u) else: # Dense neighbors = self._cg.in_neighbors(u) for v in neighbors: # If the neighbor is new, updates the distances and adds # to the list. if v not in dist_current: dist_current[v] = dist_current[u] + 1 if not distance_flag: pred_current[v] = u next_current.append(v)
comment:8 Changed 7 months ago by
- Branch changed from u/gh-rajat1433/27669_fixing_error_in_shortest_paths to 82b8482d0f0f9ad32fff0537652d544f3bc6e873
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
bug fix