Opened 17 months ago
Closed 15 months ago
#29715 closed enhancement (fixed)
Radius computation for undirected graph using certificates
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:  2437136 (Commits, GitHub, GitLab)  Commit:  2437136be053d0ef9e44de79c0ed2cec512dbd4e 
Dependencies:  Stopgaps: 
Description
This ticket aims to implement radius computation method given in http://arxiv.org/abs/1803.04660
Change History (45)
comment:1 Changed 17 months ago by
 Branch set to u/ghvipul79321/ticket29715
 Dependencies set to #29660
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 17 months ago by
 Commit set to 49c60b69b893792fbb6262190fa66637b7a82caa
comment:3 in reply to: ↑ 2 Changed 17 months ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
bf852a4 radius, diameter, eccentricity, center, periphery moved to graph and digraph separately
9e2dcc8 unneccessary comments removed
49c60b6 added for unweighted graphs
The first two commits are from #29660.
Currently, it is for unweighted graph. And I havent modified radius method ingraph.py
yet, because it might cause merge conflict.
And also, any suggestion on documentation will be helpful
comment:4 followup: ↓ 6 Changed 17 months ago by
Several comments to start:
bitset_init
to a malloc, so it should be call only once. check filesrc/sage/data_structures/bitset.pxi
. and before returning the result, you must do
bitset_free
 to empty the bitset, use
bitset_zero
orbitset_clear
 all BFS call can be done inside the main loop. I don't see the need for starting computation before the loop.
 If needed, you can emulate a
do..while
loop using awhile True:
and a test at the end with a break or return statement.  You don't need to maintain sets K and L.
 It shall be more efficient to maintain the list of active vertices, i.e. for which the eccentricity is not proved yet.
 You could rename
min_L
andmin_K
asLB
andUB
to ease readability of the code ?
comment:5 Changed 17 months ago by
 Commit changed from 49c60b69b893792fbb6262190fa66637b7a82caa to aa2abc1f7380cbaccd0c79874e6f8415a466fa5e
Branch pushed to git repo; I updated commit sha1. New commits:
aa2abc1  fixed silly mistakes

comment:6 in reply to: ↑ 4 Changed 17 months ago by
Replying to dcoudert:
Several comments to start:
bitset_init
to a malloc, so it should be call only once. check filesrc/sage/data_structures/bitset.pxi
. and before returning the result, you must do
bitset_free
 to empty the bitset, use
bitset_zero
orbitset_clear
Didnt knew that. Fixed it.
 all BFS call can be done inside the main loop. I don't see the need for starting computation before the loop.
 If needed, you can emulate a
do..while
loop using awhile True:
and a test at the end with a break or return statement.
You are right. I dont know what was I thinking. Fixed it.
 You don't need to maintain sets K and L.
agreed
 It shall be more efficient to maintain the list of active vertices, i.e. for which the eccentricity is not proved yet.
I guess, we wont need this too.
 You could rename
min_L
andmin_K
asLB
andUB
to ease readability of the code ?
Done.
comment:7 Changed 16 months ago by
 In the tests, you have to be very careful with random graphs. May be it's not connected, or has a larger diameter, etc. I suggest to change the test as follows:
 use a smaller value of n, like 20 or 30
 use a smaller density like .3. .6 is for very dense graphs.
 don't print the result. Instead, call another algorithm (the basic one) and check that the results are the same. This is much more robust.
 some simple improvements
 if not n or n == 1: + if n <= 1:
 memset(ecc_lower_bound,0,n * sizeof(uint32_t)) + memset(ecc_lower_bound, 0, n * sizeof(uint32_t))
 if(ecc[source] == ecc_lower_bound[source]): + if ecc[source] == ecc_lower_bound[source]:
 when adding a comment at the end of a line, ensure to let 2 spaces. I don't remember if it's pep8 or something else, but it's apparently better.
 bitset_init(seen,n) # intializing bitset + bitset_init(seen,n) # intializing bitset
