> 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. I pushed my changes to trac yesterday with the simplifications resulting from using this definition. After testing with a couple of graphs it seems to run faster than the previous algorithm for sparse graphs. I've implemented it in Cython because it seems to be the preferred option but perhaps a C/C++ implementation would be even faster.
Thanks for the reply. João Tavares On Mon, Mar 16, 2020 at 8:18 AM David Coudert <[email protected]> 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/ab9ea629-92c0-4be6-9505-b952952ecafd%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/CAJEthcRD%3DuLmjo96C8wfzW8JLTAC91eNwKLhtbp6tmCnmc790w%40mail.gmail.com.
