Opened 14 months ago
Closed 13 months ago
#30247 closed enhancement (fixed)
memory efficient implementation of Wiener index
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  gsoc2020 
Cc:  ghvipul79321, ghkliem  Merged in:  
Authors:  David Coudert, Vipul Gupta  Reviewers:  Vipul Gupta, Jonathan Kliem 
Report Upstream:  N/A  Work issues:  
Branch:  acf7647 (Commits, GitHub, GitLab)  Commit:  acf7647264eef0b9909fa8c9955a2a4d874f53c4 
Dependencies:  Stopgaps: 
Description (last modified by )
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.
Change History (40)
comment:1 Changed 14 months ago by
 Branch set to public/graphs/30247_wiener
 Cc ghvipul79321 added
 Commit set to 6452967541645e827e3bf54b6bb0e013d2dd0c77
 Status changed from new to needs_review
comment:2 Changed 14 months ago by
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
comment:3 Changed 14 months ago by
 Commit changed from 6452967541645e827e3bf54b6bb0e013d2dd0c77 to e29852c6fa0651426ed4d1cef346946446a23ee3
Branch pushed to git repo; I updated commit sha1. New commits:
e29852c  trac #30247: small corrections for directed graphs

comment:4 followup: ↓ 5 Changed 14 months ago by
I did a small correction for directed graphs in wiener_index
and average_distance
, and added a test.
I let the weighted case open.
comment:5 in reply to: ↑ 4 Changed 14 months ago by
Replying to dcoudert:
I did a small correction for directed graphs in
wiener_index
andaverage_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
.
comment:6 Changed 14 months ago by
Feel free to do it. As you can see, it is interesting as now we can go for larger graphs and consume little memory.
comment:7 Changed 14 months ago by
 Commit changed from e29852c6fa0651426ed4d1cef346946446a23ee3 to adb47288348163272b7766e65dffc76dabfecb2b
Branch pushed to git repo; I updated commit sha1. New commits:
adb4728  method added for weighted graphs

comment:8 followup: ↓ 10 Changed 14 months ago by
 Description modified (diff)
 I have one question, why bellmanford is not an option for algorithm in
wiener_index
,shortest_path_all_pairs
etc.
 Also, due to use of
