New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implementation of Floyd-Warshall for all pair shortest distance #27518
Comments
comment:1
I am working on this. I think we should take care of the case when edge_label is not a number (Probably set weight to 1). |
Commit: |
New commits:
|
comment:5
|
comment:6
Does the algorithm only work if given graph has all possible edges defined, Like if I input a Graph with 100 edges and 11 vertices :
But the same algorithm works for 500 edges and 11 vertices:-
Any particular reason? |
comment:7
Well, I think I figured it out. If we work on the original graph (gg) and not in the graph created in line
the problem seems to get fixed. I don't really know what causes the issue in the first place but in general, the above line seems to add to the graph g some edges which are not present in gg. |
comment:8
|
comment:9
The boost implementation of Floyd-Warshall and Johnson algorithm returns only the distances and not the paths. Would it be a good idea to use it and retrieve the paths from the distance values? Personally, I can't think of a way to do this faster than O(V3). |
comment:10
What is your objective: get distances or get paths ? For distances, you can use boost. For paths, this is another story, and you will have to code a specific algorithm. However, I'm not convinced that using Floyd-Warshall is a good idea if you want paths. |
comment:11
The current implementation has the option to also return the shortest paths between every two vertices. My objective is to preserve this feature. Would it be a good idea to reimplement Johnson's algorithm in Cython to be able to do this efficiently? |
comment:12
Unless I'm mistaken, the methods don't return paths but the matrix of predecessors. |
comment:13
Replying to @dcoudert:
But isn't this going to be O(V3)? |
comment:14
It will be O(N.M) with a small constants... |
comment:15
Ok. Here is what I am planning to do in the next couple of days:
Please let me know if there are any problems or pitfalls with what I proposed above. |
comment:16
OK
Have you checked the documentation of method |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:19
It's only the pseudo-code and it must be improved, but it should give a simpler code. So please check what can be done with boost graphs. It might not be so difficult to use, and should lead to much faster code. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:21
Replying to @dcoudert:
Fixed all errors
Changed back to the previous code
I adapted the pseudocode to my implementation. I will do some research on boost graphs and try to come up with a faster implementation using boost interface. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Changed branch from u/gh-giorgosgiapis/weighted_floyd_warshall to public/graphs/27518_floyd_warshall_boost |
comment:57
I have rebased the branch on the last beta version and fixed the merge conflicts. Please check that it's working well. New commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:59
For me this patch is good to go. I'm waiting confirmation from your side. |
comment:60
Replying to @dcoudert:
After some testing everything seems to work as expected so it is indeed good to go. |
Reviewer: David Coudert |
comment:61
Please add your real name in LGTM. |
Author: Georgios Giapitzakis Tzintanos |
comment:63
Docbuild fails, see patchbot |
comment:64
Just to make things clear, that is the failure I see
it looks like a stray space at the start of line 1085 of |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:66
Replying to @kiwifb:
Thank you for the info. Fixed it! |
comment:67
@kiwifb: can you check if it's ok ? I have an issue building the documentation that is not related to this ticket. Thank you. |
comment:68
All tests seem to pass now! |
comment:69
LGTM. |
Changed branch from public/graphs/27518_floyd_warshall_boost to |
Currently sage has implemented Floyd-Warshall algorithm only for graphs with constant edge weight of 1 in cython. Implementation of Floyd warshall algorithm in cython for finding all pair shortest distances(ASAD) can be done. This algorithm can be further improved to find all pair shortest paths(ASAP)(Later).
We can also improve all pair shortest distance algorithm using the technique described in the following paper:-
https://pdfs.semanticscholar.org/568f/58737e752bf831a3e48036cf5205facce769.pdf
Usually complexity for finding ASAD with matrix multiplication comes with large constants that results in slow running time, But the implementation that is described in the paper can faster the running time for algorithm.
CC: @dcoudert
Component: graph theory
Author: Georgios Giapitzakis Tzintanos
Branch/Commit:
dc082bb
Reviewer: David Coudert
Issue created by migration from https://trac.sagemath.org/ticket/27518
The text was updated successfully, but these errors were encountered: