On Tuesday, October 11, 2016 at 11:25:09 AM UTC, Mark Bell wrote: > > I've been working on some new algorithms for computing some properties > (eccentricity, diameter, radius, ...) of (undirected) graphs and I'm > looking for families to test these on. > > I've written a reasonable efficient C extension which implements these > algorithms and so I've started comparing these against the methods > available in Sage. > For many of the graphs that I've tried it appears that this new technique > is faster than Sage. For example, experimentally on: > > > G = graphs.RandomGNP(2001, 0.05) > > this new technique computes the diameter of G ~30% faster than Sage. > > > Is there a standard test suite of graphs that I try running these > procedures on? I think this algorithm should be particularly effective on > graphs with a large number of vertices and a large diameter. Is there a > reasonable way of generating graphs of this form? >
Some "large" graphs of "large" diameter that Sage knows about are distance regular, e.g. graphs.SymplecticDualPolarGraph It's hard to say more without knowing what exactly you're after, what kind of edge density, what kind of diameter as a function of the number of vertices, etc. > > 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. Cheers, Dima -- 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.
