Exact Algorithm for Diameters of Large Real Directed Graphs

[tabus]

Adds an algorithm for computing the diameter of directed graphs as described in https://doi.org/10.1007/978-3-319-20086-6_5

Component: graph theory

Keywords: diameter

Author: João Tavares

Branch/Commit: u/gh-tabus/exact_algorithm_for_diameters_of_large_real_directed_graphs @ a79cfd1

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

[tabus]

Branch: u/gh-tabus/exact_algorithm_for_diameters_of_large_real_directed_graphs

[tabus]

New commits:

febaa2e

First implmentation (only for undirected graphs)

[tabus]

Commit: febaa2e

[dcoudert]

comment:3

A few comments:

• please document your methods
• use standard notation n instead of V.
• you can use UINT32_MAX
• range(g.neighbors[v+1]-g.neighbors[v+1]) unless I'm mistaken, this range is empty...
• you can use bitset_first and bitset_next to iterate over 1s of a bitset. See for instance https://github.com/sagemath/sagelib/blob/master/sage/misc/bitset.pxi
• Diferent graph -> Different graph, although I don't understand this comment.

[sagetrac-git]

Changed commit from febaa2e to fa9a391

[sagetrac-git]

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

86d5bb8	Cleanup files and add tests
fa9a391	Added support for DiGraph + Fixed bug concerning the doublesweep

[tabus]

comment:5

Thank you so much for you input.

