diameter computation in undirected graphs using certificates

[vipul79321]

This ticket aims to implement diameter computation method for weighted and unweighted undirected graphs, as given in http://arxiv.org/abs/1803.04660

CC: @dcoudert

Component: graph theory

Keywords: gsoc2020

Author: Vipul Gupta

Branch/Commit: 3eed584

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/29744

[vipul79321]

Branch: u/gh-vipul79321/ticket29744

[sagetrac-git]

Commit: e6ba789

[sagetrac-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
0cd8932	method added. Naming, documentation remaining to be done
e6ba789	completed

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:4

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):

1. Select x minimizing e_L(x) and such that d(u, x) + e_L(x) <= e(u).
2. Compute e(x) and update LB.
3. 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.
4. 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...

[sagetrac-git]

Changed commit from e6ba789 to 6fa0327

[sagetrac-git]

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

6fa0327

improved a little

[vipul79321]

comment:6

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):

1. Select x minimizing e_L(x) and such that d(u, x) + e_L(x) <= e(u).
2. Compute e(x) and update LB.
3. 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.
4. 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.

[dcoudert]

comment:7

let active be the list of vertices

while True, do:

1. let idx be the index of the vertex in active with largest eccentricity upper bound
2. active[idx], active[-1] = active[-1], active[idx] # exchange
3. source = active.pop() # source is no longer active
4. compute BFS from source, set ecc[source] and update eccentricity lower bounds
5. 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.

[sagetrac-git]

Changed commit from 6fa0327 to 1068f75

[sagetrac-git]

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

1068f75

updated using active vertices list

[vipul79321]

comment:9

Replying to @dcoudert:

let active be the list of vertices

while True, do:

1. let idx be the index of the vertex in active with largest eccentricity upper bound
2. active[idx], active[-1] = active[-1], active[idx] # exchange
3. source = active.pop() # source is no longer active
4. compute BFS from source, set ecc[source] and update eccentricity lower bounds
5. 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 use source as its delegate certificate
• If after entering inner while loop there is no vertex in active list which satisfies the condition, then we should use last x as delegate certificate

[dcoudert]

Changed dependencies from #29660 to none

[dcoudert]

Changed commit from 1068f75 to 37ac47a

[dcoudert]

comment:10

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

[dcoudert]

Changed branch from u/gh-vipul79321/ticket29744 to public/graphs/29744_diameter_DHV

[sagetrac-git]

Changed commit from 37ac47a to a049556

[sagetrac-git]

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

a049556

index error fixed

[vipul79321]

comment:12

• 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.

[dcoudert]

comment:13

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).

[sagetrac-git]

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

f9319d5

trac #29744: minor edit

[sagetrac-git]

Changed commit from a049556 to f9319d5

[dcoudert]

comment:15

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.

[vipul79321]

comment:16

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

[dcoudert]

comment:17

Feel free to do it.

[sagetrac-git]

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

d33b780

trac #29744: fix merge conflicts

[sagetrac-git]

Changed commit from 9a06bbd to d33b780

[dcoudert]

comment:35

I fix merge conflict with 9.2.beta2. Please check that everything is working well.

[vipul79321]

comment:36

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.

[dcoudert]

comment:37

LGTM.

the pycodestyle warnings reported by the patchbot are fixed in #29804

[vbraun]

comment:38

Merge conflict

[sagetrac-git]

Changed commit from d33b780 to f2557a8

[sagetrac-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

[vipul79321]

comment:40

Replying to @sagetrac-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

[dcoudert]

comment:41

OK, let's wait for next beta to see the issue.

[sagetrac-git]

Changed commit from f2557a8 to 97c2b1b

[sagetrac-git]

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

97c2b1b

fixed merge conflict

[vipul79321]

comment:43

Replying to @sagetrac-git:

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

97c2b1b

fixed merge conflict

Fixed merge conflict with 9.2beta5

[sagetrac-git]

Changed commit from 97c2b1b to 3eed584

[sagetrac-git]

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

3eed584

trac #29744: review commit

[dcoudert]

comment:46

I did a minor change because in ticket #30145 I'm preparing the deprecation of edge_iterator.

LGTM

[vbraun]

Changed branch from public/graphs/29744_diameter_DHV to 3eed584