memory efficient implementation of Wiener index

[dcoudert]

We improve the implementation of Wiener index for (weighted) (di)graphs by avoiding to compute and store into memory the full distance matrix. This way we can compute this index for larger graphs.

CC: @vipul79321 @kliem

Component: graph theory

Keywords: gsoc2020

Author: David Coudert, Vipul Gupta

Branch/Commit: acf7647

Reviewer: Vipul Gupta, Jonathan Kliem

Issue created by migration from https://trac.sagemath.org/ticket/30247

[dcoudert]

Branch: public/graphs/30247_wiener

[dcoudert]

Commit: 6452967

[dcoudert]

New commits:

6452967

trac #30247: better wiener index

[dcoudert]

comment:2

Without this patch

sage: G = graphs.Grid2dGraph(10, 10)
sage: %time G.wiener_index()
CPU times: user 1.66 ms, sys: 938 µs, total: 2.6 ms
Wall time: 4.58 ms
33000
sage: G = graphs.Grid2dGraph(20, 20)
sage: %time G.wiener_index()
CPU times: user 4.4 ms, sys: 162 µs, total: 4.56 ms
Wall time: 4.59 ms
1064000
sage: G = graphs.Grid2dGraph(50, 50)
sage: %time G.wiener_index()
CPU times: user 79.4 ms, sys: 8.78 ms, total: 88.2 ms
Wall time: 88.8 ms
104125000

With this patch

sage: G = graphs.Grid2dGraph(10, 10)
sage: %time G.wiener_index()
CPU times: user 1.12 ms, sys: 497 µs, total: 1.62 ms
Wall time: 3.28 ms
33000
sage: G = graphs.Grid2dGraph(20, 20)
sage: %time G.wiener_index()
CPU times: user 4.64 ms, sys: 165 µs, total: 4.8 ms
Wall time: 4.87 ms
1064000
sage: G = graphs.Grid2dGraph(50, 50)
sage: %time G.wiener_index()
CPU times: user 62.1 ms, sys: 1.66 ms, total: 63.8 ms
Wall time: 63.4 ms
104125000

[sagetrac-git]

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

e29852c

trac #30247: small corrections for directed graphs

[sagetrac-git]

Changed commit from 6452967 to e29852c

[dcoudert]

comment:4

I did a small correction for directed graphs in wiener_index and average_distance, and added a test.

I let the weighted case open.

[vipul79321]

comment:5

Replying to @dcoudert:

I did a small correction for directed graphs in wiener_index and average_distance, and added a test.

I let the weighted case open.

I can work on implementing the weighted version of wiener_index method in boost_graph.pyx.

[dcoudert]

comment:6

Feel free to do it. As you can see, it is interesting as now we can go for larger graphs and consume little memory.

[sagetrac-git]

Changed commit from e29852c to adb4728

[sagetrac-git]

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

adb4728

method added for weighted graphs

[vipul79321]

comment:8

• I have one question, why bellman-ford is not an option for algorithm in wiener_index, shortest_path_all_pairs etc.

