I have opened a ticket for DiFUB <https://trac.sagemath.org/ticket/29422> #29422 <https://trac.sagemath.org/ticket/29422>
On Friday, 27 March 2020 15:23:42 UTC+5:30, David Coudert wrote: > > 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, > > Le vendredi 27 mars 2020 08:12:32 UTC+1, Madhav Wagle a écrit : >> >> 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 >> <https://snap.stanford.edu/data/soc-Epinions1.html> (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? >> >> -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/66778b93-69da-483a-945d-bbcebc0de4da%40googlegroups.com.
