#30247 closed enhancement (fixed)

memory efficient implementation of Wiener index

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords: gsoc2020
Cc: gh-vipul79321, gh-kliem 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:

Status badges

Description (last modified by gh-vipul79321)

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 dcoudert

  • Branch set to public/graphs/30247_wiener
  • Cc gh-vipul79321 added
  • Commit set to 6452967541645e827e3bf54b6bb0e013d2dd0c77
  • Status changed from new to needs_review

New commits:

6452967trac #30247: better wiener index

comment:2 Changed 14 months ago by dcoudert

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 git

  • Commit changed from 6452967541645e827e3bf54b6bb0e013d2dd0c77 to e29852c6fa0651426ed4d1cef346946446a23ee3

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

e29852ctrac #30247: small corrections for directed graphs

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

comment:5 in reply to: ↑ 4 Changed 14 months ago by gh-vipul79321

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.

comment:6 Changed 14 months ago by dcoudert

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 git

  • Commit changed from e29852c6fa0651426ed4d1cef346946446a23ee3 to adb47288348163272b7766e65dffc76dabfecb2b

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

adb4728method added for weighted graphs

comment:8 follow-up: Changed 14 months ago by gh-vipul79321

  • Description modified (diff)
  • 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 #30188) and modify affected doc-tests.

Best

Vipul

comment:9 Changed 14 months ago by gh-vipul79321

  • Authors changed from David Coudert to David Coudert, Vipul Gupta
  • Keywords gsoc2020 added

comment:10 in reply to: ↑ 8 ; follow-up: Changed 14 months ago by dcoudert

Replying to gh-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 #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.

comment:11 Changed 14 months ago by git

  • Commit changed from adb47288348163272b7766e65dffc76dabfecb2b to b2a415512e32d32fe0523dd9f404bc1fa9a3f183

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

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

comment:12 in reply to: ↑ 10 ; follow-up: Changed 14 months ago by gh-vipul79321

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

comment:13 in reply to: ↑ 12 ; follow-up: Changed 14 months ago by dcoudert

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 /

comment:14 Changed 14 months ago by git

  • 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 gh-vipul79321

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 git

  • Commit changed from 736f3dfb36b7ad4293fb6043131b2ea0e5095ac2 to 4067d78662a268aa658a65bb43d3c873f7154218

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

673f863trac #30247: fix merge conflict with 9.2.beta7
4067d78trac #30247: minor corrections

comment:17 Changed 14 months ago by dcoudert

I rebased on last beta, fixed merge conflicts, and did a minor correction. We are almost done.

comment:18 Changed 14 months ago by git

  • Commit changed from 4067d78662a268aa658a65bb43d3c873f7154218 to c751ae4abcae024ab2b754523003539a3d95d2fe

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

c751ae4trac #30247: fix docbuild

comment:19 Changed 14 months ago by dcoudert

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 git

  • Commit changed from c751ae4abcae024ab2b754523003539a3d95d2fe to fb3a4330998026304e5d63ae2233d79ae7dc0312

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

fb3a433trac #30247: improve type of returned value

comment:21 Changed 14 months ago by dcoudert

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.

Last edited 14 months ago by dcoudert (previous) (diff)

comment:22 Changed 13 months ago by dcoudert

  • Cc gh-kliem added

For me this ticket is good to go, but we need an external opinion / reviewer. Thanks.

comment:23 Changed 13 months ago by gh-kliem

  • There are some alignment issues and I would propose something like this:
-                       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")
                         raise RuntimeError("Dijkstra algorithm does not "
-                                          "work with negative weights, "
+                                           "work with negative weights, "
                                            "use Bellman-Ford 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, Bellman-Ford 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 than Dijkstra_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 git

  • Commit changed from fb3a4330998026304e5d63ae2233d79ae7dc0312 to 49472e3823a9aeed671f9a662a1cc72831396ab2

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

0c18eb3trac #30247: merged with 9.2.beta8
49472e3trac #30247: implement review comments

comment:25 Changed 13 months ago by dcoudert

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

comment:26 Changed 13 months ago by git

  • Commit changed from 49472e3823a9aeed671f9a662a1cc72831396ab2 to 8bbf19559e6033ede935fd8d32a3e3cecd606453

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

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

comment:27 Changed 13 months ago by dcoudert

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 git

  • Commit changed from 8bbf19559e6033ede935fd8d32a3e3cecd606453 to bfc181fbde45e92fb292413015b4f44d19603a95

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

bfc181ftrac #30247: catch new exception appearing with boost 1.7.3

comment:29 Changed 13 months ago by dcoudert

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

comment:30 Changed 13 months ago by gh-kliem

  • Status changed from needs_review to needs_work

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

comment:31 Changed 13 months ago by git

  • Commit changed from bfc181fbde45e92fb292413015b4f44d19603a95 to acf7647264eef0b9909fa8c9955a2a4d874f53c4

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

acf7647trac #30247: improved checking of weights and algorithms

comment:32 Changed 13 months ago by dcoudert

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

  • Status changed from positive_review to needs_work

comment:34 Changed 13 months ago by dcoudert

  • Status changed from needs_work to needs_review

oups, wrong button ;)

comment:35 Changed 13 months ago by gh-vipul79321

  • Status changed from needs_review to positive_review

comment:36 Changed 13 months ago by dcoudert

  • Reviewers set to Vipul Gupta

comment:37 Changed 13 months ago by gh-kliem

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 dcoudert

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

comment:39 Changed 13 months ago by gh-kliem

  • Reviewers changed from Vipul Gupta to Vipul Gupta, Jonathan Kliem

comment:40 Changed 13 months ago by vbraun

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