Le mardi 11 octobre 2016 16:03:44 UTC+2, Travis Scrimshaw a écrit :
>>> Even if it does turn out that this technique performs worse than Sage on 
>>> some graphs, is it worth trying to integrate it as an option for users?
>> Are these algorithms published? (sorry, "Mark Bell" isn't very 
>> googleable; e.g. I found this https://arxiv.org/a/bell_m_3.html
>> but this does not show any graph theory algorithms you mention :-))
>> Surely, have more fast implementations of known algorithms is great; have 
>> implementations of something
>> unpublished, not so---indeed, code reviewers would try to check that the 
>> implementation is implementing
>> something published, but I don't think reviewing correctness of 
>> algorithms is something one would reasonably expect from a 
>> code review.
> I think it is good to add it even if it is not published (although at 
> least an (arXiv) preprint would be nice). In either case, IMO it would be 
> good to have a way of choosing which algorithm to run in the methods, both 
> for testing and verification purposes.

You can already choose various algorithms to compute the diameter. The 
default one for unweighted graphs is iFUB (as proposed by Crescenzi et al). 
This is certainly not the best possible implementation since I have not 
added all the tricks for selecting the first node, but it's working.
Since, various improvements have been proposed in the literature for both 
directed and undirected graphs, but not included yet.
For eccentricity, we also use a smart algorithm (see method 
c_eccentricity_bounding in file distances_all_pairs.pyx).
We should certainly clean (again) these methods to clarify the 
documentation and to keep only the most relevant algorithms. For instance, 
networkx implementations are generally slower.

Concerning graphs for testing your algorithm. You should check on the 
papers by Pierluigi Crescenzi or Michel Habib or Takashi Hakiba etc. the 
graphs they use. Often co-authors graphs, web graphs, etc.
Recently, Laurent Viennot worked on an algorithm for the diameter that he 
has used to compute the diameter of road networks 



> Best,
> Travis

You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Reply via email to