[GSOC20] Diameter, radius, eccentricities, and distances

[João Tavares]

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 the algorithm specified in [d2].

I've only implemented the algorithm for undirected graphs and intend to incrementally make the necessary changes up to the full implementation.

Having submitted a small enhancement a while back I have some experience with trac however I have a small question.

Is it acceptable for me to push my current implementation to trac under the need_work tag and perhaps get some feedback regarding the style or the placement of the functions?

Thanks for the replies in advance.

Best regards,
João Tavares

IST - Lisbon University

P.S. This e-mail might be a duplicate. I thought I had sent a similar e-mail earlier but I can't seem to find it on the sage-gsoc page

[João Tavares]

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

[David Coudert]

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.

[João Tavares]

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?

> --
> 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 sage-gsoc+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/46f0612e-4736-4a7a-883d-83a53748ee4e%40googlegroups.com.

[David Coudert]

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.

> To unsubscribe from this group and stop receiving emails from it, send an email to sage...@googlegroups.com.

[Madhav Wagle]

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

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

[João Tavares]

> 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

> To unsubscribe from this group and stop receiving emails from it, send an email to sage-gsoc+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/ab9ea629-92c0-4be6-9505-b952952ecafd%40googlegroups.com.

[David Coudert]

• it is possible to use C++ in Cython
• It is also possible to make an efficient implementation in C++ and to make an optional (experimental) package making an interface for Sagemath 

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/ab9ea629-92c0-4be6-9505-b952952ecafd%40googlegroups.com.