implement Dijkstra's algorithm for C graphs

[rlmill]

As a follow up of #7640.

CC: @nathanncohen

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller, Yann Laigle-Chapuy

Merged: sage-4.3.rc1

Issue created by migration from https://trac.sagemath.org/ticket/7673

[nathanncohen]

comment:1

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

[wdjoyner]

comment:2

I think these are implemented in
https://github.com/sagemath/sage-prod/files/10645381/trac_6452-ring-codes.patch.gz
However, the patch was rejected due to memory errors. The author has not fixed them
yet.

Please be my guest:-)

[nathanncohen]

comment:3

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

[rlmill]

comment:4

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

[rlmill]

rebased on 4.3.rc0 + #7640

[rlmill]

comment:5

Attachment: trac_7673.patch.gz

Replying to @rlmill:

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.

[rlmill]

Author: Nathann Cohen

[rlmill]

Reviewer: Robert Miller

[sagetrac-ylchapuy]

comment:8

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

[nathanncohen]

comment:9

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

[sagetrac-ylchapuy]

comment:10

I don't know if it's nicer, but did you look at how it's done in networkx?

Replying to @nathanncohen:

I woud be glad to write a nicer solution... Any idea ? :-)

[wdjoyner]

comment:11

Replying to @nathanncohen:

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

[nathanncohen]

comment:12

Here is a fixed version :-)

[nathanncohen]

comment:13

Attachment: trac_7673.2.patch.gz

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

[rlmill]

Changed reviewer from Robert Miller to Robert Miller, Yann Laigle-Chapuy

[rlmill]

comment:14

Sorry I missed that mistake! :o

The new patch looks good.

[mwhansen]

Merged: sage-4.3.rc1