Performance of DiFUB

[Madhav Wagle]

Hi,

I have implemented the diFUB (directed iterative fringe bound) algorithm. It is performing very well on all the real directed graphs which I tried:

For Eg .

Epinions social network graph (32223 nodes in largest SCC)

sage: %time m.diameter(algorithm="DiFUB")
CPU times: user 304 ms, sys: 4.02 ms, total: 308 ms
Wall time: 305 ms
16

sage: %time m.diameter()
CPU times: user 28min 55s, sys: 35.4 ms, total: 28min 55s
Wall time: 28min 55s
16

but DIFUB isn't performing well on random graphs( in the worst case may take twice the number of BFS calls as the naive method)

Even though my code is complete, I still plan on adding details to my comments

Shall I open a ticket for this algorithm and open it for review?

[David Coudert]

Your code seems very fast on Epinions.

 

I don't know which parameters you used to generate random graphs, but I assume that you have generated qui dense graphs. Such graphs have low diameter, and so are worse cases for iFUB and DiFUB.

You can of course open a ticket for DiFUB. 

Sincerely,

[Madhav Wagle]

I have opened a ticket for DiFUB

#29422