But the algorithm described in [d2] seems to be designed for digraphs which aren't strongly connected( with a modified definition of diameter ). Even the experimental results mentioned in the paper are on digraphs which are not strongly connected. [d2] is definitely giving the correct answer for strongly connected graphs but is slower in some cases
[image: plot0.042.png] This is the summary of testing on random sparse digraph with edge probability *p* The x axis is number of nodes The y axis is % increase in run time of new algorithm with respect to original algorithm On Monday, 16 March 2020 13:48:31 UTC+5:30, David Coudert wrote: > > The first step is to somehow draw a map of the different algorithms that > are already available in Sagemath, and the conditions to use them > (directed, undirected, weighted, multi edges, etc.), and the data structure > used. > Then we can decide how to proceed. > > A general definition is that the diameter of a non connected undirected > graph is +oo. > Similarly, the diameter of a non strongly connected directed graph is +oo. > We should use these definitions. > > Le dimanche 15 mars 2020 00:59:14 UTC+1, João Tavares a écrit : >> >> Thanks for the reply and for the corrections on trac. >> While trying to fix and issue I found that I was essentially >> reinventing the wheel and that my problem had been solved elsewhere on >> the codebase. >> However when I tried to understand how they had deal with it I found >> they had not. >> >> The article [d2] seems to use a different definition of eccentricity >> and by extension of diameter where the graph does not need to be >> connected. >> Meaning sage.graphs.distances_all_pairs.diameter() would return >> different values for different algorithms, which as a user I would not >> expect. >> How has Sage dealt with these cases in the past? Should I restrict it >> to the previous definition or maybe have a different function with a >> different name? >> >> >> >> On Mon, Mar 9, 2020 at 8:27 PM David Coudert <[email protected]> wrote: >> > >> > Thank you for your interest in this project. >> > >> > If you push your code to a ticket, we will certainly help you improving >> it. We do our best to help all contributors. >> > >> > Sincerely, >> > David. >> > >> > Le lundi 9 mars 2020 20:05:24 UTC+1, João Tavares a écrit : >> >> >> >> Hello, >> >> >> >> >> >> I am a third year undergraduate student from IST - Lisbon University >> in Applied Mathematics and Computer Science. I am very >> >> interested in the "Diameter, radius, eccentricities, and distances" >> project. In fact I have started implementing [d2]. >> >> >> >> I have some knowledge about the trac system, having submited a small >> enhancement in the past, however I have a small question regarding it. >> >> >> >> Is it acceptable for me to push my current implementation to trac >> under the need_work tag and perhaps get some feedback? I have been working >> under the assumption the given graph is undirected (temporarily) so my code >> is not yet complete. >> >> >> >> >> >> Thanks for the replies in advance. >> >> >> >> >> >> Best regards, >> >> >> >> João Tavares >> >> >> >> IST - Lisbon University >> > >> > -- >> > 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/46f0612e-4736-4a7a-883d-83a53748ee4e%40googlegroups.com. >> >> >> > -- 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/caf78c35-7cea-43ab-96a8-80742c3e664d%40googlegroups.com.
