Implement weighted version of 2Dsweep and DiFUB

[gh-vipul79321]

This ticket aims to implement weighted version of 2Dsweep and DiFUB

[git]

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

​ef68ef3	code added
​8546f52	documentation added
​0c73b63	trac #29422: merged with 9.2.beta2
​eb335a5	trac #29422: review commit
​d0697f8	Exposed in digraph.py and fixed patchbots issues
​2d53b3e	weighted 2Dsweep added

[gh-vipul79321]

Replying to git:

​2d53b3e

weighted 2Dsweep added

Hello David,

I have added weighted version of 2Dsweep and wrapper method for diameter computation similar to in distances_all_pairs.pyx. Its not final yet, I just wanted to keep you updated with how I have decided to organize it.

Kindly take a look at it. Any suggestions will be helpful.

I will hopefully complete the weighted version of DiFUB by tomorrow.

Vipul

[dcoudert]

You don't compute distances from antipodes...

[gh-vipul79321]

Replying to dcoudert:

You don't compute distances from antipodes...

I didnt quite understand what you are saying, are you suggesting to stop 2Dsweep after 2nd step. But i would like to mention that we have followed the same steps in unweighted version of 2Dsweep.

Sorry to bother you.. But can you please expalin you are saying.

[dcoudert]

I missed these lines

+    source_1 = antipode_1
+    source_2 = antipode_2

so it's ok.

[git]

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

​867a0a8

weighted difub added and exposed in digraph.py

[gh-vipul79321]

Replying to git:

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

​867a0a8

weighted difub added and exposed in digraph.py

P.S. - I have made the changes in eccentricity method in digraph.py similar to graph.py

[dcoudert]

-    Returns lower bound on the diamter of weighted digraph using the weighted
-    version of the algorithm proposed in [Broder2000]_.
+    Return a lower bound on the diameter of `G`.
+    
+    This method implements the weighted version of the algorithm proposed
+    in [Broder2000]_ to compute a lower bound of the weighted digraph `G`.

This should work and be slightly faster (ok, minor improvement)

-        order_1.push_back(pair[double, v_index](distances[v], v))
+        order_1.emplace_back(distances[v], v)

-            computed diameter. They also works with negative weight, if there is
+            computed diameter. They also work with negative weight, if there is

The documentation you added in digraph.py suggests that we don't have a basic method for weighted digraphs, but we do.

In the comparison of methods, you can compare DiFUB with any exact algorithm based on eccentricity.

[git]

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

​14e44ec

minor changes in documentation

[gh-vipul79321]

Replying to dcoudert:

This should work and be slightly faster (ok, minor improvement)

-        order_1.push_back(pair[double, v_index](distances[v], v))
+        order_1.emplace_back(distances[v], v)

This threw an error, so I kept the previous version.

The documentation you added in digraph.py suggests that we don't have a basic method for weighted digraphs, but we do.

I have made changes for that, but i am not sure are those changes sufficient?

In the comparison of methods, you can compare DiFUB with any exact algorithm based on eccentricity.

Done.

[dcoudert]

have also a look at the errors reported by the patchbot.

[git]

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

​4fe3d4a

Patchbot issues fixed

[gh-vipul79321]

Replying to dcoudert:

have also a look at the errors reported by the patchbot.

Done

[dcoudert]

actually, one of these issue should be fixed in #29422, right ?

[gh-vipul79321]

Replying to dcoudert:

actually, one of these issue should be fixed in #29422, right ?

Yeah, i will do the same update there too.

[dcoudert]

While running doctests on the graph module, I get the following error.

sage -t src/sage/graphs/base/boost_graph.pyx
**********************************************************************
File "src/sage/graphs/base/boost_graph.pyx", line 2121, in sage.graphs.base.boost_graph.?
Failed example:
    diameter(G, algorithm='DiFUB', weight_function=lambda e:e[2])
Expected:
    2.0
Got:
    Traceback (most recent call last):
      File "sage/graphs/base/boost_graph.pyx", line 1869, in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:20737)
    cysignals.signals.SignalError: Segmentation fault
    Exception ignored in: 'sage.graphs.base.boost_graph.diameter_DiFUB'
    Traceback (most recent call last):
      File "sage/graphs/base/boost_graph.pyx", line 1869, in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:20737)
    cysignals.signals.SignalError: Segmentation fault
    0.0

