Opened 8 months ago

Closed 6 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) 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 8 months ago by gh-giorgosgiapis

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

comment:2 Changed 8 months ago by gh-giorgosgiapis

  • Branch set to u/gh-giorgosgiapis/weighted_floyd_warshall

comment:3 Changed 8 months ago by gh-giorgosgiapis

  • Commit set to ffcea9e1772dc81bfae6373c8b69bbc481514a4c
  • Status changed from new to needs_review

New commits:

ffcea9eModified Floyd-Warshall to work with weighted graphs with non-negative integer edge weights.

comment:4 Changed 8 months ago by gh-giorgosgiapis

  • Owner changed from (none) to gh-giorgosgiapis

comment:5 Changed 8 months ago by dcoudert

  • 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.

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

when igraph is installed, we can do H = G.igraph_graph() and then H.shortest_paths() with appropriate parameters.

comment:6 Changed 8 months ago by gh-Hrishabh-yadav

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: Changed 8 months ago by gh-giorgosgiapis

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 8 months ago by dcoudert

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 8 months ago by gh-giorgosgiapis

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 8 months ago by dcoudert

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 8 months ago by gh-giorgosgiapis

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?

Last edited 8 months ago by gh-giorgosgiapis (previous) (diff)

comment:12 follow-up: Changed 8 months ago by 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.

comment:13 in reply to: ↑ 12 Changed 8 months ago by gh-giorgosgiapis

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 8 months ago by dcoudert

It will be O(N.M) with a small constants...

comment:15 follow-up: Changed 8 months ago by gh-giorgosgiapis

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.

Last edited 8 months ago by gh-giorgosgiapis (previous) (diff)

comment:16 in reply to: ↑ 15 Changed 8 months ago by dcoudert

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 8 months ago by git

  • Commit changed from ffcea9e1772dc81bfae6373c8b69bbc481514a4c to ef91486fa6982a5c23db3c62459cc2811d039c62

Branch pushed to git repo; I updated commit sha1. New commits:

5aceae0Added predecessors support in boost johnson_shortest_paths method
e87b06bMerge branch 'u/gh-giorgosgiapis/weighted_floyd_warshall' of git://trac.sagemath.org/sage into johnson_pred
ef91486Added predecessors support in boost johnson_shortest_paths method

comment:18 Changed 8 months ago by git

  • Commit changed from ef91486fa6982a5c23db3c62459cc2811d039c62 to 41358f92e6034b50c720f608e3229dc36111ec4e

Branch pushed to git repo; I updated commit sha1. New commits:

41358f9Fixed minor issues

comment:19 follow-up: Changed 8 months ago by dcoudert

  • 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 8 months ago by git

  • Commit changed from 41358f92e6034b50c720f608e3229dc36111ec4e to 8e8799d9799ca2e915b65a4fd5b5e6bae663c04f

Branch pushed to git repo; I updated commit sha1. New commits:

8e8799dFixed comments, documentation and code for predecessors

comment:21 in reply to: ↑ 19 Changed 8 months ago by gh-giorgosgiapis

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] = j

It'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 8 months ago by dcoudert

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 8 months ago by git

  • Commit changed from 8e8799d9799ca2e915b65a4fd5b5e6bae663c04f to b10779ff182689113014532c7820e409db736dbb

Branch pushed to git repo; I updated commit sha1. New commits:

b10779fFixed minor code issues

comment:24 Changed 8 months ago by gh-giorgosgiapis

Fixed. I will now expose boost Floyd Warshall algorithm implementation to SageMath and then try to use boost to speed up both these methods.

Last edited 8 months ago by gh-giorgosgiapis (previous) (diff)

comment:25 Changed 8 months ago by git

  • Commit changed from b10779ff182689113014532c7820e409db736dbb to 1d65ba196676ee61276d0ffb33e21dcbea8a02a8

Branch pushed to git repo; I updated commit sha1. New commits:

1d65ba1Added Floyd-Warshall boost implementation

comment:26 follow-up: Changed 8 months ago by dcoudert

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 8 months ago by gh-giorgosgiapis

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: Changed 7 months ago by 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 of for e in g.edges():. Indeed, .edges() sorts edges by default and we don't need that here.

comment:29 Changed 7 months ago by git

  • Commit changed from 1d65ba196676ee61276d0ffb33e21dcbea8a02a8 to 2333057647264bfff1966030a34082c42b9b126f

Branch pushed to git repo; I updated commit sha1. New commits:

2333057Fixed minor issues

comment:30 Changed 7 months ago by git

  • Commit changed from 2333057647264bfff1966030a34082c42b9b126f to b76dd9bd9409c3fb18b48ef006b869268cd6f81c

Branch pushed to git repo; I updated commit sha1. New commits:

b76dd9bFixed comments and documentation

