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 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 (8)

comment:1 Changed 7 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 7 months ago by git

  • Commit set to 82b8482d0f0f9ad32fff0537652d544f3bc6e873

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

82b8482bug fix

comment:3 Changed 7 months ago by dcoudert

can you give an example raising an error ?

comment:4 Changed 7 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 7 months ago by dcoudert

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

comment:6 Changed 7 months ago by gh-rajat1433

  • Description modified (diff)
  • Status changed from new to needs_review

comment:7 Changed 7 months ago by dcoudert

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

  • 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
Note: See TracTickets for help on using tickets.