correct_type
inshortest_paths
,johnson_shortest_paths
,floyd_warshall_shortest_path
inboost_graph.pyx
. There is nonuniformity in output. For e.g. (20, 20.0 etc). I propose we should open another ticket with the purpose of removingcorrect_type
code (as it generally fails, discussed in comment 17 of #30188) and modify affected doctests.
Best
Vipul
comment:9 Changed 14 months ago by
 Keywords gsoc2020 added
comment:10 in reply to: ↑ 8 ; followup: ↓ 12 Changed 14 months ago by
Replying to ghvipul79321:
 I have one question, why bellmanford 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
inshortest_paths
,johnson_shortest_paths
,floyd_warshall_shortest_path
inboost_graph.pyx
. There is nonuniformity in output. For e.g. (20, 20.0 etc). I propose we should open another ticket with the purpose of removingcorrect_type
code (as it generally fails, discussed in comment 17 of #30188) and modify affected doctests.
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.
comment:11 Changed 14 months ago by
 Commit changed from adb47288348163272b7766e65dffc76dabfecb2b to b2a415512e32d32fe0523dd9f404bc1fa9a3f183
Branch pushed to git repo; I updated commit sha1. New commits:
b2a4155  made doc test use boost, added bellmanford in algorithm list

comment:12 in reply to: ↑ 10 ; followup: ↓ 13 Changed 14 months ago by
Replying to dcoudert:
Are you sure it's always failing ?
It fails for this basic scenario when edge weights are both integer and noninteger. 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) <ipythoninput4ca5ef018db1e> in <module>() > 1 shortest_paths(G,Integer(0)) /home/vipul/sage/local/lib/python3.7/sitepackages/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/sitepackages/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/sitepackages/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 nonintegral float to integer") 687 688 elif isinstance(x, pari_gen): TypeError: Cannot convert nonintegral 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 nonrational 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
comment:13 in reply to: ↑ 12 ; followup: ↓ 15 Changed 14 months ago by
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 nonrational edge weights (pi or e) and it gave ans as double approximation, which is better than nothing. See this, for examplesage: 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='FloydWarshallPython') ({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='FloydWarshallPython')  TypeError Traceback (most recent call last) <ipythoninput8e3251b3d7fb4> in <module>() > 1 G.wiener_index(by_weight=True, algorithm='FloydWarshallPython') /Users/dcoudert/sage/local/lib/python3.7/sitepackages/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 /
comment:14 Changed 14 months ago by
 Commit changed from b2a415512e32d32fe0523dd9f404bc1fa9a3f183 to 736f3dfb36b7ad4293fb6043131b2ea0e5095ac2
Branch pushed to git repo; I updated commit sha1. New commits:
736f3df  / added instead of //

comment:15 in reply to: ↑ 13 Changed 14 months ago by
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.
comment:16 Changed 14 months ago by
 Commit changed from 736f3dfb36b7ad4293fb6043131b2ea0e5095ac2 to 4067d78662a268aa658a65bb43d3c873f7154218
comment:17 Changed 14 months ago by
I rebased on last beta, fixed merge conflicts, and did a minor correction. We are almost done.
comment:18 Changed 14 months ago by
 Commit changed from 4067d78662a268aa658a65bb43d3c873f7154218 to c751ae4abcae024ab2b754523003539a3d95d2fe
Branch pushed to git repo; I updated commit sha1. New commits:
c751ae4  trac #30247: fix docbuild

comment:19 Changed 14 months ago by
I slightly changed the documentation to fix issue reported by the patchbot. I removed the alternative definition that we don't use.
comment:20 Changed 14 months ago by
 Commit changed from c751ae4abcae024ab2b754523003539a3d95d2fe to fb3a4330998026304e5d63ae2233d79ae7dc0312
Branch pushed to git repo; I updated commit sha1. New commits:
fb3a433  trac #30247: improve type of returned value

comment:21 Changed 14 months ago by
In order to fix the doctest errors reported by the patchbot, I improved the handling of returned value. Now we get an integer value whenever possible.
comment:22 Changed 13 months ago by
 Cc ghkliem added
For me this ticket is good to go, but we need an external opinion / reviewer. Thanks.
comment:23 Changed 13 months ago by
 There are some alignment issues and I would propose something like this:
 raise RuntimeError("Dijkstra algorithm does not "  "work with negative weights, "  "use BellmanFord instead") + raise RuntimeError("Dijkstra algorithm does not " + "work with negative weights, " + "use BellmanFord instead")
raise RuntimeError("Dijkstra algorithm does not "  "work with negative weights, " + "work with negative weights, " "use BellmanFord instead")
WI = wiener_index(self, algorithm=algorithm, + weight_function=weight_function, + check_weight=check_weight)  weight_function=weight_function,  check_weight=check_weight)
elif (not self.is_connected()  or (self.is_directed() and not self.is_strongly_connected())): + or (self.is_directed() and not self.is_strongly_connected())): from sage.rings.infinity import Infinity
 distances = self.shortest_path_all_pairs(by_weight=by_weight,  algorithm=algorithm, weight_function=weight_function,  check_weight=check_weight)[0] + distances = self.shortest_path_all_pairs( + by_weight=by_weight, algorithm=algorithm, + weight_function=weight_function, check_weight=check_weight)[0]
 It would be nice to doctest the error messages (running Dijkstra with negative weights, BellmanFord with negative cycle, unknown algorithm, empty or one element graph).
 Is the Wiener index really undefined for an empty or one element graph. Shouldn't it be rather
