#30039 closed enhancement (fixed)

Implement weighted version of 2Dsweep and DiFUB

Reported by: gh-vipul79321 Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords: gsoc2020
Cc: dcoudert Merged in:
Authors: Vipul Gupta Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 7bcd9db (Commits, GitHub, GitLab) Commit: 7bcd9db9dd80f8902a6bc938b34486a6801ac7c0
Dependencies: #29422 Stopgaps:

Status badges

Description

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

Change History (42)

comment:1 Changed 23 months ago by gh-vipul79321

  • Branch set to public/graphs/30039_weighted_difub
  • Status changed from new to needs_review

comment:2 follow-up: Changed 23 months ago by git

  • Commit set to 2d53b3edca6ef352aeaf12b4ff1221ac6b18f534

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

ef68ef3code added
8546f52documentation added
0c73b63trac #29422: merged with 9.2.beta2
eb335a5trac #29422: review commit
d0697f8Exposed in digraph.py and fixed patchbots issues
2d53b3e weighted 2Dsweep added

comment:3 in reply to: ↑ 2 Changed 23 months ago by 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

comment:4 follow-up: Changed 23 months ago by dcoudert

You don't compute distances from antipodes...

comment:5 in reply to: ↑ 4 Changed 23 months ago by 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.

comment:6 Changed 23 months ago by dcoudert

I missed these lines

+    source_1 = antipode_1
+    source_2 = antipode_2

so it's ok.

comment:7 follow-up: Changed 23 months ago by git

  • Commit changed from 2d53b3edca6ef352aeaf12b4ff1221ac6b18f534 to 867a0a8dd653dc70b0280ec1f8532a781ece1a95

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

867a0a8weighted difub added and exposed in digraph.py

comment:8 in reply to: ↑ 7 Changed 23 months ago by gh-vipul79321

Replying to git:

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

867a0a8weighted difub added and exposed in digraph.py

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

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

comment:10 Changed 23 months ago by git

  • Commit changed from 867a0a8dd653dc70b0280ec1f8532a781ece1a95 to 14e44ec709d3daf6bb3b849febb419605a400d57

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

14e44ecminor changes in documentation

comment:11 in reply to: ↑ 9 Changed 23 months ago by 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.

comment:12 follow-up: Changed 23 months ago by dcoudert

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

comment:13 Changed 23 months ago by git

  • Commit changed from 14e44ec709d3daf6bb3b849febb419605a400d57 to 4fe3d4ac2c6bcfe8891bea8b2accfa2237a2c591

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

4fe3d4aPatchbot issues fixed

comment:14 in reply to: ↑ 12 Changed 23 months ago by gh-vipul79321

Replying to dcoudert:

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

Done

comment:15 follow-up: Changed 23 months ago by dcoudert

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

comment:16 in reply to: ↑ 15 Changed 23 months ago by 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.

comment:17 follow-ups: Changed 23 months ago by 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.

comment:18 in reply to: ↑ 17 Changed 23 months ago by 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.

Last edited 23 months ago by gh-vipul79321 (previous) (diff)

comment:19 in reply to: ↑ 17 Changed 23 months ago by 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

comment:20 Changed 23 months ago by 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

comment:21 follow-up: Changed 23 months ago by git

  • Commit changed from 4fe3d4ac2c6bcfe8891bea8b2accfa2237a2c591 to e9a452008ac35064258f7889851d72ac640eb083

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

7a8552fMerge branch 'public/graphs/30039_weighted_difub' of git://trac.sagemath.org/sage into weighted_difub
e9a4520Fixed segmentation fault in 2dsweep

comment:22 in reply to: ↑ 21 Changed 23 months ago by gh-vipul79321

Replying to git:

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

e9a4520Fixed 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

comment:23 Changed 23 months ago by git

  • Commit changed from e9a452008ac35064258f7889851d72ac640eb083 to f7e1ad5313c6e861f8bcdd06d62ce76e96492154

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

09dc6betrac #30039: merged with 9.2.beta4
f7e1ad5trac 30039: review commit

comment:24 Changed 23 months ago by dcoudert

check that.

comment:25 Changed 23 months ago by git

  • Commit changed from f7e1ad5313c6e861f8bcdd06d62ce76e96492154 to d033760a973be8fd73d49377c4a00f75ea6f40e5

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

d033760minor improvements

comment:26 Changed 23 months ago by 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 ?

comment:27 follow-up: Changed 23 months ago by 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 ?

comment:28 in reply to: ↑ 27 Changed 23 months ago by 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).

comment:29 Changed 23 months ago by git

  • Commit changed from d033760a973be8fd73d49377c4a00f75ea6f40e5 to 9b6163b9d58dcd0bc917a34d858d4cfe38f4f9d1

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

9b6163btrac #30039: fix error message and some compilation warnings

comment:30 follow-up: Changed 23 months ago by 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).

comment:31 Changed 23 months ago by dcoudert

  • Reviewers set to David Coudert

comment:32 Changed 23 months ago by git

  • Commit changed from 9b6163b9d58dcd0bc917a34d858d4cfe38f4f9d1 to 002b8c2ea12b30b05231c35fe6a39997f422d5a3

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

002b8c2doc test added

comment:33 in reply to: ↑ 30 Changed 23 months ago by 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.

comment:34 Changed 23 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM. Successfully tested over 9.2.beta5.

comment:35 Changed 22 months ago by dcoudert

  • Status changed from positive_review to needs_work

a small edit is needed.

comment:36 Changed 22 months ago by git

  • Commit changed from 002b8c2ea12b30b05231c35fe6a39997f422d5a3 to f6db6a55c45606f41d2f5abf997bc66875673f10

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

f6db6a5trac #30039: use edges instead of edge_iterator

comment:37 Changed 22 months ago by dcoudert

  • Status changed from needs_work to positive_review

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

comment:38 Changed 22 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:39 follow-up: Changed 22 months ago by git

  • Commit changed from f6db6a55c45606f41d2f5abf997bc66875673f10 to 7bcd9db9dd80f8902a6bc938b34486a6801ac7c0

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

7bcd9dbmerge conflict fixed

comment:40 in reply to: ↑ 39 Changed 22 months ago by gh-vipul79321

  • Status changed from needs_work to needs_review

Replying to git:

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

7bcd9dbmerge conflict fixed

Solved merge conflict in boost_graph.pyx.

comment:41 Changed 22 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM.

comment:42 Changed 22 months ago by vbraun

  • Branch changed from public/graphs/30039_weighted_difub to 7bcd9db9dd80f8902a6bc938b34486a6801ac7c0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.