Opened 2 years ago
Closed 22 months ago
#27518 closed enhancement (fixed)
Implementation of Floyd-Warshall for all pair shortest distance
Reported by: | gh-Hrishabh-yadav | Owned by: | gh-giorgosgiapis |
---|---|---|---|
Priority: | major | Milestone: | sage-8.8 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | |
Authors: | Georgios Giapitzakis Tzintanos | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | dc082bb (Commits, GitHub, GitLab) | Commit: | dc082bb5e6bee3644615fb5cbc62a44d7a52ed6a |
Dependencies: | Stopgaps: |
Description
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.
Change History (70)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
- Branch set to u/gh-giorgosgiapis/weighted_floyd_warshall
comment:3 Changed 2 years ago by
- Commit set to ffcea9e1772dc81bfae6373c8b69bbc481514a4c
- Status changed from new to needs_review
New commits:
ffcea9e | Modified Floyd-Warshall to work with weighted graphs with non-negative integer edge weights.
|
comment:4 Changed 2 years ago by
- Owner changed from (none) to gh-giorgosgiapis
comment:5 Changed 2 years ago by
- The usage of edge weights is not fully unified in the graph module. However, many methods have as input parameter
wfunction
, a function that inputs an edge and outputs a number. You should consider adding this parameter as input of the method.
- There is an implementation of Floyd-Warshall algorithm in
boost
https://www.boost.org/doc/libs/1_69_0/libs/graph/doc/floyd_warshall_shortest.html
and we have an interface with boost
src/sage/graphs/base/boost_*
.
So you should first expose the boost implementation in Sagemath.
- Moreover, Johnson algorithm is considered faster for sparse graphs (and most of the graphs are sparse).
- we can use the implementation of boost:
'Johnson_Boost'
- we can also use the implementation of
igraph
(an optional package), although not directly exposed. In fact methodshortest_paths
ofigraph
call Johnson algorithm and not Floyd-Warshall for the reason explained here: https://lists.nongnu.org/archive/html/igraph-help/2009-06/msg00029.html
- we can use the implementation of boost:
when
igraph
is installed, we can doH = G.igraph_graph()
and thenH.shortest_paths()
with appropriate parameters.
comment:6 Changed 2 years ago by
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 :
sage: ....: from sage.graphs.distances_all_pairs import floyd_warshall ....: G= Graph() ....: G.allow_multiple_edges(True) ....: G.allow_loops(True) ....: G.weighted(True) ....: for i in range(100): ....: u=randint(0,10) ....: v=randint(0,10) ....: l=randint(0,1000) ....: G.add_edge(u,v,l) ....: G.add_edge(v,u,l) ....: ....: print(floyd_warshall(G,paths=False,distances=True)) ....: ....: --------------------------------------------------------------------------- LookupError Traceback (most recent call last) <ipython-input-13-c620edb96b9c> in <module>() 12 G.add_edge(v,u,l) 13 ---> 14 print(floyd_warshall(G,paths=False,distances=True)) 15 16 /home/hrishabh/sage/local/lib/python2.7/site-packages/sage/graphs/distances_all_pairs.pyx in sage.graphs.distances_all_pairs.floyd_warshall (build/cythonized/sage/graphs/distances_all_pairs.c:15993)() 1623 for u_int in g.out_neighbors(v_int): 1624 if gg.weighted() == True: -> 1625 label = str(gg.edge_label(v_int, u_int)) 1626 try: 1627 weight = int(label) /home/hrishabh/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in edge_label(self, u, v) 11310 True 11311 """ > 11312 return self._backend.get_edge_label(u,v) 11313 11314 def edge_labels(self): /home/hrishabh/sage/local/lib/python2.7/site-packages/sage/graphs/base/sparse_graph.pyx in sage.graphs.base.sparse_graph.SparseGraphBackend.get_edge_label (build/cythonized/sage/graphs/base/sparse_graph.c:19894)() 1643 cdef int v_int = self.get_vertex(v) 1644 if not (<SparseGraph>self._cg).has_arc_unsafe(u_int, v_int): -> 1645 raise LookupError("({0}, {1}) is not an edge of the graph.".format(repr(u),repr(v))) 1646 if self.multiple_edges(None): 1647 return [self.edge_labels[l_int] if l_int != 0 else None LookupError: (1, 2) is not an edge of the graph.
But the same algorithm works for 500 edges and 11 vertices:-
....: from sage.graphs.distances_all_pairs import floyd_warshall ....: G= Graph() ....: G.allow_multiple_edges(True) ....: G.allow_loops(True) ....: G.weighted(True) ....: for i in range(500): ....: u=randint(0,10) ....: v=randint(0,10) ....: l=randint(0,1000) ....: G.add_edge(u,v,l) ....: G.add_edge(v,u,l) ....: ....: print(floyd_warshall(G,paths=False,distances=True)) ....: ....: {0: {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}, 1: {0: 1, 1: 0, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}, 2: {0: 1, 1: 1, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}, 3: {0: 1, 1: 1, 2: 1, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}, 4: {0: 1, 1: 1, 2: 1, 3: 1, 4: 0, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}, 5: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 0, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1}, 6: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 0, 7: 1, 8: 1, 9: 1, 10: 1}, 7: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 0, 8: 1, 9: 1, 10: 1}, 8: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 0, 9: 1, 10: 1}, 9: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 0, 10: 1}, 10: {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 0}}
Any particular reason?
comment:7 follow-up: ↓ 8 Changed 2 years ago by
Well, I think I figured it out. If we work on the original graph (gg) and not in the graph created in line
cdef CGraph g = <CGraph> gg._backend.c_graph()[0]
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 in reply to: ↑ 7 Changed 2 years ago by
cdef CGraph g = <CGraph> gg._backend.c_graph()[0]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.
g
is in underlying backend graph format. This is a different format than Graph
in which nodes and edges have different labels than in the gg
. Although you can make much more efficient code using the backend directly, don't start playing with this if you are not an advanced user !
comment:9 Changed 2 years ago by
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 Changed 2 years ago by
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 Changed 2 years ago by
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 follow-up: ↓ 13 Changed 2 years ago by
Unless I'm mistaken, the methods don't return paths but the matrix of predecessors.
Given a matrix (or dict of dict) of distances, you can find the predecessors. For a source vertex s, for a vertex v, you find the neighbor u of v that is on a shortest s-v path by checking which vertex u is such that d(s, u) + w(u, v) = d(s, v)
. So it should be easy to add the functionality to the method implemented with boost.
comment:13 in reply to: ↑ 12 Changed 2 years ago by
Replying to dcoudert:
Unless I'm mistaken, the methods don't return paths but the matrix of predecessors. Given a matrix (or dict of dict) of distances, you can find the predecessors. For a source vertex s, for a vertex v, you find the neighbor u of v that is on a shortest s-v path by checking which vertex u is such that
d(s, u) + w(u, v) = d(s, v)
. So it should be easy to add the functionality to the method implemented with boost.
But isn't this going to be O(V3)?
comment:14 Changed 2 years ago by
It will be O(N.M) with a small constants...
comment:15 follow-up: ↓ 16 Changed 2 years ago by
Ok. Here is what I am planning to do in the next couple of days:
1) Expose the boost implementation of Floyd-Warshall in Sagemath
2) Modify johnson_shortest_paths() to return the predecessors matrix
3) Create a new method for all pairs shortest paths where the user will be able to select the algorithm used (like in shortest_paths method in src/sage/graphs/base/boost_graph.pyx
).
Please let me know if there are any problems or pitfalls with what I proposed above.
comment:16 in reply to: ↑ 15 Changed 2 years ago by
1) Expose the boost implementation of Floyd-Warshall in Sagemath
2) Modify johnson_shortest_paths() to return the predecessors matrix
OK
3) Create a new method for all pairs shortest paths where the user will be able to select the algorithm used (like in shortest_paths method in
src/sage/graphs/base/boost_graph.pyx
).
Have you checked the documentation of method shortest_path_all_pairs
? it already returns distances and predecessors matrix for different algorithms.
comment:17 Changed 2 years ago by
- Commit changed from ffcea9e1772dc81bfae6373c8b69bbc481514a4c to ef91486fa6982a5c23db3c62459cc2811d039c62
Branch pushed to git repo; I updated commit sha1. New commits:
5aceae0 | Added predecessors support in boost johnson_shortest_paths method
|
e87b06b | Merge branch 'u/gh-giorgosgiapis/weighted_floyd_warshall' of git://trac.sagemath.org/sage into johnson_pred
|
ef91486 | Added predecessors support in boost johnson_shortest_paths method
|
comment:18 Changed 2 years ago by
- Commit changed from ef91486fa6982a5c23db3c62459cc2811d039c62 to 41358f92e6034b50c720f608e3229dc36111ec4e
Branch pushed to git repo; I updated commit sha1. New commits:
41358f9 | Fixed minor issues
|
comment:19 follow-up: ↓ 21 Changed 2 years ago by
- please ensure that comments and documentation are in 80 column modes. See the developer manual
- for building the distance dict, why not using the previous code ?
dist = {int_to_v[v]: {int_to_v[w]: correct_type(result[v][w]) for w in range(N) if result[v][w] != sys.float_info.max} for v in range(N)}
- for building the predecessor dict, it's a pitty not using the boost graph that has already been build and that contains the correct edge weights. I agree it's much more complicated and requires to extend
boost_interface.cpp
to expose other methods in order to iterate over weighted edges.
Also, the pseudo code I have in mind is more like
for i, j, w in g.edges(): for k in range(N): if result[k][j] == result[k][i] + w: pred[k][j] = i if not directed and result[k][i] == result[k][j] + w: pred[k][i] = j
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.
comment:20 Changed 2 years ago by
- Commit changed from 41358f92e6034b50c720f608e3229dc36111ec4e to 8e8799d9799ca2e915b65a4fd5b5e6bae663c04f
Branch pushed to git repo; I updated commit sha1. New commits:
8e8799d | Fixed comments, documentation and code for predecessors
|
comment:21 in reply to: ↑ 19 Changed 2 years ago by
Replying to dcoudert:
- please ensure that comments and documentation are in 80 column modes. See the developer manual
Fixed all errors
- for building the distance dict, why not using the previous code ?
dist = {int_to_v[v]: {int_to_v[w]: correct_type(result[v][w]) for w in range(N) if result[v][w] != sys.float_info.max} for v in range(N)}
Changed back to the previous code
Also, the pseudo code I have in mind is more like
for i, j, w in g.edges(): for k in range(N): if result[k][j] == result[k][i] + w: pred[k][j] = i if not directed and result[k][i] == result[k][j] + w: pred[k][i] = jIt's only the pseudo-code and it must be improved, but it should give a simpler 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.
comment:22 Changed 2 years ago by
Some comments on the current code. Of course, a version directly using boost could be better.
- add an empty line between each input parameter, e.g., before
+ - ``predecessors`` -- boolean (default: ``False``); whether to return the
- you can type some variables. For instance
- dist = {} - pred = {} + cdef dict dist = {} + cdef dict pred = {}
- you can improve the alignment (although I'm not fully sure of the correct pep8 for this one)
- dist = {int_to_v[v]: {int_to_v[w]: correct_type(result[v][w]) - for w in range(N) if result[v][w] != sys.float_info.max} - for v in range(N)} + dist = {int_to_v[v]: {int_to_v[w]: correct_type(result[v][w]) + for w in range(N) if result[v][w] != sys.float_info.max} + for v in range(N)}
- you could define integer variables for
v_to_int[u]
,v_to_int[v]
- add a space after
#
in+ #dst is the weight of the edge (e[0], e[1])
- no
;
at the end of+ continue;
- use 2 lines for
+ if g.is_directed(): continue
comment:23 Changed 2 years ago by
- Commit changed from 8e8799d9799ca2e915b65a4fd5b5e6bae663c04f to b10779ff182689113014532c7820e409db736dbb
Branch pushed to git repo; I updated commit sha1. New commits:
b10779f | Fixed minor code issues
|
comment:24 Changed 2 years ago by
Fixed. I will now expose boost Floyd Warshall algorithm implementation to SageMath and then try to use boost to speed up both these methods.
comment:25 Changed 2 years ago by
- Commit changed from b10779ff182689113014532c7820e409db736dbb to 1d65ba196676ee61276d0ffb33e21dcbea8a02a8
Branch pushed to git repo; I updated commit sha1. New commits:
1d65ba1 | Added Floyd-Warshall boost implementation
|
comment:26 follow-up: ↓ 27 Changed 2 years ago by
I think the main difficulty with boost is to understand how to iterate over weighted edges... and possibly also over vertices.
comment:27 in reply to: ↑ 26 Changed 2 years ago by
Replying to dcoudert:
I think the main difficulty with boost is to understand how to iterate over weighted edges... and possibly also over vertices.
This is true. That's why I finished with everything else so as to spend some time working just on this one.
comment:28 follow-up: ↓ 31 Changed 2 years ago by
can you:
- ensure that comments and documentaiton are aligned in 80 columns mode. Not the case in Floyd Warshall at least
- avoid double empty lines when only 1 is sufficient
- add
cdef int u_int, v_int
in both methods
- either find a way to iterate over the edges of the boost graph as already discussed, or at least use
for e in g.edge_iterator():
instead offor e in g.edges():
. Indeed,.edges()
sorts edges by default and we don't need that here.
comment:29 Changed 2 years ago by
- Commit changed from 1d65ba196676ee61276d0ffb33e21dcbea8a02a8 to 2333057647264bfff1966030a34082c42b9b126f
Branch pushed to git repo; I updated commit sha1. New commits:
2333057 | Fixed minor issues
|
comment:30 Changed 2 years ago by
- Commit changed from 2333057647264bfff1966030a34082c42b9b126f to b76dd9bd9409c3fb18b48ef006b869268cd6f81c
Branch pushed to git repo; I updated commit sha1. New commits:
b76dd9b | Fixed comments and documentation
|
comment:31 in reply to: ↑ 28 Changed 2 years ago by
Replying to dcoudert:
can you:
- ensure that comments and documentaiton are aligned in 80 columns mode. Not the case in Floyd Warshall at least
- avoid double empty lines when only 1 is sufficient
- add
cdef int u_int, v_int
in both methods
- either find a way to iterate over the edges of the boost graph as already discussed, or at least use
for e in g.edge_iterator():
instead offor e in g.edges():
. Indeed,.edges()
sorts edges by default and we don't need that here.
I think I fixed everything. If you find anything wrong please let me know.
comment:32 Changed 2 years ago by
- this statement is incorrect as edge weights are not always 1. Better to say that
w
is a predecessor ofv
on a shortest path fromu
tov
.+ `v` and ``predecessors[u][v]`` denotes a neighbor `w` of `v` such that + `dist(u,v) = 1 + dist(u,w)`.
- pep8
- pred = {v : {v : None} for v in g} + pred = {v: {v: None} for v in g}
- why are you using
cpdef
. Any particular reason for that ?cdef
might be enough here, no ?
- no need for
dst = 0
as you assign another value to dst just after
- To avoid code ducplication, you could have a method that, given the graph, the
result
, and all needed parameters, return the predecessor matrix.
comment:33 Changed 2 years ago by
- Commit changed from b76dd9bd9409c3fb18b48ef006b869268cd6f81c to 76bfdaa5a47fc65bb99600201258c8b3cd9dc08a
Branch pushed to git repo; I updated commit sha1. New commits:
76bfdaa | Fixed documentation and added new method
|
comment:34 follow-up: ↓ 36 Changed 2 years ago by
get_predecessors
:
- you can shorten the text like
- Given the shortest distances between all pairs of vertices in a graph return - the predecessors matrix. + Return the predecessor matrix from the distance matrix of the graph.
- I propose to simplify the weight function definition and to force to give one. So for the text:
- ``weight_function`` -- function; a function that takes as input an edge ``(u, v, l)`` and outputs its weight. If ``weight_function`` is ``None`` and the graph is weighted, then use the edge weight. Otherwise all edges have weight 1.
- output
A dictionary of dictionaries ``pred`` such that ``pred[u][v]`` indicates the predecessor of `v` in the shortest path from `u` to `v`.
- don't do
import sys
inside the loop. If you need it, do that before the loop.
johnson_shortest_paths
:
- improvement
- `v` and ``predecessors[u][v]`` denotes a neighbor `w` of `v` such that - it lies on the shortest path from `u` to `v`. + `v` and ``predecessors[u][v]`` indicates the predecessor of `w` on a + shortest path from `u` to `v`.
floyd_warshall_shortest_paths
:
- avoid double blank lines
- output: same comment than above
In generic_graph.py
, method shortest_path_all_pairs
: you must update the output section by removing the note on Johnson algorithm.
Have you tried to use the boost graph to iterate over edges, get edge weights, etc. ?
It's a pity to use the weight function in get_predecessors
when all weights with correct value are recorded on the edges of the boost graph.
comment:35 Changed 2 years ago by
- Commit changed from 76bfdaa5a47fc65bb99600201258c8b3cd9dc08a to 533545d45da6ee0e4dd9969eb83fe590a3d28e5d
Branch pushed to git repo; I updated commit sha1. New commits:
533545d | Improved code and documentation
|
comment:36 in reply to: ↑ 34 Changed 2 years ago by
Fixed everything. Tomorrow I will try to use boost edge iterator in get_predecessors
.
comment:37 Changed 2 years ago by
- Commit changed from 533545d45da6ee0e4dd9969eb83fe590a3d28e5d to 328e02b05ced4164574de385838584400c6f44cd
Branch pushed to git repo; I updated commit sha1. New commits:
328e02b | Fixed documentation on generic_graph.py
|
comment:38 follow-up: ↓ 39 Changed 23 months ago by
any progress on using boost edge iterator ?
in your last commit, you remove the empty line before .. NOTE::
. Please put it back.
comment:39 in reply to: ↑ 38 Changed 23 months ago by
Replying to dcoudert:
any progress on using boost edge iterator ?
in your last commit, you remove the empty line before
.. NOTE::
. Please put it back.
I'm working on it. I will probably have it ready in the next 3-4 days.
comment:40 Changed 23 months ago by
- Commit changed from 328e02b05ced4164574de385838584400c6f44cd to b68078a91af0db8906264be3154c0ab81f60922a
Branch pushed to git repo; I updated commit sha1. New commits:
b68078a | get_predecessors now uses boost graph
|
comment:41 Changed 23 months ago by
I am sorry for the delay but I think I fixed it. Now get_predecessors
uses boost edge iterator. Please let me know if there is anything else that needs to be done.
comment:42 follow-up: ↓ 44 Changed 23 months ago by
Good news !
Please check that it's working well for directed and undirected graphs (add appropriate doctests). You might have a type problem when calling get_predecessor
.
comment:43 Changed 23 months ago by
- Commit changed from b68078a91af0db8906264be3154c0ab81f60922a to 1754628b6123d33f61026a5013fea25169d93201
Branch pushed to git repo; I updated commit sha1. New commits:
1754628 | Fixed type issues
|
comment:44 in reply to: ↑ 42 Changed 23 months ago by
Replying to dcoudert:
Good news !
Please check that it's working well for directed and undirected graphs (add appropriate doctests). You might have a type problem when calling
get_predecessor
.
Running some tests seem to produce the right answer. I did, however, pass the correct edge type to get_predecessors
and cast all edge weights to that type.
New commits:
1754628 | Fixed type issues
|
comment:45 Changed 23 months ago by
in method get_predecessors
:
int_to_v
is a list, so please update the description of input parameters and do:- pred = {int_to_v[i]: {int_to_v[i]: None} for i in range(0, N)} + cdef dict pred = {v: {v: None} for v in int_to_v}
in floyd_warshall_shortest_paths
- ensure that all comments are in 80 columns mode
- in the call
pred = get_predecessors(g_boost_dir, result, int_to_v, directed=True, weight_type=correct_type)
, there is no need fordirected=
andweight_type=
as these parameters are not optional
comment:46 Changed 23 months ago by
- Commit changed from 1754628b6123d33f61026a5013fea25169d93201 to dc8a9e1cdd2e7e39b0e39b946ad4db960097b304
Branch pushed to git repo; I updated commit sha1. New commits:
dc8a9e1 | Fixed minor issues
|
comment:47 Changed 22 months ago by
don't forget to ensure that comments and documentation are in 80 columns mode. For instance, this is not
+ - ``distances`` -- boolean (default: ``True``); whether to return the dictionary
comment:48 Changed 22 months ago by
- Commit changed from dc8a9e1cdd2e7e39b0e39b946ad4db960097b304 to 495d610aff176350dc5bcddde123482cba7da494
Branch pushed to git repo; I updated commit sha1. New commits:
495d610 | Comments and documentation are in 80 columns mode
|
comment:49 follow-up: ↓ 50 Changed 22 months ago by
in johnson_shortest_paths
too ;)
comment:50 in reply to: ↑ 49 Changed 22 months ago by
Replying to dcoudert:
in
johnson_shortest_paths
too ;)
Are you sure there is a problem with johnson_shortest_paths
? (I think I fixed everything in the previous commit)
comment:51 follow-up: ↓ 53 Changed 22 months ago by
I think this line for instance has length more that 80
+ ``(distances, predecessors)`` where ``distance[u][v]`` denotes the distance of
comment:52 Changed 22 months ago by
- Commit changed from 495d610aff176350dc5bcddde123482cba7da494 to e26d63d525a46211ee56d453df0768cab4099dba
Branch pushed to git repo; I updated commit sha1. New commits:
e26d63d | Fixed issues with comments and documentation
|
comment:53 in reply to: ↑ 51 Changed 22 months ago by
Replying to dcoudert:
I think this line for instance has length more that 80
+ ``(distances, predecessors)`` where ``distance[u][v]`` denotes the distance of
You are right. Everything should be ok now (I think).
comment:54 Changed 22 months ago by
You still have to expose methods floyd_warshall_shortest_paths
and johnson_shortest_paths
from method shortest_path_all_pairs
of generic_graph.py
.
Don't forget to add required doctests.
comment:55 Changed 22 months ago by
- Commit changed from e26d63d525a46211ee56d453df0768cab4099dba to ee720d465143f5143281edf88698ed8e69310545
Branch pushed to git repo; I updated commit sha1. New commits:
ee720d4 | Modified shortest_path_all_pairs method in generic_graph.py
|
comment:56 Changed 22 months ago by
- Commit changed from ee720d465143f5143281edf88698ed8e69310545 to ef38d911514f201c7204d42f919ad6442ad505e3
Branch pushed to git repo; I updated commit sha1. New commits:
ef38d91 | Fixed typo
|
comment:57 Changed 22 months ago by
- Branch changed from u/gh-giorgosgiapis/weighted_floyd_warshall to public/graphs/27518_floyd_warshall_boost
- Commit changed from ef38d911514f201c7204d42f919ad6442ad505e3 to 803af4ef7e33181484e7472a3a71bed96e65bf2e
I have rebased the branch on the last beta version and fixed the merge conflicts.
I pushed a new branch. It is in public/
, so you can access and modify it.
Please check that it's working well.
New commits:
803af4e | trac #27518: fix merge conflict with 8.8.beta4
|
comment:58 Changed 22 months ago by
- Commit changed from 803af4ef7e33181484e7472a3a71bed96e65bf2e to 2a26a6594180d69be8e784d6c2948e443407af04
Branch pushed to git repo; I updated commit sha1. New commits:
2a26a65 | trac #27518: alignement
|
comment:59 follow-up: ↓ 60 Changed 22 months ago by
For me this patch is good to go. I'm waiting confirmation from your side.
comment:60 in reply to: ↑ 59 Changed 22 months ago by
Replying to dcoudert:
For me this patch is good to go. I'm waiting confirmation from your side.
After some testing everything seems to work as expected so it is indeed good to go.
comment:61 Changed 22 months ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
Please add your real name in Authors
field.
LGTM.
comment:62 Changed 22 months ago by
comment:63 Changed 22 months ago by
- Status changed from positive_review to needs_work
Docbuild fails, see patchbot
comment:64 follow-up: ↓ 66 Changed 22 months ago by
Just to make things clear, that is the failure I see
Error building the documentation. multiprocessing.pool.RemoteTraceback: """ Traceback (most recent call last): File "/usr/lib/python3.7/multiprocessing/pool.py", line 121, in worker result = (True, func(*args, **kwds)) File "/usr/lib/python3.7/multiprocessing/pool.py", line 44, in mapstar return list(map(*args)) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 79, in build_ref_doc getattr(ReferenceSubBuilder(doc, lang), format)(*args, **kwds) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 761, in _wrapper getattr(DocBuilder, build_type)(self, *args, **kwds) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 133, in f runsphinx() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/sphinxbuild.py", line 317, in runsphinx sys.stderr.raise_errors() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/sphinxbuild.py", line 252, in raise_errors raise OSError(self._error) OSError: docstring of sage.graphs.base.boost_graph.johnson_shortest_paths:18: WARNING: Definition list ends without a blank line; unexpected unindent. """ The above exception was the direct cause of the following exception: Traceback (most recent call last): File "sage_setup/docbuild/__main__.py", line 2, in <module> main() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 1730, in main builder() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 351, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 547, in _wrapper build_many(build_ref_doc, L) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 288, in build_many ret = x.get(99999) File "/usr/lib/python3.7/multiprocessing/pool.py", line 657, in get raise self._value OSError: docstring of sage.graphs.base.boost_graph.johnson_shortest_paths:18: WARNING: Definition list ends without a blank line; unexpected unindent.
it looks like a stray space at the start of line 1085 of sage/graphs/base/boost_graph.pyx
https://git.sagemath.org/sage.git/tree/src/sage/graphs/base/boost_graph.pyx?id=136cae2e3fb5f6dec8173f427da3321d49b0a835#n1085 is the cause of the problem. Removing it makes the documentation build here.
comment:65 Changed 22 months ago by
- Commit changed from 2a26a6594180d69be8e784d6c2948e443407af04 to dc082bb5e6bee3644615fb5cbc62a44d7a52ed6a
Branch pushed to git repo; I updated commit sha1. New commits:
dc082bb | Fixed typo
|
comment:66 in reply to: ↑ 64 Changed 22 months ago by
Replying to fbissey:
Just to make things clear, that is the failure I see
Error building the documentation. multiprocessing.pool.RemoteTraceback: """ Traceback (most recent call last): File "/usr/lib/python3.7/multiprocessing/pool.py", line 121, in worker result = (True, func(*args, **kwds)) File "/usr/lib/python3.7/multiprocessing/pool.py", line 44, in mapstar return list(map(*args)) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 79, in build_ref_doc getattr(ReferenceSubBuilder(doc, lang), format)(*args, **kwds) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 761, in _wrapper getattr(DocBuilder, build_type)(self, *args, **kwds) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 133, in f runsphinx() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/sphinxbuild.py", line 317, in runsphinx sys.stderr.raise_errors() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/sphinxbuild.py", line 252, in raise_errors raise OSError(self._error) OSError: docstring of sage.graphs.base.boost_graph.johnson_shortest_paths:18: WARNING: Definition list ends without a blank line; unexpected unindent. """ The above exception was the direct cause of the following exception: Traceback (most recent call last): File "sage_setup/docbuild/__main__.py", line 2, in <module> main() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 1730, in main builder() File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 351, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 547, in _wrapper build_many(build_ref_doc, L) File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/sage_setup/docbuild/__init__.py", line 288, in build_many ret = x.get(99999) File "/usr/lib/python3.7/multiprocessing/pool.py", line 657, in get raise self._value OSError: docstring of sage.graphs.base.boost_graph.johnson_shortest_paths:18: WARNING: Definition list ends without a blank line; unexpected unindent.it looks like a stray space at the start of line 1085 of
sage/graphs/base/boost_graph.pyx
https://git.sagemath.org/sage.git/tree/src/sage/graphs/base/boost_graph.pyx?id=136cae2e3fb5f6dec8173f427da3321d49b0a835#n1085 is the cause of the problem. Removing it makes the documentation build here.
Thank you for the info. Fixed it!
comment:67 Changed 22 months ago by
@fbissey: 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 Changed 22 months ago by
All tests seem to pass now!
comment:70 Changed 22 months ago by
- Branch changed from public/graphs/27518_floyd_warshall_boost to dc082bb5e6bee3644615fb5cbc62a44d7a52ed6a
- Resolution set to fixed
- Status changed from positive_review to closed
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).