0
?
if WI in QQ:
. This doesn't appear to be a good check to me:sage: float(2.sqrt()) in QQ True
So I think this will always return a rational? It seems like you excluded
Dijkstra_NetworkX
from the party. Does it perform much worse thanDijkstra_Boost
? It would also be memory efficient, if you skip the part of creating the double dictionary and then summing it up.
comment:24 Changed 13 months ago by
 Commit changed from fb3a4330998026304e5d63ae2233d79ae7dc0312 to 49472e3823a9aeed671f9a662a1cc72831396ab2
comment:25 Changed 13 months ago by
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) <ipythoninput40fae33b2819e> in <module> > 1 networkx.wiener_index(gnx) ~/sage/local/lib/python3.7/sitepackages/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/sitepackages/decorator.py:decoratorgen299> in is_connected(G) ~/sage/local/lib/python3.7/sitepackages/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/sitepackages/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 toif 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?).
comment:26 Changed 13 months ago by
 Commit changed from 49472e3823a9aeed671f9a662a1cc72831396ab2 to 8bbf19559e6033ede935fd8d32a3e3cecd606453
Branch pushed to git repo; I updated commit sha1. New commits:
8bbf195  trac #30247: set wiener index of one vertex graph to 0

comment:27 Changed 13 months ago by
I let wiener index of empty graph undefined and set the 0 the wiener index of one vertex graphs.
comment:28 Changed 13 months ago by
 Commit changed from 8bbf19559e6033ede935fd8d32a3e3cecd606453 to bfc181fbde45e92fb292413015b4f44d19603a95
Branch pushed to git repo; I updated commit sha1. New commits:
bfc181f  trac #30247: catch new exception appearing with boost 1.7.3

comment:29 Changed 13 months ago by
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 BellmanFord 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/sitepackages/sage/doctest/forker.py", line 715, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/dcoudert/sage/local/lib/python3.7/sitepackages/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
comment:30 Changed 13 months ago by
 Status changed from needs_review to needs_work