Along the code, you should add comments like:
 we take a vertex with minimum eccentricity lower bound and compute it's exact eccentricity
 if its eccentricity equals its lower bound, we found a vertex with minimum eccentricity, and so the radius
 otherwise, we take the vertex at largest distance from the current source, called the antipode, and use BFS distances from this antipode to improve eccentricity lower bounds.
And FYI, in this kind of algorithms, a vertex with small eccentricity helps reducing the upper bounds while a vertex with large eccentricity helps increasing lower bounds. That's why we don't use more the BFS from source here. We care only about lower bound.
Q: have you tested the algorithm on rather large graphs ? Do you agree that it's way faster than other algorithms ?
comment:8 Changed 16 months ago by
Yeah it works faster than other algorithms. Few examples are as follows
sage: from sage.graphs.distances_all_pairs import radius sage: G = graphs.BubbleSortGraph(7) sage: %time radius(G) CPU times: user 1.41 s, sys: 7.12 ms, total: 1.42 s Wall time: 1.42 s 21 sage: %time G.radius() CPU times: user 45.3 s, sys: 6.58 ms, total: 45.3 s Wall time: 45.3 s 21
sage: G = graphs.FoldedCubeGraph(13) sage: %time radius(G) CPU times: user 47.2 ms, sys: 0 ns, total: 47.2 ms Wall time: 46.6 ms 6 sage: %time G.radius() CPU times: user 1min 1s, sys: 3.15 ms, total: 1min 1s Wall time: 1min 1s 6
sage: G = graphs.RandomBicubicPlanar(400) sage: %time radius(G) CPU times: user 10.3 ms, sys: 0 ns, total: 10.3 ms Wall time: 9.91 ms 23 sage: %time G.radius() CPU times: user 538 ms, sys: 4 µs, total: 538 ms Wall time: 536 ms 23
sage: G = graphs.RandomGNP(1000,0.6) sage: %time radius(G) CPU times: user 181 ms, sys: 7.99 ms, total: 189 ms Wall time: 188 ms 2 sage: %time G.radius() CPU times: user 2min 9s, sys: 26 s, total: 2min 35s Wall time: 2min 35s 2
comment:9 Changed 16 months ago by
 Commit changed from aa2abc1f7380cbaccd0c79874e6f8415a466fa5e to b86ae754ade5a1b5ad7afcdc684d5d0a6485c52f
Branch pushed to git repo; I updated commit sha1. New commits:
b86ae75  comments updated

comment:10 followup: ↓ 12 Changed 16 months ago by
 Reviewers set to David Coudert
The default of this test is that soon it will compare the new algorithm with itself ;)
Currently, when calling G.radius()
, we take the minimum over all eccentricities, and for unweighted undirected graphs, eccentricities are computed using the algorithm by Takes and Kosters in distances_all_pairs
.
So you could do for instance the following
 sage: radius(G) == G.radius() + sage: from sage.graphs.distances_all_pairs import eccentricity + sage: radius(G) == min(eccentricity(G, algorithm='bounds'))
In the future, we should rename 'bounds'
to something like 'TK'
to better distinguish between algorithms by Takes and Koster and algorithms by Dragan, Habib and Viennot.
I just realized that the key of the reference to the paper is Habib2018 while the first author is Dragan. Please correct that and put the reference at the right place.
comment:11 Changed 16 months ago by
 Commit changed from b86ae754ade5a1b5ad7afcdc684d5d0a6485c52f to 1777fad4b5bedcb34286e6064bf20d2d02231a88
Branch pushed to git repo; I updated commit sha1. New commits:
1777fad  reference fixed

