Implementation of Floyd-Warshall for all pair shortest distance

[gh-Hrishabh-yadav]

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.

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

[gh-giorgosgiapis]

New commits:

​ffcea9e

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

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

• 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 method shortest_paths of igraph call Johnson algorithm and not Floyd-Warshall for the reason explained here: ​https://lists.nongnu.org/archive/html/igraph-help/2009-06/msg00029.html

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

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

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

[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 !

[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(V³).

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

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

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

[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(V³)?

[dcoudert]

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

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

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

[git]

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

[git]

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

​41358f9

Fixed minor issues

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

[git]

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

​8e8799d

Fixed comments, documentation and code for predecessors

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

[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

[git]

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

​b10779f

Fixed minor code issues

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

[git]

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

​1d65ba1

Added Floyd-Warshall boost implementation

[dcoudert]

I think the main difficulty with boost is to understand how to iterate over weighted edges... and possibly also over vertices.

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

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

[git]

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

​2333057

Fixed minor issues

[git]

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

​b76dd9b

Fixed comments and documentation

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

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

[git]

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

​76bfdaa

Fixed documentation and added new method

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

[git]

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

​533545d

Improved code and documentation

[gh-giorgosgiapis]

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

[git]

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

​328e02b

Fixed documentation on generic_graph.py

[dcoudert]

any progress on using boost edge iterator ?

in your last commit, you remove the empty line before .. NOTE::. Please put it back.

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

[git]

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

​b68078a

get_predecessors now uses boost graph

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

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

[git]

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

​1754628

Fixed type issues

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

​1754628

Fixed type issues

[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

[git]

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

​dc8a9e1

Fixed minor issues

[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

[git]

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

​495d610

Comments and documentation are in 80 columns mode

[dcoudert]

in johnson_shortest_paths too ;)

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

[dcoudert]

I think this line for instance has length more that 80

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

[git]

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

​e26d63d

Fixed issues with comments and documentation

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

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

[git]

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

​ee720d4

Modified shortest_path_all_pairs method in generic_graph.py

[git]

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

​ef38d91

Fixed typo

[dcoudert]

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

[git]

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

​2a26a65

trac #27518: alignement

[dcoudert]

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

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

[dcoudert]

Please add your real name in Authors field.

LGTM.

[vbraun]

Docbuild fails, see patchbot

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

[git]

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

​dc082bb

Fixed typo

[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!

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

[gh-giorgosgiapis]

All tests seem to pass now!

[dcoudert]

LGTM.