search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.46k stars 484 forks source link

Exact Algorithm for Diameters of Large Real Directed Graphs #29309

Open dda6db36-28bb-4f5a-b05b-dbe429983e68 opened 4 years ago

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago

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

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago

Branch: u/gh-tabus/exact_algorithm_for_diameters_of_large_real_directed_graphs

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago

New commits:

febaa2eFirst implmentation (only for undirected graphs)
dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago

Commit: febaa2e

dcoudert commented 4 years ago
comment:3

A few comments:

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from febaa2e to fa9a391

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

86d5bb8Cleanup files and add tests
fa9a391Added support for DiGraph + Fixed bug concerning the doublesweep
dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago
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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

b6e4ac4Fixing the notation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from fa9a391 to b6e4ac4

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago
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?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

2fc27daChange to simple_BFS
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from b6e4ac4 to 2fc27da

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago

New commits:

febaa2eFirst implmentation (only for undirected graphs)
86d5bb8Cleanup files and add tests
fa9a391Added support for DiGraph + Fixed bug concerning the doublesweep
b6e4ac4Fixing the notation
2fc27daChange to simple_BFS
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 2fc27da to 121fa76

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

25010cbWorking version of the implementation
121fa76Merge 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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 121fa76 to 0e87a2b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

0e87a2bFix the merge mistakes
dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago

Author: João Tavares

videlec commented 4 years ago
comment:13

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 0e87a2b to 81a019f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

81a019fAdded doctests
dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago
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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

781538fAdded note to doctest warning that the method is faster for sparse graphs
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 81a019f to 781538f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 781538f to a79cfd1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

a79cfd1Added reference + Disposed of memory
dcoudert commented 4 years ago
comment:19

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

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago
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 commented 4 years ago
comment:21

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

dda6db36-28bb-4f5a-b05b-dbe429983e68 commented 4 years ago
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 commented 4 years ago
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 commented 4 years ago
comment:24

red flag

mkoeppe commented 3 years ago
comment:26

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

mkoeppe commented 3 years ago
comment:27

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