#7673 closed defect (fixed)
implement Dijkstra's algorithm for C graphs
Reported by: | rlm | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3 |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | sage-4.3.rc1 |
Authors: | Nathann Cohen | Reviewers: | Robert Miller, Yann Laigle-Chapuy |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As a follow up of #7640.
Attachments (2)
Change History (18)
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
I think these are implemented in http://trac.sagemath.org/sage_trac/attachment/ticket/6452/trac_6452-ring-codes.patch However, the patch was rejected due to memory errors. The author has not fixed them yet.
Please be my guest:-)
comment:3 Changed 10 years ago by
- Status changed from new to needs_review
Here is one version using heapq from Python.... Once we will have a good Cython implementation of heaps, it will take something like 20 seconds to update it ! :-)
comment:4 follow-up: ↓ 5 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:5 in reply to: ↑ 4 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:6 Changed 10 years ago by
- Milestone changed from sage-4.3.1 to sage-4.3
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:7 Changed 10 years ago by
- Milestone changed from sage-4.3 to sage-4.3.1
comment:8 Changed 10 years ago by
- Status changed from positive_review to needs_work
Hi, I'm sorry, but this implementation is buggy...
sage: G = Graph() sage: G.add_edge(0,1,9) sage: G.add_edge(0,2,8) sage: G.add_edge(1,2,7) sage: G.shortest_path(0,1,by_weight=True) [0, 1] sage: G.shortest_path_length(0,1,by_weight=True) 9 sage: Gc = G.copy(implementation='c_graph') sage: Gc.shortest_path(0,1,by_weight=True) [0, 2, 1] sage: Gc.shortest_path_length(0,1,by_weight=True) 15
comment:9 follow-ups: ↓ 10 ↓ 11 Changed 10 years ago by
Clearly, it is !! Thank you for taking a lot at it :-)
Well, the only bugfix I can think about is to keep in memory the vertex v such that dist_y[v] + dist_x[v] is minimal, and only build the path when the neighborhoods of x and y at distance 2*(dist_y[v] + dist_x[v]) have been explored. It clearly fixes your counter-example, and I think it should solve all others, but I woud be glad to write a nicer solution... Any idea ? :-)
Thank you very much again ! :-)
Nathann
comment:10 in reply to: ↑ 9 Changed 10 years ago by
I don't know if it's nicer, but did you look at how it's done in networkx?
Replying to ncohen:
I woud be glad to write a nicer solution... Any idea ? :-)
comment:11 in reply to: ↑ 9 Changed 10 years ago by
Replying to ncohen:
Clearly, it is !! Thank you for taking a lot at it :-)
Well, the only bugfix I can think about is to keep in memory the vertex v such that dist_y[v] + dist_x[v] is minimal, and only build the path when the neighborhoods of x and y at distance 2*(dist_y[v] + dist_x[v]) have been explored. It clearly fixes your counter-example, and I think it
Maybe this is related to the "piority queue" in Demaine's descrition of the algorithm in
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/651C0FC9-55D1-4404-A801-A9D0392A668C/0/lec17.pdf
at
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm
should solve all others, but I woud be glad to write a nicer solution... Any idea ? :-)
Thank you very much again ! :-)
Nathann
comment:12 Changed 10 years ago by
- Status changed from needs_work to needs_review
Here is a fixed version :-)
Changed 10 years ago by
comment:13 Changed 10 years ago by
I do not think so, this bug just came from the fact that this version of dijkstra is bidirectional, and I wrongly assumed that as in the simple version of it, the first path found was the correct path. Obviously ( see your example ) it is not, and I expect this version of the algorithm to be correct :-)
Nathann
comment:14 Changed 10 years ago by
- Reviewers changed from Robert Miller to Robert Miller, Yann Laigle-Chapuy
- Status changed from needs_review to positive_review
Sorry I missed that mistake! :o
The new patch looks good.
comment:15 Changed 10 years ago by
- Merged in set to sage-4.3.rc1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:16 Changed 10 years ago by
- Milestone changed from sage-4.3.1 to sage-4.3
To write it I could need an implementation of heaps in Cython ( I would need top keep a list sorted through the execution of the algorithm, with insertion/deletions ). If anybody knows about such a thing, please tell me :-)