Opened 2 years ago
Closed 2 years ago
#29744 closed enhancement (fixed)
diameter computation in undirected graphs using certificates
Reported by:  vipul73921  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  graph theory  Keywords:  gsoc2020 
Cc:  David Coudert  Merged in:  
Authors:  Vipul Gupta  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  3eed584 (Commits, GitHub, GitLab)  Commit:  3eed5849912893e1e9d6e8ec9ca0f1400091369b 
Dependencies:  Stopgaps: 
Description
This ticket aims to implement diameter computation method for weighted and unweighted undirected graphs, as given in http://arxiv.org/abs/1803.04660
Change History (47)
comment:1 Changed 2 years ago by
Branch:  → u/ghvipul79321/ticket29744 

comment:2 Changed 2 years ago by
Commit:  → e6ba789eec1f138ffe1f6ebf2f1c840c295a0e3e 

comment:3 Changed 2 years ago by
Status:  new → needs_review 

comment:4 followup: 6 Changed 2 years ago by
Reviewers:  → David Coudert 

The paper is unclear for the line Select x such that d(u, x) + e(x) = e(u)
. In fact, this is method minES in the paper.
Since we don't know e(x), we do as follows (a while True
loop):
 Select x minimizing e_L(x) and such that d(u, x) + e_L(x) <= e(u).
 Compute e(x) and update
LB
.  If e(x) = e_L(x), then x a good choice. We use it to update eccentricity upper bounds. Then we break from the while loop.
 Otherwise, x was not a good choice. We use its antipode to update lower bounds. Then, we go to 1.
It might be suitable to maintain the list of vertices from which we have not yet computed a BFS.
Don't forget to add this ticket in the meta ticket. Also, I have not checked if a previously opened ticket was trying to implement the same algorithm...
comment:5 Changed 2 years ago by
Commit:  e6ba789eec1f138ffe1f6ebf2f1c840c295a0e3e → 6fa032702da536c26d3e5de0a69b4a4ef2e39922 

Branch pushed to git repo; I updated commit sha1. New commits:
6fa0327  improved a little

comment:6 Changed 2 years ago by
Replying to dcoudert:
The paper is unclear for the line
Select x such that d(u, x) + e(x) = e(u)
. In fact, this is method minES in the paper.Since we don't know e(x), we do as follows (a
while True
loop):
 Select x minimizing e_L(x) and such that d(u, x) + e_L(x) <= e(u).
 Compute e(x) and update
LB
. If e(x) = e_L(x), then x a good choice. We use it to update eccentricity upper bounds. Then we break from the while loop.
 Otherwise, x was not a good choice. We use its antipode to update lower bounds. Then, we go to 1.
I have added following changes and performance improved a little, but still not comparable to iFUB.
It might be suitable to maintain the list of vertices from which we have not yet computed a BFS.
It unclear to me, how we should use list of active vertices. Can you explain this part, so I can work on it.
comment:7 followup: 9 Changed 2 years ago by
let active be the list of vertices
while True, do:
 let idx be the index of the vertex in active with largest eccentricity upper bound
 active[idx], active[1] = active[1], active[idx] # exchange
 source = active.pop() # source is no longer active
 compute BFS from source, set ecc[source] and update eccentricity lower bounds
 apply minES as described in #comment:4.
 Each time you select a vertex x in active, you remove it from active.
 Warning: when you select the antipode, may be it is no longer active, and so cannot be removed from active. This is something hard to avoid. But you can use it anyway. So check if the antipode is in active and if so remove it.
Hope it helps.
comment:8 Changed 2 years ago by
Commit:  6fa032702da536c26d3e5de0a69b4a4ef2e39922 → 1068f753c89e6de759681e6faeb436c94bb0a836 

Branch pushed to git repo; I updated commit sha1. New commits:
1068f75  updated using active vertices list

comment:9 Changed 2 years ago by
Replying to dcoudert:
let active be the list of vertices
while True, do:
 let idx be the index of the vertex in active with largest eccentricity upper bound
 active[idx], active[1] = active[1], active[idx] # exchange
 source = active.pop() # source is no longer active
 compute BFS from source, set ecc[source] and update eccentricity lower bounds
 apply minES as described in #comment:4.
 Each time you select a vertex x in active, you remove it from active.
 Warning: when you select the antipode, may be it is no longer active, and so cannot be removed from active. This is something hard to avoid. But you can use it anyway. So check if the antipode is in active and if so remove it.
