Modify shortest_paths method in boost_graph.pyx to take list of vertices as input

[gh-vipul79321]

This ticket aims to modify shortest_paths method in boost_graph.pyx to take list of vertices as input. This will reduce the current scenario of converting a Sage graph to a Boost graph and then computing shortest paths for each required vertex.

[git]

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

[git]

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

​cc924a3

code added

[slelievre]

Please add your full name in the "Authors" field.

Please set to needs_review when ready for review.

Use one more f-string:

-            raise ValueError("the starting vertex " + str(v) + " is not in " +
-                             "the graph")
+            raise ValueError(f"the starting vertex {v} is not in the graph")

Maybe wrap long lines, for instance:

-                        raise RuntimeError("Dijkstra algorithm does not work with negative weights, use Bellman-Ford instead")
+                        raise RuntimeError("Dijkstra algorithm does not "
+                                           "work with negative weights, "
+                                           "use Bellman-Ford instead")

Maybe remove unnecessary parentheses:

-    return (distances, predecessors)
+    return distances, predecessors

[git]

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

​0c86a04

minor review commit

[gh-vipul79321]

Replying to slelievre:

Please add your full name in the "Authors" field.

Please set to needs_review when ready for review.

Currently, I am working on documentation. Will update as soon as I will be done.

Vipul

[gh-vipul79321]

I have one query regarding the documentation of shortest_path method in boost_graph.pyx. It mentions that

    Note that, if the graph is undirected, a negative edge automatically creates
    a negative cycle: for this reason, in this case, Dijkstra algorithm is
    always better.

I dont understand since there is already negative weight, then why to use dijkstra. And further, in such graphs shortest path computation may not be possible to negative cycle.

[git]

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

​33e436d

documentation added

[gh-vipul79321]

Replying to git:

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

​33e436d

documentation added

I have added documentation.

One thing, I would like to mention is that when vertext_list contains only one vertex, I have returned two dicts, instead of two dicts of dict. I have done so to keep uniformity in output from our method and current shortest_path method. So that in future, it will be easy for use to replace shortest_path method.

[gh-vipul79321]

Now after complete review, we just need to expose this method in shortest_path_all_pairs, centrality_closeness and all such methods in generic_graph.py

[dcoudert]

• Here you should first check if vertex_list is None

  +    if not isinstance(vertex_list, list):
  +        vertex_list = [vertex_list]
  +
  +    for v in vertex_list:
  +        if v not in g:
  +            raise ValueError(f"the starting vertex {v} is not in the graph")
  +
  +    if vertex_list == None:
  +        vertex_list = list(g)
  

• A list is better here. It's faster to get a value from a list than from a dictionary

  -    cdef dict int_to_v = dict(enumerate(g))
  +    cdef list int_to_v = list(g)
  

• Why this comment ?

  +    # Needed for rational curves.
  

• define types of variables distances, predecessors, pred_v, etc.

