On Apr 28, 7:10 pm, William Stein <wst...@gmail.com> wrote: > Maple13 was released today, I think. > ... > Looking it over, the only overlap with Sage (current or in > development features) seems to be the following: > * They now have graph isomorphism testing > * They now have graph enumeration > ... > We've had very good implementations of the first four above > for over a year, and I'm looking forward to seeing if our > implementations in Sage blow them away or not.
Here are a couple of graph theoretic timing comparisons between Sage 4.0.alpha0 and Maple 13. They were performed on my Macbook Pro running OSX 10.4.11. They indicate that Maple generates graphs a bit faster but Sage tests isomorphisms *much* faster. In neither case is the difference a simple linear factor, rather the time complexities seem to be fundamentally different. The tests I ran are as follows: 1) Generate all graphs with n vertices. 2) Verify that all the generated graphs are, indeed, distinct. Sage, n = 5: Test 1: 0.13s Test 2: 0.02s Sage, n = 6: Test 1: 1.1s Test 2: 0.3s Sage, n = 7: Test 1: 12.9s Test 2: 13.5s Maple, n = 5: Test 1: 0.018s Test 2: 0.13s Maple, n = 6: Test 1: 0.08s Test 2: 10.8s Maple, n = 7: Test 1: 0.63 Test 2: Locked up after 10 minutes. Here is the code I used (I can't promise that it's the best): Sage: %time n = 5 some_graphs = list(graphs(n)) some_graphs = [g.copy(implementation='c_graph') for g in some_graphs] %time result = false for i in xrange(0,len(some_graphs)-1): for j in xrange(i+1, len(some_graphs)): if some_graphs[i].is_isomorphic(some_graphs[j]): result = true break if result: break result Maple: with(GraphTheory); n := 5; t := time(); mygraphs := NonIsomorphicGraphs(n, output = graphs, outputform = graph); time()-t isomorphicpairs := false; t := time(); for i to NonIsomorphicGraphs(n) do for j from i+1 to NonIsomorphicGraphs(n) do if IsIsomorphic(mygraphs[i], mygraphs[j]) then isomorphicpairs := true end if end do end do: time()-t Mark McClure --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---