Also, you could add specific doctests for 2Dsweep and DiFUB.

[gh-vipul79321]

Replying to dcoudert:

While running doctests on the graph module, I get the following error.

sage -t src/sage/graphs/base/boost_graph.pyx
**********************************************************************
File "src/sage/graphs/base/boost_graph.pyx", line 2121, in sage.graphs.base.boost_graph.?
Failed example:
    diameter(G, algorithm='DiFUB', weight_function=lambda e:e[2])
Expected:
    2.0
Got:
    Traceback (most recent call last):
      File "sage/graphs/base/boost_graph.pyx", line 1869, in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:20737)
    cysignals.signals.SignalError: Segmentation fault
    Exception ignored in: 'sage.graphs.base.boost_graph.diameter_DiFUB'
    Traceback (most recent call last):
      File "sage/graphs/base/boost_graph.pyx", line 1869, in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:20737)
    cysignals.signals.SignalError: Segmentation fault
    0.0

That's weird, when ran doctest on my system it passed with no error. I have checked it again. Still no problem.

sage: from sage.graphs.base.boost_graph import diameter
sage: G = DiGraph([(0,1,2), (1,0,-1)])
sage: diameter(G, algorithm='DiFUB')
1.0
sage: diameter(G, algorithm='DiFUB', weight_function=lambda e:e[2])
2.0

---

vipul@vipul-Predator-G3-572:~/sage$ ./sage -t src/sage/graphs/base/boost_graph.pyx
Running doctests with ID 2020-07-08-13-24-51-0d1b09f6.
Git branch: weighted_difub
Using --optional=build,dochtml,memlimit,python_openid,sage,speaklater
Doctesting 1 file.
sage -t --warn-long 45.7 src/sage/graphs/base/boost_graph.pyx
    [135 tests, 0.37 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.4 seconds
    cpu time: 0.4 seconds
    cumulative wall time: 0.4 seconds

P.S - I am currently on latest beta release.

[gh-vipul79321]

Replying to dcoudert:

While running doctests on the graph module, I get the following error.

sage -t src/sage/graphs/base/boost_graph.pyx
**********************************************************************
File "src/sage/graphs/base/boost_graph.pyx", line 2121, in sage.graphs.base.boost_graph.?
Failed example:
    diameter(G, algorithm='DiFUB', weight_function=lambda e:e[2])
Expected:
    2.0
Got:
    Traceback (most recent call last):
      File "sage/graphs/base/boost_graph.pyx", line 1869, in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:20737)
    cysignals.signals.SignalError: Segmentation fault
    Exception ignored in: 'sage.graphs.base.boost_graph.diameter_DiFUB'

One more thing, I would like to ask is why the execption is being ignored. Why it is not raising exception in that method itself.

Also, you could add specific doctests for 2Dsweep and DiFUB.

Ok

[dcoudert]

This is due to default value of antipode_2 in 2Dsweep. Indeed, to find the antipode, you initialize LB_2 = 0. But with this graph, the eccentricity of vertex 1 is -1. So antipode_2 stays at the default value (depends on the system).

If I change the weights, I can get the error with antipode_1

sage: G = DiGraph([(0,1,-1), (1,0,2)])
sage: diameter(G, algorithm='2Dsweep', weight_function=lambda e:e[2])
---------------------------------------------------------------------------
SignalError                               Traceback (most recent call last)
<ipython-input-6-283ef9f979bc> in <module>()
----> 1 diameter(G, algorithm='2Dsweep', weight_function=lambda e:e[Integer(2)])

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.diameter (build/cythonized/sage/graphs/base/boost_graph.cpp:23444)()
   2077     return LB
   2078 