Hope it helps.
I have update my method as you mentioned. But there is no improvement in performance.
One major drawback of our code is that sometimes it never comes out of inner while loop. This happens, because there is no vertex in active
list which satisfies the condition distances[v] + ecc_lower_bound[v] <= ecc[source]
and hence the continuous popping from active
list
We have to figure out a way to deal with this situation when there is no such vertex in active
list
I have following suggestions:
 If intially there is no vertex in
active
list, which satisfies the condition, then we should usesource
as itsdelegate certificate
 If after entering inner while loop there is no vertex in
active
list which satisfies the condition, then we should use lastx
asdelegate certificate
comment:10 Changed 2 years ago by
Branch:  u/ghvipul79321/ticket29744 → public/graphs/29744_diameter_DHV 

Commit:  1068f753c89e6de759681e6faeb436c94bb0a836 → 37ac47a9297fc0a04441862ba8b2a82251d464a7 
Dependencies:  #29660 
I pushed a new branch with a different version of the algorithm. For me it's better and it is generally faster than iFUB.
I have also renamed the algorithm as DHV
instead of diameter_dragan
. The branch is in public, so you can modify it.
New commits:
1d08d3b  trac #29744: rebuild on top of 9.2.beta0

37ac47a  trac #29744: improved version of the algorithm

comment:11 Changed 2 years ago by
Commit:  37ac47a9297fc0a04441862ba8b2a82251d464a7 → a0495566ae194295ec7613decac5d983527c451d 

Branch pushed to git repo; I updated commit sha1. New commits:
a049556  index error fixed

comment:12 Changed 2 years ago by
 First of all, I would like to mention, it is very clean, efficient and simplified code :)
 One problem, I encountered was that it was giving index error as follows
sage: from sage.graphs.distances_all_pairs import diameter sage: G = graphs.RandomGNP(21,0.6) sage: % time diameter(G, algorithm = 'DHV')  IndexError Traceback (most recent call last) IndexError: list index out of range Exception ignored in: 'sage.graphs.distances_all_pairs.diameter_dragan' IndexError: list index out of range CPU times: user 512 µs, sys: 27 µs, total: 539 µs Wall time: 470 µs 0
I have fixed that.
 I agree, it sometimes works faster than iFUB.
Few examples that I would like to point out, where it perform equivalent to brute are 
sage: G = graphs.RandomGNP(1009,0.6) sage: % time diameter(G, algorithm = 'standard') CPU times: user 673 ms, sys: 7.41 ms, total: 681 ms Wall time: 679 ms 2 sage: % time diameter(G, algorithm = 'DHV') CPU times: user 648 ms, sys: 0 ns, total: 648 ms Wall time: 647 ms 2 sage: % time diameter(G) CPU times: user 346 ms, sys: 0 ns, total: 346 ms Wall time: 345 ms 2
sage: G = graphs.BubbleSortGraph(7) sage: % time diameter(G, algorithm = 'standard') CPU times: user 530 ms, sys: 0 ns, total: 530 ms Wall time: 529 ms 21 sage: % time diameter(G, algorithm = 'DHV') CPU times: user 580 ms, sys: 0 ns, total: 580 ms Wall time: 580 ms 21 sage: % time diameter(G) CPU times: user 276 ms, sys: 0 ns, total: 276 ms Wall time: 276 ms 21
sage: G = graphs.FoldedCubeGraph(13) sage: % time diameter(G, algorithm = 'standard') CPU times: user 359 ms, sys: 0 ns, total: 359 ms Wall time: 358 ms 6 sage: % time diameter(G, algorithm = 'DHV') CPU times: user 374 ms, sys: 0 ns, total: 374 ms Wall time: 373 ms 6 sage: % time diameter(G) CPU times: user 297 ms, sys: 0 ns, total: 297 ms Wall time: 296 ms 6
Maybe above graphs are the worst cases of this algorithm.
comment:13 Changed 2 years ago by
if we need to add active
in the outer while loop, it means that we are not correctly maintaining LB and UB. Indeed, if active is empty, it means that we have computed BFS from all the vertices. So we must have LB = UB. Can you check that ?
For the performance, try a large sparse graph, or graphs.RandomBarabasiAlbert(100000, 2)
.
comment:14 Changed 2 years ago by
Commit:  a0495566ae194295ec7613decac5d983527c451d → f9319d547f03ca9c8dcf166a7a626e6f22c12599 