• Also, due to use of correct_type in shortest_paths, johnson_shortest_paths, floyd_warshall_shortest_path in boost_graph.pyx. There is non-uniformity in output. For e.g. (20, 20.0 etc). I propose we should open another ticket with the purpose of removing correct_type code (as it generally fails, discussed in comment 17 of Modify shortest_paths method in boost_graph.pyx to take list of vertices as input #30188) and modify affected doc-tests.

Best

Vipul

[vipul79321]

Changed keywords from none to gsoc2020

[vipul79321]

Changed author from David Coudert to David Coudert, Vipul Gupta

[dcoudert]

comment:10

Replying to @vipul79321:

• I have one question, why bellman-ford is not an option for algorithm in wiener_index, shortest_path_all_pairs etc.

Certainly because the usage of the list of algorithms has not been updated. No specific reason I think.

• Also, due to use of correct_type in shortest_paths, johnson_shortest_paths, floyd_warshall_shortest_path in boost_graph.pyx. There is non-uniformity in output. For e.g. (20, 20.0 etc). I propose we should open another ticket with the purpose of removing correct_type code (as it generally fails, discussed in comment 17 of Modify shortest_paths method in boost_graph.pyx to take list of vertices as input #30188) and modify affected doc-tests.

Are you sure it's always failing ? The key questions are:

• are distances computation with boost always done on double ?
• what's the impact on methods using the results ?

In general, it's important to be able to return the correct type, but we can also document the fact that some algorithm are able to return only double, double or int, or any type. For instance, using a pure Python code, we should be able to compute distances over rationals and more generally any type supporting addition and with a total ordering of its elements. But using boost, it's not possible.

Can you update examples in boost and generic_graph.py to force using boost on the circuit.

[sagetrac-git]

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

b2a4155

made doc test use boost, added bellman-ford in algorithm list

[sagetrac-git]

Changed commit from adb4728 to b2a4155

[vipul79321]

comment:12

Replying to @dcoudert:

Are you sure it's always failing ?

It fails for this basic scenario when edge weights are both integer and non-integer. See this for instance -

sage: from sage.graphs.base.boost_graph import shortest_paths
sage: G = Graph([(0,1,2), (1,2,3.3)], weighted=True)
sage: shortest_paths(G,0)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-ca5ef018db1e> in <module>()
----> 1 shortest_paths(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 (build/cythonized/sage/graphs/base/boost_graph.cpp:12344)()
    819 
    820 
--> 821 cpdef shortest_paths(g, start, weight_function=None, algorithm=None):
    822     r"""
    823     Compute the shortest paths from ``start`` to all other vertices.

/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.shortest_paths (build/cythonized/sage/graphs/base/boost_graph.cpp:12130)()
   1012         if result.distances[v] != sys.float_info.max:
   1013             w = int_to_v[v]
-> 1014             dist[w] = correct_type(result.distances[v])
   1015             pred[w] = int_to_v[result.predecessors[v]] if result.predecessors[v] != v else None
   1016     return (dist, pred)

/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

---

The key questions are:
1).are distances computation with boost always done on double ?

Yes. See this piece of code in boost_interface.cpp -

typedef struct {
    std::vector<double> distances; // An array with all distances from the starting vertex
    std::vector<v_index> predecessors; // For each vertex v, the first vertex in a shortest
                                  // path from the starting vertex to v.
} result_distances;

2). what's the impact on methods using the results ?

Sorry, I didnt understand what you mean.

---

In general, it's important to be able to return the correct type, but we can also document the fact that some algorithm are able to return only double, double or int, or any type. For instance, using a pure Python code, we should be able to compute distances over rationals and more generally any type supporting addition and with a total ordering of its elements. But using boost, it's not possible.

Yeah, We can mention that in documentation, because with boost we can only get double values.

---

Currently, I dont have any scenario where vector[double] will fails. For e.g., I tried it with non-rational edge weights (pi or e) and it gave ans as double approximation, which is better than nothing. See this, for example

sage: from sage.graphs.base.boost_graph import wiener_index
sage: G = Graph([(0,1,pi)], weighted=True)
sage: wiener_index(G)
3.141592653589793

[dcoudert]

comment:13

OK. If we document properly that the returned values with boost are always double, then I'm Ok to remove the correct type stuff.

2). what's the impact on methods using the results ?

Sorry, I didnt understand what you mean.

Do we have methods calling distance computation with boost and assuming that the returned value is an int ?
It may happen with unweighted graphs as we then assume weight 1.

Currently, I dont have any scenario where vector[double] will fails. For e.g., I tried it with non-rational edge weights (pi or e) and it gave ans as double approximation, which is better than nothing. See this, for example

sage: from sage.graphs.base.boost_graph import wiener_index
sage: G = Graph([(0,1,pi)], weighted=True)
sage: wiener_index(G)
3.141592653589793

In such case, the weights are converted to double. So a user expecting a results with pi must use another method. For instance:

sage: G = Graph([(0, 1, pi), (1, 2, e), (2, 3, sage: G = Graph([(0, 1, pi), (1, 2, e), (2, 3, sqrt(2))])
sage: G.edges()
[(0, 1, pi), (1, 2, e), (2, 3, sqrt(2))]
sage: sum(G.edge_labels())
pi + sqrt(2) + e
sage: G.weighted(True)
sage: G.shortest_path_all_pairs(by_weight=True, algorithm='Floyd-Warshall-Python')
({0: {0: 0, 1: pi, 2: pi + e, 3: pi + sqrt(2) + e},
  1: {1: 0, 0: pi, 2: e, 3: sqrt(2) + e},
  2: {2: 0, 1: e, 3: sqrt(2), 0: pi + e},
  3: {3: 0, 2: sqrt(2), 0: pi + sqrt(2) + e, 1: sqrt(2) + e}},
 {0: {0: None, 1: 0, 2: 1, 3: 2},
  1: {1: None, 0: 1, 2: 1, 3: 2},
  2: {2: None, 1: 2, 3: 2, 0: 1},
  3: {3: None, 2: 3, 0: 1, 1: 2}})

But so far we have an error for wiener index:

sage: G.wiener_index(by_weight=True, algorithm='Floyd-Warshall-Python')
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-e3251b3d7fb4> in <module>()
----> 1 G.wiener_index(by_weight=True, algorithm='Floyd-Warshall-Python')

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in wiener_index(self, by_weight, algorithm, weight_function, check_weight)
  16853             total += sum(u.values())
  16854 
> 16855         return total // 2
  16856 
  16857     def average_distance(self, by_weight=False, algorithm=None,

TypeError: unsupported operand type(s) for //: 'sage.symbolic.expression.Expression' and 'int'

so we must change from // to /

[sagetrac-git]

Changed commit from b2a4155 to 736f3df

[sagetrac-git]

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

736f3df

/ added instead of //

[vipul79321]

comment:15

Replying to @dcoudert:

so we must change from // to /

Done. I have tried to add a note in wiener_index method to mention that boost algorithms will return double version of wiener_index. Is it sufficient ?

P.S - There is already an example to show this in documentation.

[sagetrac-git]

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

673f863	trac #30247: fix merge conflict with 9.2.beta7
4067d78	trac #30247: minor corrections

[sagetrac-git]

Changed commit from 736f3df to 4067d78

[dcoudert]

comment:25

I made the changes except:

• empty or one element graphs, the usual small case issue in graph theory (often not well defined). The previous choice was to let these cases undefined. For one element graphs, we could answer 0, but for the empty graph, it's certainly a user choice.
  I tried with networkx and get:

sage: import networkx                                                                                                                                                             
sage: G = Graph()                                                                                                                                                                 
sage: gnx = G.networkx_graph()                                                                                                                                                    
sage: networkx.wiener_index(gnx)                                                                                                                                                  
---------------------------------------------------------------------------
NetworkXPointlessConcept                  Traceback (most recent call last)
<ipython-input-4-0fae33b2819e> in <module>
----> 1 networkx.wiener_index(gnx)

~/sage/local/lib/python3.7/site-packages/networkx/algorithms/wiener.py in wiener_index(G, weight)
     79     is_directed = G.is_directed()
     80     if (is_directed and not is_strongly_connected(G)) or \
---> 81             (not is_directed and not is_connected(G)):
     82         return float('inf')
     83     total = sum(chaini(p.values() for v, p in spl(G, weight=weight)))

</Users/dcoudert/sage/local/lib/python3.7/site-packages/decorator.py:decorator-gen-299> in is_connected(G)

~/sage/local/lib/python3.7/site-packages/networkx/utils/decorators.py in _not_implemented_for(not_implement_for_func, *args, **kwargs)
     80             raise nx.NetworkXNotImplemented(msg)
     81         else:
---> 82             return not_implement_for_func(*args, **kwargs)
     83     return _not_implemented_for
     84 

~/sage/local/lib/python3.7/site-packages/networkx/algorithms/components/connected.py in is_connected(G)
    145     if len(G) == 0:
    146         raise nx.NetworkXPointlessConcept('Connectivity is undefined ',
--> 147                                           'for the null graph.')
    148     return sum(1 for node in _plain_bfs(G, arbitrary_element(G))) == len(G)
    149 

NetworkXPointlessConcept: ('Connectivity is undefined ', 'for the null graph.')
sage: G = Graph(1)                                                                                                                                                                
sage: gnx = G.networkx_graph()                                                                                                                                                    
sage: networkx.wiener_index(gnx)                                                                                                                                                  
0.0

Do you think I should do like networkx and return 0 for one element graphs ?

• for if WI in QQ, I changed to if WI in ZZ. Should be better.

• I added Dijkstra_NetworkX, but I don't see how a pure Python method could be faster than a C++ one.

  Actually, we have too many methods for computing shortest paths and distances and this is not well documented. Ideally, we should create a specific documentation page describing the various methods with advantages and limitations.

• for the double dictionary, it's a side effect of the fact that we have too much ways of computing distances. So for some algorithms, it's currently the only way.

  A long term objective is to create a DistancesView hiding internal representations, and so avoiding double dictionary. The difficulty is to handle the different types of values (integer, floats, rational, etc.). It could even have a lazy mode to avoid computing distances from a vertex if never asked (again a difficulty: how / when to raise errors like negative weight cycle?).

[sagetrac-git]

Changed commit from 49472e3 to 8bbf195

[sagetrac-git]

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

8bbf195

trac #30247: set wiener index of one vertex graph to 0

[dcoudert]

comment:27

I let wiener index of empty graph undefined and set the 0 the wiener index of one vertex graphs.

[sagetrac-git]

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

bfc181f

trac #30247: catch new exception appearing with boost 1.7.3

[sagetrac-git]

Changed commit from 8bbf195 to bfc181f

[dcoudert]

comment:29

this last commit fix a new error appearing when using boost 1.7.3 (I have a new laptop with it). With boost 1.7.2, we don't have this error.

File "src/sage/graphs/base/boost_graph.pyx", line 2674, in sage.graphs.base.boost_graph.wiener_index
Failed example:
    wiener_index(g, algorithm="Dijkstra", weight_function=weight_of)
Expected:
    Traceback (most recent call last):
    ...
    RuntimeError: Dijkstra algorithm does not work with negative weights, use Bellman-Ford instead
Got:
    libc++abi.dylib: terminating with uncaught exception of type boost::wrapexcept<boost::negative_edge>: The graph may not contain an edge with negative weight.
    Traceback (most recent call last):
      File "sage/graphs/base/boost_graph.pyx", line 2762, in sage.graphs.base.boost_graph.wiener_index (build/cythonized/sage/graphs/base/boost_graph.cpp:28864)
        sig_on()
    RuntimeError: Aborted
    <BLANKLINE>
    During handling of the above exception, another exception occurred:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 715, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1139, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.graphs.base.boost_graph.wiener_index[13]>", line 1, in <module>
        wiener_index(g, algorithm="Dijkstra", weight_function=weight_of)
      File "sage/graphs/base/boost_graph.pyx", line 2604, in sage.graphs.base.boost_graph.wiener_index (build/cythonized/sage/graphs/base/boost_graph.cpp:29336)
        cpdef wiener_index(g, algorithm=None, weight_function=None, check_weight=True):
      File "sage/graphs/base/boost_graph.pyx", line 2770, in sage.graphs.base.boost_graph.wiener_index (build/cythonized/sage/graphs/base/boost_graph.cpp:28966)
        raise RuntimeError(msg)
    RuntimeError: Aborted

[kliem]

comment:30

Build error

[sagelib-9.2.beta8] /srv/public/kliem/sage/local/include/boost/mpl/assert.hpp:188:21: warning: unnecessary parentheses in declaration of ‘assert_arg’ [-Wparentheses]
[sagelib-9.2.beta8]  failed ************ (Pred::************
[sagelib-9.2.beta8]                      ^
[sagelib-9.2.beta8] /srv/public/kliem/sage/local/include/boost/mpl/assert.hpp:193:21: warning: unnecessary parentheses in declaration of ‘assert_not_arg’ [-Wparentheses]
[sagelib-9.2.beta8]  failed ************ (boost::mpl::not_<Pred>::************
[sagelib-9.2.beta8]                      ^
[sagelib-9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c: In function ‘__pyx_f_4sage_6graphs_19distances_all_pairs_diameter_DHV’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:843:40: warning: ‘__pyx_v_idx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
[sagelib-9.2.beta8]    #define likely(x)   __builtin_expect(!!(x), 1)
[sagelib-9.2.beta8]                                         ^
[sagelib-9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:16252:8: note: ‘__pyx_v_idx’ was declared here
[sagelib-9.2.beta8]  size_t __pyx_v_idx;
[sagelib-9.2.beta8]         ^~~~~~~~~~~
[sagelib-9.2.beta8] In file included from build/cythonized/sage/graphs/base/boost_graph.cpp:668:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp: In member function ‘result_distances BoostGraph<OutEdgeListS, VertexListS, DirectedS, EdgeListS, EdgeProperty>::dijkstra_shortest_paths(v_index)’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:26: error: ‘wrapexcept’ in namespace ‘boost’ does not name a template type
[sagelib-9.2.beta8]           } catch (boost::wrapexcept<boost::negative_edge> e) {
[sagelib-9.2.beta8]                           ^~~~~~~~~~
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:36: error: expected ‘)’ before ‘<’ token
[sagelib-9.2.beta8]           } catch (boost::wrapexcept<boost::negative_edge> e) {
[sagelib-9.2.beta8]                   ~                 ^
[sagelib-9.2.beta8]                                     )
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:36: error: expected ‘{’ before ‘<’ token
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:36: error: expected primary-expression before ‘<’ token
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:57: error: expected primary-expression before ‘>’ token
[sagelib-9.2.beta8]           } catch (boost::wrapexcept<boost::negative_edge> e) {
[sagelib-9.2.beta8]                                                          ^
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:59: error: ‘e’ was not declared in this scope
[sagelib-9.2.beta8]           } catch (boost::wrapexcept<boost::negative_edge> e) {
[sagelib-9.2.beta8]                                                            ^
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp: In function ‘PyObject* __pyx_f_4sage_6graphs_4base_11boost_graph_diameter_DHV(PyObject*, int, __pyx_opt_args_4sage_6graphs_4base_11boost_graph_diameter_DHV*)’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:22823:35: warning: comparison of integer expressions of different signedness: ‘size_t’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
[sagelib-9.2.beta8]    for (__pyx_t_16 = 0; __pyx_t_16 < __pyx_t_15; __pyx_t_16+=1) {
[sagelib-9.2.beta8]                         ~~~~~~~~~~~^~~~~~~~~~~~
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp: In function ‘PyObject* __pyx_f_4sage_6graphs_4base_11boost_graph_wiener_index(PyObject*, int, __pyx_opt_args_4sage_6graphs_4base_11boost_graph_wiener_index*)’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:28348:35: warning: comparison of integer expressions of different signedness: ‘v_index’ {aka ‘int’} and ‘unsigned int’ [-Wsign-compare]
[sagelib-9.2.beta8]    for (__pyx_t_14 = 0; __pyx_t_14 < __pyx_t_17; __pyx_t_14+=1) {
[sagelib-9.2.beta8]                         ~~~~~~~~~~~^~~~~~~~~~~~
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:29099:46: warning: comparison of integer expressions of different signedness: ‘v_index’ {aka ‘int’} and ‘unsigned int’ [-Wsign-compare]
[sagelib-9.2.beta8]      for (__pyx_t_35 = __pyx_t_33; __pyx_t_35 < __pyx_t_34; __pyx_t_35+=1) {
[sagelib-9.2.beta8]                                    ~~~~~~~~~~~^~~~~~~~~~~~
[sagelib-9.2.beta8] In file included from build/cythonized/sage/graphs/base/boost_graph.cpp:668:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp: In instantiation of ‘result_distances BoostGraph<OutEdgeListS, VertexListS, DirectedS, EdgeListS, EdgeProperty>::dijkstra_shortest_paths(v_index) [with OutEdgeListS = boost::vecS; VertexListS = boost::vecS; DirectedS = boost::directedS; EdgeListS = boost::vecS; EdgeProperty = boost::property<boost::edge_weight_t, double>; v_index = int]’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:11682:82:   required from here
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:243:12: warning: catching polymorphic type ‘class boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::negative_edge> >’ by value [-Wcatch-value=]
[sagelib-9.2.beta8]           } catch (boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::negative_edge> > e) {
[sagelib-9.2.beta8]             ^~~~~
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp: In instantiation of ‘result_distances BoostGraph<OutEdgeListS, VertexListS, DirectedS, EdgeListS, EdgeProperty>::dijkstra_shortest_paths(v_index) [with OutEdgeListS = boost::vecS; VertexListS = boost::vecS; DirectedS = boost::undirectedS; EdgeListS = boost::vecS; EdgeProperty = boost::property<boost::edge_weight_t, double>; v_index = int]’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:11746:82:   required from here
[sagelib-9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:243:12: warning: catching polymorphic type ‘class boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::negative_edge> >’ by value [-Wcatch-value=]
[sagelib-9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c: In function ‘__pyx_pw_4sage_6graphs_19distances_all_pairs_9eccentricity’:
[sagelib-9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:843:40: warning: ‘__pyx_v_idx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
[sagelib-9.2.beta8]    #define likely(x)   __builtin_expect(!!(x), 1)
[sagelib-9.2.beta8]                                         ^
[sagelib-9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:12598:8: note: ‘__pyx_v_idx’ was declared here
[sagelib-9.2.beta8]  size_t __pyx_v_idx;
[sagelib-9.2.beta8]         ^~~~~~~~~~~
[sagelib-9.2.beta8] gcc -pthread -shared -L/srv/public/kliem/sage/local/lib -Wl,-rpath,/srv/public/kliem/sage/local/lib -L. -L/srv/public/kliem/sage/local/lib -Wl,-rpath,/srv/public/kliem/sage/local/lib -Wl,-rpath-link,/srv/public/kliem/sage/local/lib -L/srv/public/kliem/sage/local/lib -Wl,-rpath,/srv/public/kliem/sage/local/lib -march=native -O2 -g build/temp.linux-x86_64-3.7/build/cythonized/sage/graphs/distances_all_pairs.o -L/srv/public/kliem/sage/local/lib -lgmp -lpython3.7m -o build/lib.linux-x86_64-3.7/sage/graphs/distances_all_pairs.cpython-37m-x86_64-linux-gnu.so -lpari

[sagetrac-git]

Changed commit from bfc181f to acf7647

[sagetrac-git]

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

acf7647

trac #30247: improved checking of weights and algorithms

[dcoudert]

comment:32

This version is much simpler, avoids modifying the boost interface, and I expect more robust.

[dcoudert]

comment:34

oups, wrong button ;)

[dcoudert]

Reviewer: Vipul Gupta

[kliem]

comment:37

Thanks for making the suggested changes. I didn't get around to finally reviewing it, but I wrote don't anything that somewhat bothered me.

[dcoudert]

comment:38

Thank you. Do not hesitate to add your name as reviewer.

[kliem]

Changed reviewer from Vipul Gupta to Vipul Gupta, Jonathan Kliem

[vbraun]

Changed branch from public/graphs/30247_wiener to acf7647