-> 2079 cpdef diameter(G, algorithm=None, source=None,
   2080                weight_function=None, check_weight=True):
   2081     r"""

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.diameter (build/cythonized/sage/graphs/base/boost_graph.cpp:23145)()
   2188 
   2189     if algorithm == '2Dsweep':
-> 2190         LB = diameter_lower_bound_2Dsweep(g_boost, rev_g_boost,
   2191                                             isource, algo)[0]
   2192 

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:20568)()
   1847     # maximum backward distance. LB_1 will be Backward eccentricity of source_1.
   1848     if algorithm == 'Bellman-Ford':
-> 1849         sig_on()
   1850         result_1 = rev_g_boost.bellman_ford_shortest_paths(source_1)
   1851         sig_off()

SignalError: Segmentation fault

[git]

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

​7a8552f	Merge branch 'public/graphs/30039_weighted_difub' of git://trac.sagemath.org/sage into weighted_difub
​e9a4520	Fixed segmentation fault in 2dsweep

[gh-vipul79321]

Replying to git:

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

​e9a4520

Fixed segmentation fault in 2dsweep

I have added equality while looking for antipode. So that atleast one vertex will be made antipode and i think it will solve it.

Please check that it works (because i am unable to confirm it).

Vipul

[git]

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

​09dc6be	trac #30039: merged with 9.2.beta4
​f7e1ad5	trac 30039: review commit

[dcoudert]

check that.

[git]

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

​d033760

minor improvements

[gh-vipul79321]

sage: G = DiGraph([(0,1,-2), (1,0,1)])
sage: G.diameter(by_weight=True)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:22068)()
   2012         sig_off()
   2013     if not result_1.distances.size():
-> 2014         raise ValueError("the graph contains a negative cycle")
   2015 
   2016     LB_1 = -sys.float_info.max

ValueError: the graph contains a negative cycle
Exception ignored in: 'sage.graphs.base.boost_graph.diameter_DiFUB'
Traceback (most recent call last):
  File "sage/graphs/base/boost_graph.pyx", line 2014, in sage.graphs.base.boost_graph.diameter_lower_bound_2Dsweep (build/cythonized/sage/graphs/base/boost_graph.cpp:22068)
ValueError: the graph contains a negative cycle
0.0

Is there anyway we can properly get an error and not printing 0.0 ?

[dcoudert]

I don't understand why the 0.0 is printed. It should not be the case. I don't understand either why it is written that an exception is ignored in DiFUB. Which one ? the issue occurs in 2Dsweep. Have you localized when is 0.0 returned ?

[gh-vipul79321]

Replying to dcoudert:

Have you localized when is 0.0 returned ?

It will occur only via DiFUB and this will occur only when there is an error raised in 2DSweep.

I am also unable to understand it properly since it is receiving error, instead of terminating right then, it is ignoring it and sending garbage value stored in LB(on my system it is 0.0) without executing remaining part of code.

I am guessing if you run this example on your system you might encounter different value than 0.0(as it has previously happened in case of antipode).

[git]

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

​9b6163b

trac #30039: fix error message and some compilation warnings

[dcoudert]

got it ! the error was not correctly transmitted to caller method. So the solution was:

-                           str algorithm):
+                           str algorithm) except? -1:

See ​https://cython.readthedocs.io/en/latest/src/userguide/language_basics.html#error-return-values for more details.

On the way, I fixed some compilation warnings (got bored of them).

[git]

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

​002b8c2

doc test added

[gh-vipul79321]

Replying to dcoudert:

got it ! the error was not correctly transmitted to caller method. So the solution was:

-                           str algorithm):
+                           str algorithm) except? -1:

See ​https://cython.readthedocs.io/en/latest/src/userguide/language_basics.html#error-return-values for more details.

Ok.

On the way, I fixed some compilation warnings (got bored of them).

Well, that's some relief to eyes.

I have added a doctest for DiFUB and I think there is nothing more to do.

[dcoudert]

LGTM. Successfully tested over 9.2.beta5.

[dcoudert]

a small edit is needed.

[git]

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

​f6db6a5

trac #30039: use edges instead of edge_iterator

[dcoudert]

small modification to use .edges instead of edge_iterator (see #30145).

[vbraun]

Merge conflict

[git]

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

​7bcd9db

merge conflict fixed

[gh-vipul79321]

Replying to git:

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

​7bcd9db

merge conflict fixed

Solved merge conflict in boost_graph.pyx.

[dcoudert]

LGTM.