comment:12 in reply to: ↑ 10 ; followup: ↓ 13 Changed 16 months ago by
Replying to dcoudert:
The default of this test is that soon it will compare the new algorithm with itself ;)
Didnt saw that coming :)
Currently, when calling
G.radius()
, we take the minimum over all eccentricities, and for unweighted undirected graphs, eccentricities are computed using the algorithm by Takes and Kosters indistances_all_pairs
. So you could do for instance the following sage: radius(G) == G.radius() + sage: from sage.graphs.distances_all_pairs import eccentricity + sage: radius(G) == min(eccentricity(G, algorithm='bounds'))
Done
In the future, we should rename
'bounds'
to something like'TK'
to better distinguish between algorithms by Takes and Koster and algorithms by Dragan, Habib and Viennot.
ok
I just realized that the key of the reference to the paper is Habib2018 while the first author is Dragan. Please correct that and put the reference at the right place.
fixed.
One more thing. Should I implement the weighted version of this algorithm in this ticket or open separate ticket for that purpose?
comment:13 in reply to: ↑ 12 Changed 16 months ago by
One more thing. Should I implement the weighted version of this algorithm in this ticket or open separate ticket for that purpose?
you can certainly do it here, but in another file (different backend). The + is that you will be able to integrate all at once. The  is that the risk of conflict with other tickets increases, but is honestly rather limited.
I just realized that it is incorrect to raise an error if the graph is weighted. This method does not take edge weights into account and it is clear in the method description (you can be more explicit if you think it is not enough).
 if G.is_directed() or G.weighted(): + if G.is_directed():
comment:14 followup: ↓ 15 Changed 16 months ago by
 Commit changed from 1777fad4b5bedcb34286e6064bf20d2d02231a88 to 25f72302aabc364e87d5c9e4c473d6f0ffa5b3da
Branch pushed to git repo; I updated commit sha1. New commits:
25f7230  added radius method for weighted graphs

comment:15 in reply to: ↑ 14 Changed 16 months ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
25f7230 added radius method for weighted graphs
I have added method for computing radius of weighted graph in boost_graph.pyx file.
TODO:
 complete documentation
 add testcases
Major issue:
 on running program alongwith radius, following error occurs. I tried solving it, with no luck. Can you look into it.
sage: from sage.graphs.base.boost_graph import radius sage: G = graphs.PetersenGraph() sage: radius(G) 2.0 sage: free(): invalid next size (fast)  /home/vipul/sage/local/lib/python3.7/sitepackages/cysignals/signals.cpython37mx86_64linuxgnu.so(+0x827b)[0x7f85753f427b] /home/vipul/sage/local/lib/python3.7/sitepackages/cysignals/signals.cpython37mx86_64linuxgnu.so(+0x8338)[0x7f85753f4338] /home/vipul/sage/local/lib/python3.7/sitepackages/cysignals/signals.cpython37mx86_64linuxgnu.so(+0xb2e5)[0x7f85753f72e5] /lib/x86_64linuxgnu/libc.so.6(+0x3ef20)[0x7f8584092f20] /lib/x86_64linuxgnu/libc.so.6(gsignal+0xc7)[0x7f8584092e97] /lib/x86_64linuxgnu/libc.so.6(abort+0x141)[0x7f8584094801] /lib/x86_64linuxgnu/libc.so.6(+0x89897)[0x7f85840dd897] /lib/x86_64linuxgnu/libc.so.6(+0x9090a)[0x7f85840e490a] /lib/x86_64linuxgnu/libc.so.6(+0x19bcc1)[0x7f85841efcc1] /lib/x86_64linuxgnu/libc.so.6(__libc_thread_freeres+0x32)[0x7f85841f0652] /lib/x86_64linuxgnu/libpthread.so.0(+0x7700)[0x7f8583e3c700] /lib/x86_64linuxgnu/libc.so.6(clone+0x3f)[0x7f858417588f]  Attaching gdb to process id 13376.
comment:16 followup: ↓ 18 Changed 16 months ago by
What is the relation with #29431? It looks to me like they should be combined somehow, or one should be closed as a duplicate.
comment:17 Changed 16 months ago by
I suspect the issue is cdef vector[double] ecc = {0 for i in range(n)}
. I tried using a for loop with push_back
and got no issue.
You can:
 use type
bint
fornegative_weight
 use type
v_index
forsource
,next_source
,antipode
andv
 use strict comparison for
if eccentricity <= result.distances[v]:
 error message start with lower case letter, so This > this