I have taken care of points 2, 3, 5 (I wasn't aware of the existence of a function like bitwise_next in O(1), thank you!).

Regarding the 6th point (sorry for the typo) the comment refers to the fact that the BFS should be done only on the SCC of the considered node with the inverted edges in order to obtain the backwards distance. Temporarily I had used the given graph because I was considering G as an undirected graph. The comment was only there to remind me to find and efficient way to perform the BFS on the desired graph.

[sagetrac-git]

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

b6e4ac4

Fixing the notation

[sagetrac-git]

Changed commit from fa9a391 to b6e4ac4

[tabus]

comment:7

Replying to @dcoudert:

A few comments:

• please document your methods
• use standard notation n instead of V.
• you can use UINT32_MAX
• range(g.neighbors[v+1]-g.neighbors[v+1]) unless I'm mistaken, this range is empty...
• you can use bitset_first and bitset_next to iterate over 1s of a bitset. See for instance https://github.com/sagemath/sagelib/blob/master/sage/misc/bitset.pxi
• Diferent graph -> Different graph, although I don't understand this comment.

About the 6th point as I commented before, the problem is that I have to consider the graph of reverse edges with vertices in the SCC. One way to do this is to create these graphs, however this seems be very inefficient. One solution I've though of is to create only the revere graph using init_revese, which is already implemented, and to run BFS adding only the vertices on the same SCC to the queue.

The current implementation of simple_BFS does not allow for this. However with a couple of very simple changes and adding an optional list of components to the arguments of the function it could. I am hesitant about this path because I would then have to fix all calls to this function.

Can I get your input on this one? Is it preferred not to mess with the arguments of already implemented functions? Perhaps I should just switch to another graph structure which allows for these operations although a bit less efficient?

[sagetrac-git]

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

2fc27da

Change to simple_BFS

[sagetrac-git]

Changed commit from b6e4ac4 to 2fc27da

[tabus]

New commits:

febaa2e	First implmentation (only for undirected graphs)
86d5bb8	Cleanup files and add tests
fa9a391	Added support for DiGraph + Fixed bug concerning the doublesweep
b6e4ac4	Fixing the notation
2fc27da	Change to simple_BFS

[sagetrac-git]

Changed commit from 2fc27da to 121fa76

[sagetrac-git]

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

25010cb	Working version of the implementation
121fa76	Merge remote-tracking branch 'refs/remotes/trac/u/gh-tabus/exact_algorithm_for_diameters_of_large_real_directed_graphs' into t/29309/exact_algorithm_for_diameters_of_large_real_directed_graphs

[sagetrac-git]

Changed commit from 121fa76 to 0e87a2b

[sagetrac-git]

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

0e87a2b

Fix the merge mistakes

[tabus]

Author: João Tavares

[videlec]

comment:13

You must add doctests for your algorithms. Also, benchmarks would be welcome.

[sagetrac-git]

Changed commit from 0e87a2b to 81a019f

[sagetrac-git]

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

81a019f

Added doctests

[tabus]

comment:15

I have been experimenting and it seems this method is more efficient when the graph is sparse.
It should happen because the method creates a short_digraph with the reverse edges, something that iFUB does not have to do.

sage: G = DiGraph([[1,2]])
....: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(1000, 0.2)
....: 
....: %time G.diameter(algorithm='TYY')
....: %time G.diameter()
....: 
CPU times: user 887 ms, sys: 11.9 ms, total: 899 ms
Wall time: 912 ms
2
CPU times: user 542 ms, sys: 2.96 ms, total: 545 ms
Wall time: 549 ms
2
sage: G = DiGraph([[1,2]])
....: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(1000, 0.1)
....: 
....: %time G.diameter(algorithm='TYY')
....: %time G.diameter()
....: 
CPU times: user 77.5 ms, sys: 0 ns, total: 77.5 ms
Wall time: 78.5 ms
3
CPU times: user 314 ms, sys: 3.66 ms, total: 317 ms
Wall time: 320 ms
3
sage: G = DiGraph([[1,2]])
....: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(1000, 0.01)
....: 
....: %time G.diameter(algorithm='TYY')
....: %time G.diameter()
....: 
CPU times: user 22.5 ms, sys: 0 ns, total: 22.5 ms
Wall time: 31.6 ms
6
CPU times: user 54.6 ms, sys: 196 µs, total: 54.8 ms
Wall time: 63.6 ms
6
sage: G = DiGraph([[1,2]])
....: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(5000, 0.2)
....: 
....: %time G.diameter(algorithm='TYY')
....: %time G.diameter()
....: 
CPU times: user 1min 9s, sys: 218 ms, total: 1min 9s
Wall time: 1min 10s
2
CPU times: user 36.7 s, sys: 232 ms, total: 36.9 s
Wall time: 37.1 s
2
sage: G = DiGraph([[1,2]])
....: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(5000, 0.1)
....: 
....: %time G.diameter(algorithm='TYY')
....: %time G.diameter()
....: 
CPU times: user 30.3 s, sys: 24.1 ms, total: 30.3 s
Wall time: 30.3 s
2
CPU times: user 16.4 s, sys: 64.1 ms, total: 16.4 s
Wall time: 16.4 s
2
sage: G = DiGraph([[1,2]])
....: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(5000, 0.05)
....: 
....: %time G.diameter(algorithm='TYY')
....: %time G.diameter()
....: 
CPU times: user 665 ms, sys: 13 µs, total: 665 ms
Wall time: 665 ms
3
CPU times: user 7.59 s, sys: 4.04 ms, total: 7.6 s
Wall time: 7.6 s
3

[sagetrac-git]

Changed commit from 781538f to a79cfd1

[sagetrac-git]

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

a79cfd1

Added reference + Disposed of memory

[dcoudert]

comment:19

FYI, #29346 also proposes an implementation of the same algorithm. Authors could join forces to get a better code.

[tabus]

comment:20

Replying to @dcoudert:

FYI, #29346 also proposes an implementation of the same algorithm. Authors could join forces to get a better code.

#29346 implements the same algorithm with the modified definition of diameter, where we consider the maximum finite eccentricities only. This seems counter intuitive to have different algorithms giving different answers

[dcoudert]

comment:21

May be with a proper documentation and an appropriate parameter, the same method could be used for both definitions, no?

[tabus]

comment:22

Replying to @dcoudert:

May be with a proper documentation and an appropriate parameter, the same method could be used for both definitions, no?

Absolutely, but in that case the implementation over at #29346 should be used, mine has a lot of simplifications due to the restriction to connected graphs

[mkoeppe]

comment:23

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[dcoudert]

comment:24

red flag

[mkoeppe]

comment:26

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:27

Setting a new milestone for this ticket based on a cursory review.