Branch pushed to git repo; I updated commit sha1. New commits:
f9319d5  trac #29744: minor edit

comment:15 followup: 16 Changed 2 years ago by
You are right, we need to add active
as a test of the outer while loop. This is typically the case for a graph with 2 vertices and an edge. I added a dockets for this case.
May be we should rename the method diameter_DHV
to be consistent, no ?
You can now make this method available from the diameter method in graph.py
.
comment:16 Changed 2 years ago by
Replying to dcoudert:
You are right, we need to add
active
as a test of the outer while loop. This is typically the case for a graph with 2 vertices and an edge. I added a dockets for this case.May be we should rename the method
diameter_DHV
to be consistent, no ?
Yeah, that will be good.
You can now make this method available from the diameter method in
graph.py
.
Before doing this. I was wondering maybe I should implement the weighted version of this algorithm in boost_graph.pyx
? Then we will expose it graph.py
comment:18 followup: 19 Changed 2 years ago by
Commit:  f9319d547f03ca9c8dcf166a7a626e6f22c12599 → 0ada5851e8cacae3fcec1325bc9bfb9810c6df13 

comment:19 Changed 2 years ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
7314e0f trac 29744: method added for weighted graphs and exposed in graph.py
e9798b8 documentation updated
0ada585 Merge branch 'public/graphs/29744_diameter_DHV' of git://trac.sagemath.org/sage into diameter_DHV
added diameter_DHV
for weighted graph alongwith check_weight
parameter and exposed both methods in graph.py
.
comment:20 followup: 21 Changed 2 years ago by
Status:  needs_review → needs_work 

