Opened 3 years ago

Closed 3 years ago

#28221 closed enhancement (fixed)

minor improvement in bidirectional_dijkstra

Reported by: Rajat Mittal Owned by:
Priority: major Milestone: sage-8.9
Component: graph theory Keywords: gsoc19
Cc: David Coudert Merged in:
Authors: Rajat Mittal Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: c9b04a1 (Commits, GitHub, GitLab) Commit: c9b04a141b22ca074f77ccc36ecd80235d594fab
Dependencies: Stopgaps:

Status badges

Description

While reading some cython codes I came across this code and found a variable can be converted to cython. Its very minor but I thought it must be fixed.

Change History (22)

comment:1 Changed 3 years ago by Rajat Mittal

Branch: public/graphs/28221_bidirectiona_dijkstra

comment:2 Changed 3 years ago by git

Commit: 8f7f4a4edc4cccf2772e9f3d07c79e525946b66c

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

8f7f4a4added cython variable

comment:3 Changed 3 years ago by Rajat Mittal

Status: newneeds_review

comment:4 Changed 3 years ago by Rajat Mittal

I think it can be improved further as the distance can be float so

cdef int distance

cdef priority_queue[pair[pair[int, int], pair[int, int]]] pq

can be changed to

cdef double distance

cdef priority_queue[pair[pair[double, int], pair[int, int]]] pq

waiting for your thoughts on it....

comment:5 Changed 3 years ago by David Coudert

Try to do the change and check if it passes all doctests.

comment:6 Changed 3 years ago by git

Commit: 8f7f4a4edc4cccf2772e9f3d07c79e525946b66c45267e50b0972d244fa90d3dcacda183363138ef

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

45267e5fixed bug and added doctest!

comment:7 Changed 3 years ago by David Coudert

Status: needs_reviewneeds_work

You should sometimes run ./sage -btp --long src/sage/graphs/

sage -t src/sage/graphs/generic_graph.py
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 14446, in sage.graphs.generic_graph.GenericGraph.distance
Failed example:
    G.distance(0, 3, by_weight=True)
Expected:
    3
Got:
    3.0
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 16362, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    D.shortest_path_length(4, 9, algorithm='Dijkstra_Bid')
Expected:
    5
Got:
    5.0
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 16375, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    G.shortest_path_length(0, 3, by_weight=True)
Expected:
    3
Got:
    3.0
**********************************************************************
File "src/sage/graphs/generic_graph.py", line 16397, in sage.graphs.generic_graph.GenericGraph.?
Failed example:
    G.shortest_path_length(0, 2, by_weight=True)
Expected:
    2
Got:
    2.0
**********************************************************************
2 items had failures:
   3 of 858 in sage.graphs.generic_graph.GenericGraph.?
   1 of  10 in sage.graphs.generic_graph.GenericGraph.distance
    [3470 tests, 4 failures, 50.62 s]

Can you check for instance in the boost backend for a method to turn the result to int when possible ? It would be a smarter solution than just changing the doctests.

comment:8 Changed 3 years ago by git

Commit: 45267e50b0972d244fa90d3dcacda183363138effb0c847ff8d6392e6c1462da4ae690df663c25e0

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

fb0c847fixed code to convert to int

comment:9 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:10 Changed 3 years ago by Rajat Mittal

Priority: minormajor

comment:11 Changed 3 years ago by David Coudert

this might be better

sage: from sage.rings.integer_ring import ZZ
sage: 3.0 in ZZ
True
sage: 3.1 in ZZ
False

I don't know if we have a faster (cython level) method.

comment:12 Changed 3 years ago by git

Commit: fb0c847ff8d6392e6c1462da4ae690df663c25e0c590c2f27fafce9f6028d8c915af459061b634b1

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

c590c2fimproved integer check

comment:13 Changed 3 years ago by David Coudert

Status: needs_reviewpositive_review

LGTM

comment:14 Changed 3 years ago by Volker Braun

Status: positive_reviewneeds_work

Merge conflict

comment:15 Changed 3 years ago by git

Commit: c590c2f27fafce9f6028d8c915af459061b634b1c9b04a141b22ca074f77ccc36ecd80235d594fab

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

c9b04a1trac #28221 merged with 8.9beta4

comment:16 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:17 Changed 3 years ago by David Coudert

Status: needs_reviewpositive_review

LGTM.

comment:18 Changed 3 years ago by Volker Braun

Status: positive_reviewneeds_work

Author name is missing

comment:19 Changed 3 years ago by Rajat Mittal

Authors: Rajat Mittal
Status: needs_workneeds_review

comment:20 Changed 3 years ago by David Coudert

Status: needs_reviewpositive_review

OK

comment:21 Changed 3 years ago by David Coudert

Keywords: gsoc19 added

comment:22 Changed 3 years ago by Volker Braun

Branch: public/graphs/28221_bidirectiona_dijkstrac9b04a141b22ca074f77ccc36ecd80235d594fab
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.