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
-~----------~----~----~----~------~----~------~--~---

Reply via email to