What I don't like here is that the method returns dict of dicts. A least a matrix would be a better choice. If the graph is large, it's a huge waste of time and space :(

[gh-vipul79321]

Replying to dcoudert:

What I don't like here is that the method returns dict of dicts. A least a matrix would be a better choice. If the graph is large, it's a huge waste of time and space :(

I was hoping maybe we could return dict instead of dict of dict. And in that dict key values will be vertex in vertex list. And item value will be a list or vector storing distances[v] in order of list(g). Meaning distances[v][i] will return shortest distance between v and list(g)[i].

Similarly for predecessor.

Is it ok?

P.S.- we can do similar thing with matrix. But i just feel that this will be nice way.

[git]

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

​f4011b5	trac #30188: fix merge conflicts
​a44ccbd	trac #30188: review commit

[dcoudert]

rebased on last beta and some minor improvements.

[git]

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

​8ae8745

made list of lists as return type

[gh-vipul79321]

Replying to git:

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

​8ae8745

made list of lists as return type

I have made the return type as list of lists. Now for i, v in enumerate(vertex_list): distances[i] and predecessors[i] will give us the shortest path information from v.

Although, one thing I would like to mention is following scenario -

Current output using list of lists
sage: G = Graph(5)
sage: shortest_paths_from_vertices(G,0)
([[0, +Infinity, +Infinity, +Infinity, +Infinity]],
 [[None, None, None, None, None]])

when returning dict of dict
sage: shortest_paths(G,0)
({0: 0}, {0: None})

Clearly, there is a need of extra memory in list of lists in case of disconnected graphs.

One bug that i encountered is:

sage: G = Graph([ (0,1,2), (1,2,0.7)], weighted = True)
sage: shortest_paths_from_vertices(G, 0)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-12-1e6b63e11f81> in <module>()
----> 1 shortest_paths_from_vertices(G, Integer(0))

/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.shortest_paths_from_vertices (build/cythonized/sage/graphs/base/boost_graph.cpp:26092)()
   2101     return LB
   2102 
-> 2103 cpdef shortest_paths_from_vertices(g, vertex_list=None, weight_function=None, algorithm=None):
   2104     r"""
   2105     Compute the shortest paths to all vertices from each vertex in

/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.shortest_paths_from_vertices (build/cythonized/sage/graphs/base/boost_graph.cpp:25805)()
   2312         for vert in range(g.num_verts()):
   2313             if result.distances[vert] != sys.float_info.max:
-> 2314                 dist_v.append(correct_type(result.distances[vert]))
   2315                 pred = result.predecessors[vert]
   2316                 if pred != vert:

/home/vipul/sage/local/lib/python3.7/site-packages/sage/rings/integer.pyx in sage.rings.integer.Integer.__init__ (build/cythonized/sage/rings/integer.c:6091)()
    684                     mpz_set_pylong(self.value, n)
    685                 else:
--> 686                     raise TypeError("Cannot convert non-integral float to integer")
    687 
    688             elif isinstance(x, pari_gen):

TypeError: Cannot convert non-integral float to integer

I guess, we have to remove code of correct_type.

Best Vipul

[git]

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

​c309ab4

minor mistake

[gh-vipul79321]

Replying to git:

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

​c309ab4

minor mistake

Fixed a error, which i mistakenly introduced.

I havent updated documentation yet. I will update it, when we finalize the changes

[dcoudert]

Deciding of the correct type to use is not easy. May be it's easier to not try to correct the type, no ?

[gh-vipul79321]

Replying to dcoudert:

Deciding of the correct type to use is not easy. May be it's easier to not try to correct the type, no ?

Yeah, i will remove that part.

[git]

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

​10143a3

correct type code removed

[gh-vipul79321]

Replying to git:

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

​10143a3

correct type code removed

Correct type code removed. If we are on board on current return method, I will update the documentation and expose it in generic_graph.py

[dcoudert]

Honestly, I'm not completely sure of what the method does and it's objective. Can you clarify how you plan to use it and where. I'm not sure it does exactly what is needed.

[gh-vipul79321]

Goal of this ticket is avoid format conversion (from sage graph to boost graph) for each vertex during shortest_path_all_pairs computation or other such method in generic_graph.py. For e.g, see the following code -

    from sage.graphs.base.boost_graph import shortest_paths
    dist = dict()
    pred = dict()
    for u in self:
        dist[u], pred[u] = shortest_paths(self, u, weight_function, algorithm)
    return dist, pred

Here shortest_paths of boost_graph.pyx is called for each vertex and hence format conversion time for each vertex.

This ticket aims to implement a method in boost_graph.pyx and take list of vertices as input and return shortest_path information for each vertex. Thus avoid conversion overhead.

Our current method shortest_path_from_vertices in boost_graph.pyx does that.

I hope it clear your doubt about purpose of the ticket :)

Vipul

[dcoudert]

my main concern is that this method returns lists of distances. Outside this method, the chosen order of the vertices is not known. So I don't know how this can be used.

[gh-vipul79321]

Replying to dcoudert:

my main concern is that this method returns lists of distances. Outside this method, the chosen order of the vertices is not known. So I don't know how this can be used.

I think we can do it as follows in methods calling this method for retreiving path information -

distances , predecessors = shortest_path_from_vertices(G, vertex_list)
for i, v in enumerate(vertex_list):
    dist_v = distances[i]
    pred_v = predecessors[i]
    
    for id, vertex in enumerate(G):
       distance of vertex from v  = dist_v[id]
       predecessor of vertex in shortest_path from v = pred_v[id]

Will it work?

[dcoudert]

I don't think it's a safe usage, but I may be wrong.

[gh-vipul79321]

Replying to dcoudert:

I don't think it's a safe usage, but I may be wrong.

If that's the case then, we can returnlist of dicts, although it will be slow, but it will be an overall improvement on current scenario.

I will add a note about in meta-ticket.

[dcoudert]

2 ideas to consider:

• add input parameter order or int_to_vertex to specify the order of the vertices in the list
• have 2 possible returned types: dict of lists and dict of dicts. The decision could be either when the given ordering is None, or with an extra input parameter.

[git]

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

​466e7fb	updated
​243a084	documentation remaining
​9ee8ea2	introduced a extra parameter order
​2c27cb7	correct type method re-introduced for sake of doc-test. Will modify after finailizing
​c5bfbfa	Merge branch 'develop' into temp

[dcoudert]

We are almost done

• to avoid potential issues when building the doc, avoid : in

  +    The input graph can be weighted: if the algorithm is Dijkstra, no negative
  +    weights are allowed, while if the algorithm is Bellman-Ford, negative
  +    weights are allowed, but there must be no negative cycle (otherwise, the
  +    shortest paths might not exist).
  +
  +    However, Dijkstra algorithm is more efficient: for this reason, we suggest
  +    to use Bellman-Ford only if necessary (which is also the default option).
  

• in the inout blocks, when the sentences are short, the convention is to not end with ., e.g.,

  -    - ``order`` -- list (default: ``None``); order of vertices of `g`.
  +    - ``order`` -- list (default: ``None``); order of vertices of `g`
  

  of course, if you have a paragraph with several sentences, a final . is needed
• again avoid : in Two possible outputs:. You can write for instead The type of output depends on the input. More precisely,

• this is simpler and more efficient

  -           for vertex in g:
  -                if vertex not in order:
  -                    raise ValueError("Given ordering is not valid")
  +            if any(v not in g for v in order:
  +                raise ValueError("Given ordering is not valid")
  

  indeed, since order is a list, the test vertex not in order has time complexity in O(n), while testing v not in g takes constant time (I hope)

[git]

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

​ad7dc7d	review commit
​b345479	fixed merge conflict
​97fef26	minor correction

[gh-vipul79321]

Replying to dcoudert:

• this is simpler and more efficient

  -           for vertex in g:
  -                if vertex not in order:
  -                    raise ValueError("Given ordering is not valid")
  +            if any(v not in g for v in order:
  +                raise ValueError("Given ordering is not valid")
  

  indeed, since order is a list, the test vertex not in order has time complexity in O(n), while testing v not in g takes constant time (I hope)

Tried this

 +            if any(v not in g for v in order:
 +                raise ValueError("Given ordering is not valid")

but it gave the following error closures inside cpdef functions not yet supported.

[dcoudert]

LGTM.