You should add a doctest with a weighted graph in boost.
sage: from sage.graphs.base.boost_graph import diameter_DHV sage: G = graphs.CycleGraph(6) sage: for u, v in G.edges(labels=False): ....: G.set_edge_label(u, v, 1) sage: G.set_edge_label(4, 5, 1) sage: diameter_DHV(G) # unweighted 3.0 sage: diameter_DHV(G, weight_function=lambda e:e[2]) # weighted 0.0
This last answer is not correct.
Other issues, that were certainly already here.
sage: G.diameter(by_weight=True)  ValueError Traceback (most recent call last) <ipythoninput8a687234a118b> in <module>() > 1 G.diameter(by_weight=True) /Users/dcoudert/sage/local/lib/python3.7/sitepackages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight) 5612 if by_weight: 5613 raise ValueError("algorithm '" + algorithm + "' does not work" + > 5614 " on weighted graphs") 5615 from sage.graphs.distances_all_pairs import diameter 5616 return diameter(self, algorithm=algorithm) ValueError: algorithm 'iFUB' does not work on weighted graphs sage: G.diameter(by_weight=True, algorithm='Johnson_Boost')  ValueError Traceback (most recent call last) <ipythoninput108e8a8c6456b1> in <module>() > 1 G.diameter(by_weight=True, algorithm='Johnson_Boost') /Users/dcoudert/sage/local/lib/python3.7/sitepackages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight) 5619 weight_function=weight_function, 5620 check_weight=check_weight, > 5621 algorithm=algorithm)) 5622 5623 @doc_index("Distances") /Users/dcoudert/sage/local/lib/python3.7/sitepackages/sage/graphs/graph.py in eccentricity(self, v, by_weight, algorithm, weight_function, check_weight, dist_dict, with_labels) 5387 elif algorithm in ['FloydWarshallPython', 'FloydWarshallCython', 'Johnson_Boost']: 5388 raise ValueError("algorithm '" + algorithm + "' works only if all" + > 5389 " eccentricities are needed") 5390 5391 if not isinstance(v, list): ValueError: algorithm 'Johnson_Boost' works only if all eccentricities are needed
comment:21 followup: 22 Changed 2 years ago by
Replying to dcoudert:
You should add a doctest with a weighted graph in boost.
sage: from sage.graphs.base.boost_graph import diameter_DHV sage: G = graphs.CycleGraph(6) sage: for u, v in G.edges(labels=False): ....: G.set_edge_label(u, v, 1) sage: G.set_edge_label(4, 5, 1) sage: diameter_DHV(G) # unweighted 3.0 sage: diameter_DHV(G, weight_function=lambda e:e[2]) # weighted 0.0This last answer is not correct.
This happens because instead of detecting negative cycle, BellmanFord
is returning negative distances :(
sage: from sage.graphs.base.boost_graph import shortest_paths sage: G = graphs.CycleGraph(6) sage: shortest_paths(G,0, weight_function = lambda e:e[2])[0] {0: 2, 1: 1, 2: 0, 3: 3, 4: 4, 5: 5}
Any suggestion on what should I do for this?
Other issues, that were certainly already here.
sage: G.diameter(by_weight=True)  ValueError Traceback (most recent call last) <ipythoninput8a687234a118b> in <module>() > 1 G.diameter(by_weight=True) /Users/dcoudert/sage/local/lib/python3.7/sitepackages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight) 5612 if by_weight: 5613 raise ValueError("algorithm '" + algorithm + "' does not work" + > 5614 " on weighted graphs") 5615 from sage.graphs.distances_all_pairs import diameter 5616 return diameter(self, algorithm=algorithm) ValueError: algorithm 'iFUB' does not work on weighted graphs sage: G.diameter(by_weight=True, algorithm='Johnson_Boost')  ValueError Traceback (most recent call last) <ipythoninput108e8a8c6456b1> in <module>() > 1 G.diameter(by_weight=True, algorithm='Johnson_Boost') /Users/dcoudert/sage/local/lib/python3.7/sitepackages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight) 5619 weight_function=weight_function, 5620 check_weight=check_weight, > 5621 algorithm=algorithm)) 5622 5623 @doc_index("Distances") /Users/dcoudert/sage/local/lib/python3.7/sitepackages/sage/graphs/graph.py in eccentricity(self, v, by_weight, algorithm, weight_function, check_weight, dist_dict, with_labels) 5387 elif algorithm in ['FloydWarshallPython', 'FloydWarshallCython', 'Johnson_Boost']: 5388 raise ValueError("algorithm '" + algorithm + "' works only if all" + > 5389 " eccentricities are needed") 5390 5391 if not isinstance(v, list): ValueError: algorithm 'Johnson_Boost' works only if all eccentricities are needed
This will be fixed by making changes suggested in last comment:37 in #29715
comment:22 followup: 23 Changed 2 years ago by
This happens because instead of detecting negative cycle,
BellmanFord
is returning negative distances :( ... Any suggestion on what should I do for this?
1) Mention the problem in the meta ticket. 2) Check the documentation of 'Johnson_Boost' in case it can be used to detect negative cycles. Otherwise, we may have to change default algorithm.
comment:23 Changed 2 years ago by
Replying to dcoudert:
This happens because instead of detecting negative cycle,
BellmanFord
is returning negative distances :( ... Any suggestion on what should I do for this?1) Mention the problem in the meta ticket.
Done.
2) Check the documentation of 'Johnson_Boost' in case it can be used to detect negative cycles.
Yeah it detects negative cycle properly.
But we cant use that in our algorithm. We have to find a way to avoid this, smae problem appears here and in radius_DHV
in #29715.
 1).I have one solution, since this methods are restricted to undirected graphs, why dont we exploit that property, since any edge with negative weight will definitely be a cycle. So raise an error in begining while checking for negative edges?
 2). or We can try the method, I suggested in #29657.
Finally, whichever method we decide, we have to decide what do we want from our method, when graph contains negative cycle , as well graph is disconnected
.
comment:24 Changed 2 years ago by
TODO:
 Find a reliable way to detect negative cycle, which can be used in our method.
 Make call to
eccentricity
method fromdiameter
method withv = None
.
 Finally, decide default algorithms.
comment:25 followups: 26 28 Changed 2 years ago by
If I understand well, so far we have no algorithm that can be used for weighted undirected graph with at least 1 edge with negative weight. So I propose for this ticket and for #29715 to:
 raise an error if the graph has an edge with negative weight, and so to remove calls to BellmanFord. This way we have a correct implementation for graphs with nonnegative weights.
 Indicate in the todo list of #29657 that we have this issue. If we are able to find a proper fix, then we will be able to update all methods with this issue at once.
comment:26 followup: 32 Changed 2 years ago by
Replying to dcoudert:
If I understand well, so far we have no algorithm that can be used for weighted undirected graph with at least 1 edge with negative weight.
Yeah,because a negative edge in Undirected graph will automatically a cycle, because we can move in both direction from that edge and hence a cycle. Take a look at this, it might help us. https://stackoverflow.com/questions/14785413/canweapplythebellmanfordalgorithmtoanundirectedgraph.
comment:27 Changed 2 years ago by
Commit:  0ada5851e8cacae3fcec1325bc9bfb9810c6df13 → 9a06bbd64dfa93e3497c7de0a6ff775b3e1d37cc 

