Opened 23 months ago
Closed 22 months ago
#30039 closed enhancement (fixed)
Implement weighted version of 2Dsweep and DiFUB
Reported by:  ghvipul79321  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description
This ticket aims to implement weighted version of 2Dsweep
and DiFUB
Change History (42)
comment:1 Changed 23 months ago by
 Branch set to public/graphs/30039_weighted_difub
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 23 months ago by
 Commit set to 2d53b3edca6ef352aeaf12b4ff1221ac6b18f534
comment:3 in reply to: ↑ 2 Changed 23 months ago by
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 followup: ↓ 5 Changed 23 months ago by
You don't compute distances from antipodes...
comment:5 in reply to: ↑ 4 Changed 23 months ago by
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
I missed these lines
+ source_1 = antipode_1 + source_2 = antipode_2
so it's ok.
comment:7 followup: ↓ 8 Changed 23 months ago by
 Commit changed from 2d53b3edca6ef352aeaf12b4ff1221ac6b18f534 to 867a0a8dd653dc70b0280ec1f8532a781ece1a95
Branch pushed to git repo; I updated commit sha1. New commits:
867a0a8  weighted difub added and exposed in digraph.py

comment:8 in reply to: ↑ 7 Changed 23 months ago by
comment:9 followup: ↓ 11 Changed 23 months ago by
 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
 Commit changed from 867a0a8dd653dc70b0280ec1f8532a781ece1a95 to 14e44ec709d3daf6bb3b849febb419605a400d57
Branch pushed to git repo; I updated commit sha1. New commits:
14e44ec  minor changes in documentation

comment:11 in reply to: ↑ 9 Changed 23 months ago by
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 followup: ↓ 14 Changed 23 months ago by
have also a look at the errors reported by the patchbot.
comment:13 Changed 23 months ago by
 Commit changed from 14e44ec709d3daf6bb3b849febb419605a400d57 to 4fe3d4ac2c6bcfe8891bea8b2accfa2237a2c591
Branch pushed to git repo; I updated commit sha1. New commits:
4fe3d4a  Patchbot issues fixed

comment:14 in reply to: ↑ 12 Changed 23 months ago by
comment:15 followup: ↓ 16 Changed 23 months ago by
actually, one of these issue should be fixed in #29422, right ?
comment:16 in reply to: ↑ 15 Changed 23 months ago by
comment:17 followups: ↓ 18 ↓ 19 Changed 23 months ago by
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
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@vipulPredatorG3572:~/sage$ ./sage t src/sage/graphs/base/boost_graph.pyx Running doctests with ID 202007081324510d1b09f6. Git branch: weighted_difub Using optional=build,dochtml,memlimit,python_openid,sage,speaklater Doctesting 1 file. sage t warnlong 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.
comment:19 in reply to: ↑ 17 Changed 23 months ago by
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
andDiFUB
.
Ok
comment:20 Changed 23 months ago by
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) <ipythoninput6283ef9f979bc> in <module>() > 1 diameter(G, algorithm='2Dsweep', weight_function=lambda e:e[Integer(2)]) /Users/dcoudert/sage/local/lib/python3.7/sitepackages/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/sitepackages/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/sitepackages/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 == 'BellmanFord': > 1849 sig_on() 1850 result_1 = rev_g_boost.bellman_ford_shortest_paths(source_1) 1851 sig_off() SignalError: Segmentation fault
comment:21 followup: ↓ 22 Changed 23 months ago by
 Commit changed from 4fe3d4ac2c6bcfe8891bea8b2accfa2237a2c591 to e9a452008ac35064258f7889851d72ac640eb083
comment:22 in reply to: ↑ 21 Changed 23 months ago by
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
comment:23 Changed 23 months ago by
 Commit changed from e9a452008ac35064258f7889851d72ac640eb083 to f7e1ad5313c6e861f8bcdd06d62ce76e96492154
comment:24 Changed 23 months ago by
check that.
comment:25 Changed 23 months ago by
 Commit changed from f7e1ad5313c6e861f8bcdd06d62ce76e96492154 to d033760a973be8fd73d49377c4a00f75ea6f40e5
Branch pushed to git repo; I updated commit sha1. New commits:
d033760  minor improvements

comment:26 Changed 23 months ago by
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/sitepackages/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 followup: ↓ 28 Changed 23 months ago by
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
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
 Commit changed from d033760a973be8fd73d49377c4a00f75ea6f40e5 to 9b6163b9d58dcd0bc917a34d858d4cfe38f4f9d1
Branch pushed to git repo; I updated commit sha1. New commits:
9b6163b  trac #30039: fix error message and some compilation warnings

comment:30 followup: ↓ 33 Changed 23 months ago by
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#errorreturnvalues for more details.
On the way, I fixed some compilation warnings (got bored of them).
comment:31 Changed 23 months ago by
 Reviewers set to David Coudert
comment:32 Changed 23 months ago by
 Commit changed from 9b6163b9d58dcd0bc917a34d858d4cfe38f4f9d1 to 002b8c2ea12b30b05231c35fe6a39997f422d5a3
Branch pushed to git repo; I updated commit sha1. New commits:
002b8c2  doc test added

comment:33 in reply to: ↑ 30 Changed 23 months ago by
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#errorreturnvalues 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
 Status changed from needs_review to positive_review
LGTM. Successfully tested over 9.2.beta5.
comment:35 Changed 22 months ago by
 Status changed from positive_review to needs_work
a small edit is needed.
comment:36 Changed 22 months ago by
 Commit changed from 002b8c2ea12b30b05231c35fe6a39997f422d5a3 to f6db6a55c45606f41d2f5abf997bc66875673f10
Branch pushed to git repo; I updated commit sha1. New commits:
f6db6a5  trac #30039: use edges instead of edge_iterator

comment:37 Changed 22 months ago by
 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
 Status changed from positive_review to needs_work
Merge conflict
comment:39 followup: ↓ 40 Changed 22 months ago by
 Commit changed from f6db6a55c45606f41d2f5abf997bc66875673f10 to 7bcd9db9dd80f8902a6bc938b34486a6801ac7c0
Branch pushed to git repo; I updated commit sha1. New commits:
7bcd9db  merge conflict fixed

comment:40 in reply to: ↑ 39 Changed 22 months ago by
 Status changed from needs_work to needs_review
comment:42 Changed 22 months ago by
 Branch changed from public/graphs/30039_weighted_difub to 7bcd9db9dd80f8902a6bc938b34486a6801ac7c0
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
code added
documentation added
trac #29422: merged with 9.2.beta2
trac #29422: review commit
Exposed in digraph.py and fixed patchbots issues
weighted 2Dsweep added