Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#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)

trac_7673.patch (5.2 KB) - added by rlm 9 years ago.
rebased on 4.3.rc0 + #7640
trac_7673.2.patch (6.2 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 9 years ago by ncohen

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 :-)

comment:2 Changed 9 years ago by wdj

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 9 years ago by ncohen

  • 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: Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work

This is going to conflict with the patch at #7640. Can you rebase this patch on 4.3.rc0 + #7640?

Changed 9 years ago by rlm

rebased on 4.3.rc0 + #7640

comment:5 in reply to: ↑ 4 Changed 9 years ago by rlm

  • Status changed from needs_work to needs_review

Replying to rlm:

This is going to conflict with the patch at #7640. Can you rebase this patch on 4.3.rc0 + #7640?

OK, I've posted a new patch.

comment:6 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • 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 9 years ago by rlm

  • Milestone changed from sage-4.3 to sage-4.3.1

comment:8 Changed 9 years ago by ylchapuy

  • 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: Changed 9 years ago by 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 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 9 years ago by ylchapuy

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 9 years ago by wdj

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 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Here is a fixed version :-)

Changed 9 years ago by ncohen

comment:13 Changed 9 years ago by ncohen

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 9 years ago by rlm

  • 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 9 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:16 Changed 9 years ago by rlm

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.