memory efficient implementation of Wiener index

dcoudert commented 3 years ago

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 commented 3 years ago

Branch: public/graphs/30247_wiener

dcoudert commented 3 years ago

Commit: 6452967

dcoudert commented 3 years ago

New commits:

6452967 trac #30247: better wiener index

dcoudert commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

e29852c trac #30247: small corrections for directed graphs

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 6452967 to e29852c

dcoudert commented 3 years ago

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.

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

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 commented 3 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from e29852c to adb4728

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

adb4728 method added for weighted graphs

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

Description changed:

--- 
+++ 
@@ -1,2 +1,2 @@
-We improve the implementation of Wiener index for unweighted graphs by avoiding to compute and store into memory the full distance matrix. This way we can compute this index for larger graphs.
+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.

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

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 #30188) and modify affected doc-tests.

Best

Vipul

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

Changed keywords from none to gsoc2020

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

Changed author from David Coudert to David Coudert, Vipul Gupta

dcoudert commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from adb4728 to b2a4155

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

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 commented 3 years ago

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 /

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from b2a4155 to 736f3df

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

736f3df / added instead of //

09ac5a22-6a87-4290-8c34-5c8dd760bfaf commented 3 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 736f3df to 4067d78

dcoudert commented 3 years ago

comment:17

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

c751ae4 trac #30247: fix docbuild

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 4067d78 to c751ae4

dcoudert commented 3 years ago

comment:19

I slightly changed the documentation to fix issue reported by the patchbot. I removed the alternative definition that we don't use.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from c751ae4 to fb3a433

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

fb3a433 trac #30247: improve type of returned value

dcoudert commented 3 years ago

comment:21

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.

dcoudert commented 3 years ago

comment:22

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

kliem commented 3 years ago

comment:23

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from fb3a433 to 49472e3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

`0c18eb3`	`trac #30247: merged with 9.2.beta8`
`49472e3`	`trac #30247: implement review comments`

dcoudert commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 49472e3 to 8bbf195

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

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

dcoudert commented 3 years ago

comment:27

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

bfc181f trac #30247: catch new exception appearing with boost 1.7.3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 8bbf195 to bfc181f

dcoudert commented 3 years ago

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 commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from bfc181f to acf7647

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

acf7647 trac #30247: improved checking of weights and algorithms

dcoudert commented 3 years ago

comment:32

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

dcoudert commented 3 years ago

comment:34

oups, wrong button ;)

dcoudert commented 3 years ago

Reviewer: Vipul Gupta

kliem commented 3 years ago

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.

sagemath / sage

memory efficient implementation of Wiener index #30247