implement Dijkstra's algorithm for C graphs

[rlm]

As a follow up of #7640.

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

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

[ncohen]

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

[rlm]

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

[rlm]

rebased on 4.3.rc0 + #7640

[rlm]

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.

[ylchapuy]

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

[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

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

[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

[ncohen]

Here is a fixed version :-)

[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

[rlm]

Sorry I missed that mistake! :o

The new patch looks good.