comment:18 in reply to: ↑ 16 Changed 16 months ago by
Replying to ghDaveWitteMorris:
What is the relation with #29431? It looks to me like they should be combined somehow, or one should be closed as a duplicate.
Right. We will certainly have to close #29431 as duplicate.
comment:19 followup: ↓ 20 Changed 16 months ago by
 Commit changed from 25f72302aabc364e87d5c9e4c473d6f0ffa5b3da to abdabce90fd9cb623753c1e5fcde4b00b39b46b9
Branch pushed to git repo; I updated commit sha1. New commits:
abdabce  Documentation completed

comment:20 in reply to: ↑ 19 Changed 16 months ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
abdabce Documentation completed
I have updated documentation. For testing correctness, I have checked this on unweighted graphs. For performance comparisons, I have compared it with G.radius(algorithm='Dijkstra_Boost')
on unweighted graphs.
Can you suggest me some weighted graph to test and compare it on.
Major issue

sage: from sage.graphs.base.boost_graph import radius sage: G = graphs.PathGraph(7) sage: radius(G) 3.0 sage: G.weighted() False sage: G.radius(algorithm = 'Dijkstra_Boost') 3 sage: G.weighted() True sage: radius(G)  TypeError Traceback (most recent call last) <ipythoninput77c36f6341733> in <module>() > 1 radius(G) /home/vipul/sage/local/lib/python3.7/sitepackages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.radius (build/cythonized/sage/graphs/base/boost_graph.cpp:19859)() 1605 return cycle_basis 1606 > 1607 cpdef radius(g, weight_function=None): 1608 r""" 1609 Return radius of weighted graph `g`. /home/vipul/sage/local/lib/python3.7/sitepackages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.radius (build/cythonized/sage/graphs/base/boost_graph.cpp:19149)() 1672 cdef dict v_to_int = {vv: vi for vi, vv in enumerate(g)} 1673 cdef BoostVecWeightedGraph g_boost > 1674 boost_weighted_graph_from_sage_graph(&g_boost, g, v_to_int, weight_function) 1675 1676 import sys /home/vipul/sage/local/lib/python3.7/sitepackages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.boost_weighted_graph_from_sage_graph (build/cythonized/sage/graphs/base/boost_graph.cpp:3879)() 159 else: 160 for u,v,w in g_sage.edge_iterator(): > 161 g.add_edge(vertex_to_int[u], vertex_to_int[v], float(w)) 162 else: 163 if reverse: TypeError: float() argument must be a string or a number, not 'NoneType'
This error occurs due to conversion of G
from unweighted
to weighted
and this conversion occurs in shortest_path_lengths
method in generic_graph.py
Ideas to solve this problem
 Either we make sure that
radius
method inboost_graph.pyx
is always called with nonnone weight function, as done inshortest_path_lengths
method ingeneric_graph.py
. As we cannot define a function inside cpdef function.
 We make changes in
shortest_path_lengths
ingeneric_graph.pyx
method and simultaneously updateshortest_paths
method inboost_graph.pyx
. (This might have some other consequences.)
comment:21 followup: ↓ 22 Changed 16 months ago by
You raised an issue that must be fixed separately.
Can you open a specific ticket (no need to build it on top of this ticket) ?
In general, the input graph should never be modified by a method, unless the method is specifically designed for (e.g., add an edge/vertex, etc.).
comment:22 in reply to: ↑ 21 Changed 16 months ago by
Replying to dcoudert:
You raised an issue that must be fixed separately.
Can you open a specific ticket (no need to build it on top of this ticket) ?
In general, the input graph should never be modified by a method, unless the method is specifically designed for (e.g., add an edge/vertex, etc.).
I have opened #29734 for this purpose and provided my solution for it. You can review it. And tell me, if anything needs to be done.
comment:23 followup: ↓ 25 Changed 16 months ago by
you can now rename the methods radius_DHV
and expose them in graph.py
.
comment:24 Changed 16 months ago by
 Commit changed from abdabce90fd9cb623753c1e5fcde4b00b39b46b9 to e002e8aa65e1584af1d0c881dc8e21cae842f8e1
comment:25 in reply to: ↑ 23 Changed 16 months ago by
Replying to dcoudert:
you can now rename the methods
radius_DHV
and expose them ingraph.py
.
Done rebasing and updating graph.py.
comment:26 Changed 16 months ago by
 Branch changed from u/ghvipul79321/ticket29715 to public/graphs/29715_radius_DHV
 Commit changed from e002e8aa65e1584af1d0c881dc8e21cae842f8e1 to 0a642271bb637ccc57611610115191aea814b8d0
 Dependencies #29660 deleted
I pushed further improvements in a new branch and removed dependency on 29660. The main change is to reduce the number of arrays used. Do not hesitate to make further tests.
New commits:
453dcc5  trac #29715: review edit for unweighted graphs

045022c  trac #29715: review edit for weighted graphs

0a64227  trac #29715: review edit in graph.py

comment:27 followup: ↓ 28 Changed 16 months ago by
 Commit changed from 0a642271bb637ccc57611610115191aea814b8d0 to a02a614ca3d98e4b9e76cf21d23a8efe96d78b98
Branch pushed to git repo; I updated commit sha1. New commits:
a02a614  minor changes and improved consistency

comment:28 in reply to: ↑ 27 Changed 16 months ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
a02a614 minor changes and improved consistency
I have made changes in defining weight_function in eccentricity
method. So that bothG.radius(algorithm='Dijkstra_Boost', by_weight=True)
and G.radius(by_weight=True)
will give same result when graph is unweighted and edge_labels are None
Rest look fine to me :)
comment:29 Changed 16 months ago by
 Commit changed from a02a614ca3d98e4b9e76cf21d23a8efe96d78b98 to d9c90d1dbe213ce1711f5f2b2aef68cf313f60ba
Branch pushed to git repo; I updated commit sha1. New commits:
d9c90d1  trac #29715: fix documentation

comment:30 followup: ↓ 31 Changed 16 months ago by
This should fix the documentation.
Some issues remain with the usage of weights with boost. If the method is called without weight function and that g.weigthed() == False
, then the weight of edges is set to 1. This is not documented in the boost method.
Also, we don't use the parameter check_weight
.
comment:31 in reply to: ↑ 30 ; followup: ↓ 32 Changed 16 months ago by
Replying to dcoudert:
Some issues remain with the usage of weights with boost. If the method is called without weight function and that
g.weigthed() == False
, then the weight of edges is set to 1. This is not documented in the boost method.
  ``weight_function``  function (default: ``None``); a function that  associates a weight to each edge. If ``None`` (default), the weights of  ``g`` are used, if available, otherwise all edges have weight 1. +  ``weight_function``  function (default: ``None``); a function that + associates a weight to each edge. If ``None`` (default), the weights of + ``g`` are used, if ``g.weighted()==True``, otherwise all edges have weight 1.
Are you suggesting this?
Also, we don't use the parameter
check_weight
.
For this we can do the following:
 In
radius
method ingraph.py
+ if by_weight and not weight_function:
+ def weight_function(e):
+ return e[2] if e[2] else 1
 In
radius_DHV
inboost_graph.pyx
, introduce check_weight parameter
+ if check_weight and weight_function:
+ self._check_weight_function(weight_function)
What are your opinion on this. I will apply same changes in #29744
comment:32 in reply to: ↑ 31 Changed 16 months ago by
Are you suggesting this?
Yes, something like that.
Also, we don't use the parameter
check_weight
.For this we can do the following:
 In
radius
method ingraph.py
+ if by_weight and not weight_function: + def weight_function(e): + return e[2] if e[2] else 1
better to do return 1 if e[2] is None else e[2]
. Somehow, we should raise an error if the label of an edge is a string or something else.
 In
radius_DHV
inboost_graph.pyx
, introduce check_weight parameter+ if check_weight and weight_function: + self._check_weight_function(weight_function)
What are your opinion on this. I will apply same changes in #29744
ok
comment:33 followup: ↓ 34 Changed 16 months ago by
 Commit changed from d9c90d1dbe213ce1711f5f2b2aef68cf313f60ba to e495db83ee3a3c6062af53777603221a57077b7b
Branch pushed to git repo; I updated commit sha1. New commits:
e495db8  updated according to last commit

comment:34 in reply to: ↑ 33 Changed 16 months ago by
comment:35 Changed 16 months ago by
 Commit changed from e495db83ee3a3c6062af53777603221a57077b7b to 9501a4a70a5ac6eab7ced68917a5c92e18a38730
Branch pushed to git repo; I updated commit sha1. New commits:
9501a4a  minor correction

comment:36 Changed 16 months ago by
One problem that, I encountered is when method eccentricity
is called with v = G.vertices()
and algorithm = Johnson_Boost
or or FloydWarshallPython
or FloydWarshallCython
. It raises error that works only when all eccentricities are needed.
It has consequences on radius
and diameter
method, since they call min or max of G.eccentricity(v=list(self),....)
In my opinion, We should make condition as v is None or v == self.vertices()
. Also, to be more precise, shall we do set(v) == set(self.vertices())
, so ordering wont affect?
Shall I proceed to open a ticket for this problem and do suggested changes?
comment:37 Changed 16 months ago by
You can do it here and mention in diameter ticket that the issue is fixed here.
A possible fix is to change the test in method eccentricity to:
if v is None or all(u in self for u in v):
and when calling method eccentricity to set v=None
instead of v=list(self)
.
comment:38 Changed 16 months ago by
One problem that we forget to address in #29734 was that :
 We didnt updated documentation of
shortest_paths
method inboost_graph.pyx
, to this.
+  ``weight_function``  function (default: ``None``); a function that
+ associates a weight to each edge. If ``None`` (default), the weights of
+ ``g`` are used, if ``g.weighted()==True``, otherwise all edges have weight 1
 To make weight_function use uniform, I think, we should make following changes in,
shortest_path
,shortest_path_length
,shortest_paths
,shortest_path_lengths
,shortest_path_all_pairs
+ if by_weight and weight_function is None:
+ def weight_function(e):
+ return 1 if e[2] is None else e[2]
and this should be at the begining of each method, so that we wont have to worry about it anymore.
What are your opinion on this?
comment:39 Changed 16 months ago by
What I suggest is:
 We finalize this ticket for radius / DHV and postpone to other tickets problems we raised but that are independent of this ticket.
 For each identified issue, you add a note in the meta ticket #29657 with example and possibly ideas on how to fix it. It will help organizing the discussion and following the tasks. We are currently discussing the same issues in 2 tickets...
And your proposal is certainly good.
comment:40 Changed 16 months ago by
 Commit changed from 9501a4a70a5ac6eab7ced68917a5c92e18a38730 to 8f9d62761bbab1efc8206985e25c93a2e09bd8ba
Branch pushed to git repo; I updated commit sha1. New commits:
8f9d627  made corrections

comment:41 Changed 16 months ago by
TODO:
 Find a reliable way to detect negative cycle, which can be used in our method. For more info check comment_22 in #29744
 Decide default algorithms.
comment:42 followup: ↓ 43 Changed 16 months ago by
 Commit changed from 8f9d62761bbab1efc8206985e25c93a2e09bd8ba to 2437136be053d0ef9e44de79c0ed2cec512dbd4e
Branch pushed to git repo; I updated commit sha1. New commits:
2437136  Fixed for negative edge weights

comment:43 in reply to: ↑ 42 Changed 16 months ago by
comment:44 Changed 16 months ago by
 Keywords gsoc2020 added; gsoc removed
 Status changed from needs_review to positive_review
LGTM.
comment:45 Changed 15 months ago by
 Branch changed from public/graphs/29715_radius_DHV to 2437136be053d0ef9e44de79c0ed2cec512dbd4e
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
radius, diameter, eccentricity, center, periphery moved to graph and digraph separately
unneccessary comments removed
added for unweighted graphs