Build error
[sagelib9.2.beta8] /srv/public/kliem/sage/local/include/boost/mpl/assert.hpp:188:21: warning: unnecessary parentheses in declaration of ‘assert_arg’ [Wparentheses] [sagelib9.2.beta8] failed ************ (Pred::************ [sagelib9.2.beta8] ^ [sagelib9.2.beta8] /srv/public/kliem/sage/local/include/boost/mpl/assert.hpp:193:21: warning: unnecessary parentheses in declaration of ‘assert_not_arg’ [Wparentheses] [sagelib9.2.beta8] failed ************ (boost::mpl::not_<Pred>::************ [sagelib9.2.beta8] ^ [sagelib9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c: In function ‘__pyx_f_4sage_6graphs_19distances_all_pairs_diameter_DHV’: [sagelib9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:843:40: warning: ‘__pyx_v_idx’ may be used uninitialized in this function [Wmaybeuninitialized] [sagelib9.2.beta8] #define likely(x) __builtin_expect(!!(x), 1) [sagelib9.2.beta8] ^ [sagelib9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:16252:8: note: ‘__pyx_v_idx’ was declared here [sagelib9.2.beta8] size_t __pyx_v_idx; [sagelib9.2.beta8] ^~~~~~~~~~~ [sagelib9.2.beta8] In file included from build/cythonized/sage/graphs/base/boost_graph.cpp:668: [sagelib9.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)’: [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:26: error: ‘wrapexcept’ in namespace ‘boost’ does not name a template type [sagelib9.2.beta8] } catch (boost::wrapexcept<boost::negative_edge> e) { [sagelib9.2.beta8] ^~~~~~~~~~ [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:36: error: expected ‘)’ before ‘<’ token [sagelib9.2.beta8] } catch (boost::wrapexcept<boost::negative_edge> e) { [sagelib9.2.beta8] ~ ^ [sagelib9.2.beta8] ) [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:36: error: expected ‘{’ before ‘<’ token [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:36: error: expected primaryexpression before ‘<’ token [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:57: error: expected primaryexpression before ‘>’ token [sagelib9.2.beta8] } catch (boost::wrapexcept<boost::negative_edge> e) { [sagelib9.2.beta8] ^ [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_interface.cpp:245:59: error: ‘e’ was not declared in this scope [sagelib9.2.beta8] } catch (boost::wrapexcept<boost::negative_edge> e) { [sagelib9.2.beta8] ^ [sagelib9.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*)’: [sagelib9.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’ [Wsigncompare] [sagelib9.2.beta8] for (__pyx_t_16 = 0; __pyx_t_16 < __pyx_t_15; __pyx_t_16+=1) { [sagelib9.2.beta8] ~~~~~~~~~~~^~~~~~~~~~~~ [sagelib9.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*)’: [sagelib9.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’ [Wsigncompare] [sagelib9.2.beta8] for (__pyx_t_14 = 0; __pyx_t_14 < __pyx_t_17; __pyx_t_14+=1) { [sagelib9.2.beta8] ~~~~~~~~~~~^~~~~~~~~~~~ [sagelib9.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’ [Wsigncompare] [sagelib9.2.beta8] for (__pyx_t_35 = __pyx_t_33; __pyx_t_35 < __pyx_t_34; __pyx_t_35+=1) { [sagelib9.2.beta8] ~~~~~~~~~~~^~~~~~~~~~~~ [sagelib9.2.beta8] In file included from build/cythonized/sage/graphs/base/boost_graph.cpp:668: [sagelib9.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]’: [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:11682:82: required from here [sagelib9.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 [Wcatchvalue=] [sagelib9.2.beta8] } catch (boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<boost::negative_edge> > e) { [sagelib9.2.beta8] ^~~~~ [sagelib9.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]’: [sagelib9.2.beta8] build/cythonized/sage/graphs/base/boost_graph.cpp:11746:82: required from here [sagelib9.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 [Wcatchvalue=] [sagelib9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c: In function ‘__pyx_pw_4sage_6graphs_19distances_all_pairs_9eccentricity’: [sagelib9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:843:40: warning: ‘__pyx_v_idx’ may be used uninitialized in this function [Wmaybeuninitialized] [sagelib9.2.beta8] #define likely(x) __builtin_expect(!!(x), 1) [sagelib9.2.beta8] ^ [sagelib9.2.beta8] build/cythonized/sage/graphs/distances_all_pairs.c:12598:8: note: ‘__pyx_v_idx’ was declared here [sagelib9.2.beta8] size_t __pyx_v_idx; [sagelib9.2.beta8] ^~~~~~~~~~~ [sagelib9.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,rpathlink,/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.linuxx86_643.7/build/cythonized/sage/graphs/distances_all_pairs.o L/srv/public/kliem/sage/local/lib lgmp lpython3.7m o build/lib.linuxx86_643.7/sage/graphs/distances_all_pairs.cpython37mx86_64linuxgnu.so lpari
comment:31 Changed 13 months ago by
 Commit changed from bfc181fbde45e92fb292413015b4f44d19603a95 to acf7647264eef0b9909fa8c9955a2a4d874f53c4
Branch pushed to git repo; I updated commit sha1. New commits:
acf7647  trac #30247: improved checking of weights and algorithms

comment:32 Changed 13 months ago by
 Status changed from needs_work to positive_review
This version is much simpler, avoids modifying the boost interface, and I expect more robust.
comment:33 Changed 13 months ago by
 Status changed from positive_review to needs_work
comment:34 Changed 13 months ago by
 Status changed from needs_work to needs_review
oups, wrong button ;)
comment:35 Changed 13 months ago by
 Status changed from needs_review to positive_review
comment:36 Changed 13 months ago by
 Reviewers set to Vipul Gupta
comment:37 Changed 13 months ago by
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.
comment:38 Changed 13 months ago by
Thank you. Do not hesitate to add your name as reviewer.
comment:39 Changed 13 months ago by
 Reviewers changed from Vipul Gupta to Vipul Gupta, Jonathan Kliem
comment:40 Changed 13 months ago by
 Branch changed from public/graphs/30247_wiener to acf7647264eef0b9909fa8c9955a2a4d874f53c4
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #30247: better wiener index