comment:31 in reply to: ↑ 28 Changed 7 months ago by gh-giorgosgiapis

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 of for 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 7 months ago by dcoudert

  • this statement is incorrect as edge weights are not always 1. Better to say that w is a predecessor of v on a shortest path from u to v.
    +    `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 7 months ago by git

  • Commit changed from b76dd9bd9409c3fb18b48ef006b869268cd6f81c to 76bfdaa5a47fc65bb99600201258c8b3cd9dc08a

Branch pushed to git repo; I updated commit sha1. New commits:

76bfdaaFixed documentation and added new method

comment:34 follow-up: Changed 7 months ago by dcoudert

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 7 months ago by git

  • Commit changed from 76bfdaa5a47fc65bb99600201258c8b3cd9dc08a to 533545d45da6ee0e4dd9969eb83fe590a3d28e5d

Branch pushed to git repo; I updated commit sha1. New commits:

533545dImproved code and documentation

comment:36 in reply to: ↑ 34 Changed 7 months ago by gh-giorgosgiapis

Fixed everything. Tomorrow I will try to use boost edge iterator in get_predecessors.

comment:37 Changed 7 months ago by git

  • Commit changed from 533545d45da6ee0e4dd9969eb83fe590a3d28e5d to 328e02b05ced4164574de385838584400c6f44cd

Branch pushed to git repo; I updated commit sha1. New commits:

328e02bFixed documentation on generic_graph.py

comment:38 follow-up: Changed 7 months ago by dcoudert

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 7 months ago by gh-giorgosgiapis

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 7 months ago by git

  • Commit changed from 328e02b05ced4164574de385838584400c6f44cd to b68078a91af0db8906264be3154c0ab81f60922a

Branch pushed to git repo; I updated commit sha1. New commits:

b68078aget_predecessors now uses boost graph

comment:41 Changed 7 months ago by gh-giorgosgiapis

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: Changed 7 months ago by 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.

comment:43 Changed 7 months ago by git

  • Commit changed from b68078a91af0db8906264be3154c0ab81f60922a to 1754628b6123d33f61026a5013fea25169d93201

Branch pushed to git repo; I updated commit sha1. New commits:

1754628Fixed type issues

comment:44 in reply to: ↑ 42 Changed 7 months ago by gh-giorgosgiapis

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:

1754628Fixed type issues

comment:45 Changed 7 months ago by dcoudert

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 for directed= and weight_type= as these parameters are not optional

comment:46 Changed 7 months ago by git

  • Commit changed from 1754628b6123d33f61026a5013fea25169d93201 to dc8a9e1cdd2e7e39b0e39b946ad4db960097b304

Branch pushed to git repo; I updated commit sha1. New commits:

dc8a9e1Fixed minor issues

comment:47 Changed 7 months ago by dcoudert

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 7 months ago by git

  • Commit changed from dc8a9e1cdd2e7e39b0e39b946ad4db960097b304 to 495d610aff176350dc5bcddde123482cba7da494

Branch pushed to git repo; I updated commit sha1. New commits:

495d610Comments and documentation are in 80 columns mode

comment:49 follow-up: Changed 7 months ago by dcoudert

in johnson_shortest_paths too ;)

comment:50 in reply to: ↑ 49 Changed 7 months ago by gh-giorgosgiapis

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: Changed 7 months ago by dcoudert

I think this line for instance has length more that 80

+    ``(distances, predecessors)`` where ``distance[u][v]`` denotes the distance of 

comment:52 Changed 7 months ago by git

  • Commit changed from 495d610aff176350dc5bcddde123482cba7da494 to e26d63d525a46211ee56d453df0768cab4099dba

Branch pushed to git repo; I updated commit sha1. New commits:

e26d63dFixed issues with comments and documentation

comment:53 in reply to: ↑ 51 Changed 7 months ago by gh-giorgosgiapis

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 7 months ago by dcoudert

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 7 months ago by git

  • Commit changed from e26d63d525a46211ee56d453df0768cab4099dba to ee720d465143f5143281edf88698ed8e69310545

Branch pushed to git repo; I updated commit sha1. New commits:

ee720d4Modified shortest_path_all_pairs method in generic_graph.py

comment:56 Changed 7 months ago by git

  • Commit changed from ee720d465143f5143281edf88698ed8e69310545 to ef38d911514f201c7204d42f919ad6442ad505e3

Branch pushed to git repo; I updated commit sha1. New commits:

ef38d91Fixed typo

comment:57 Changed 6 months ago by dcoudert

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

803af4etrac #27518: fix merge conflict with 8.8.beta4

comment:58 Changed 6 months ago by git

  • Commit changed from 803af4ef7e33181484e7472a3a71bed96e65bf2e to 2a26a6594180d69be8e784d6c2948e443407af04

Branch pushed to git repo; I updated commit sha1. New commits:

2a26a65trac #27518: alignement

comment:59 follow-up: Changed 6 months ago by dcoudert

For me this patch is good to go. I'm waiting confirmation from your side.

comment:60 in reply to: ↑ 59 Changed 6 months ago by gh-giorgosgiapis

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 6 months ago by dcoudert

  • 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 6 months ago by gh-giorgosgiapis

  • Authors set to Georgios Giapitzakis Tzintanos

comment:63 Changed 6 months ago by vbraun

  • Status changed from positive_review to needs_work

Docbuild fails, see patchbot

comment:64 follow-up: Changed 6 months ago by 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.

comment:65 Changed 6 months ago by git

  • Commit changed from 2a26a6594180d69be8e784d6c2948e443407af04 to dc082bb5e6bee3644615fb5cbc62a44d7a52ed6a

Branch pushed to git repo; I updated commit sha1. New commits:

dc082bbFixed typo

comment:66 in reply to: ↑ 64 Changed 6 months ago by gh-giorgosgiapis

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 6 months ago by dcoudert

@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 6 months ago by gh-giorgosgiapis

All tests seem to pass now!

comment:69 Changed 6 months ago by dcoudert

  • Status changed from needs_work to positive_review

LGTM.

comment:70 Changed 6 months ago by vbraun

  • Branch changed from public/graphs/27518_floyd_warshall_boost to dc082bb5e6bee3644615fb5cbc62a44d7a52ed6a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.