Branch pushed to git repo; I updated commit sha1. New commits:
9a06bbd  fixed for negative weights

comment:28 Changed 2 years ago by
Replying to dcoudert:
If I understand well, so far we have no algorithm that can be used for weighted undirected graph with at least 1 edge with negative weight. So I propose for this ticket and for #29715 to:
 raise an error if the graph has an edge with negative weight, and so to remove calls to BellmanFord. This way we have a correct implementation for graphs with nonnegative weights.
 Indicate in the todo list of #29657 that we have this issue. If we are able to find a proper fix, then we will be able to update all methods with this issue at once.
Done.
comment:29 Changed 2 years ago by
Status:  needs_work → needs_review 

comment:30 Changed 2 years ago by
Keywords:  gsoc2020 added; gsoc20 removed 

Status:  needs_review → positive_review 
LGTM.
comment:32 Changed 2 years ago by
@dcoudert, I tried solving the merge conflict using following steps 
1). Firstly, I pulled branch public/graphs/29744_diameter_DHV
in my local branch diameter
of develop.
2). Then, on branch develop
, I ran git pull
to pull changes from sage git repository.
3). Then, I checked out diameter
branch and ran git merge develop
, hoping to get merge conflicts. But It merged cleanly. And is running without any problem.
Is this the right procedure to find merge conflicts?
Can you suggest me something for this?
comment:33 Changed 2 years ago by
We have to wait for the next beta to see the conflict. Tickets are accepted and merged into the develop branch for next beta in a certain order. The radius ticket has been merged and it adds the references to Dragan. This might be the issue. So we will have to modify this ticket accordingly. This is for the same reason that we are waiting for the finalization of the eccentricity ticket.
comment:34 Changed 2 years ago by
Commit:  9a06bbd64dfa93e3497c7de0a6ff775b3e1d37cc → d33b7808fac7b8a42411e554a62dcde75734fc69 

Branch pushed to git repo; I updated commit sha1. New commits:
d33b780  trac #29744: fix merge conflicts

comment:35 followup: 36 Changed 2 years ago by
Status:  needs_work → needs_review 

I fix merge conflict with 9.2.beta2. Please check that everything is working well.
comment:36 Changed 2 years ago by
Replying to dcoudert:
I fix merge conflict with 9.2.beta2. Please check that everything is working well.
I have checked boundary cases. It looks good to me.
comment:37 Changed 2 years ago by
Status:  needs_review → positive_review 

LGTM.
the pycodestyle warnings reported by the patchbot are fixed in #29804
comment:39 followup: 40 Changed 2 years ago by
Commit:  d33b7808fac7b8a42411e554a62dcde75734fc69 → f2557a81df67ef5df8133c5784891fe4ee927e35 

comment:40 Changed 2 years ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
95d669a Merge branch 'public/graphs/29744_diameter_DHV' of git://trac.sagemath.org/sage into diameter
f2557a8 minor documentation change
Done some minor change in documentation.
Merge conflict still to be solved in next release
comment:42 followup: 43 Changed 2 years ago by
Commit:  f2557a81df67ef5df8133c5784891fe4ee927e35 → 97c2b1bf6422f9b1f46d460cce048bb25353c78a 

Branch pushed to git repo; I updated commit sha1. New commits:
97c2b1b  fixed merge conflict

comment:43 Changed 2 years ago by
comment:44 Changed 2 years ago by
Status:  needs_work → needs_review 

comment:45 Changed 2 years ago by
Commit:  97c2b1bf6422f9b1f46d460cce048bb25353c78a → 3eed5849912893e1e9d6e8ec9ca0f1400091369b 

Branch pushed to git repo; I updated commit sha1. New commits:
3eed584  trac #29744: review commit

comment:46 Changed 2 years ago by
Status:  needs_review → positive_review 

I did a minor change because in ticket #30145 I'm preparing the deprecation of edge_iterator
.
LGTM
comment:47 Changed 2 years ago by
Branch:  public/graphs/29744_diameter_DHV → 3eed5849912893e1e9d6e8ec9ca0f1400091369b 

Resolution:  → fixed 
Status:  positive_review → 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
method added. Naming, documentation remaining to be done
completed