On Feb 26, 9:35 pm, Robert Miller <rlmills...@gmail.com> wrote:
> Between Sage 3.1.1 and 3.2.3, the background implementation
> of graph isomorphism was completely switched over. ...
> if the input graphs are based on NetworkX graphs, it will
> go much more slowly than it used to. For maximum speed in
> is_isomorphic, you should construct c_graphs.
Thanks Robert, that definitely helps a lot. The results of
my timing tests are below.
Timings:
Graphs7
NetworkX: 26s
Sage 3.1.1: 32s
Sage 3.3: 37s
(c_graphs)
Graphs6
Networkx: 0.55s
Sage 3.1.1: 0.72s
Sage 3.3: 0.79s
(c_graphs)
Again, I imported a collection of graphs and checked that
they were indeed all distinct. Graphs7 is the collection
of all 1044 connected graphs on 7 vertices and Graphs6 is
the collection of all 156 graphs on 6 vertices. I did not
include the Sage 3.3 timings using the old NetworkX graphs
but those timings appear to be about a factor of 4 slower.
I did experiment with sparse=True or sparse=False but the
timings appeared to be unaffected. Of course, these aren't
large matrices.
For clarity, my slightly revised code is below.
import urllib2
f = urllib2.urlopen('http://cs.anu.edu.au/~bdm/data/graph6.g6') # Or
graph7.g6
graph_strings = f.readlines()
f.close()
some_graphs = [Graph(graph_string) for graph_string in graph_strings]
# Switch to the new c_graph implementation.
better_graphs = [g.copy(implementation='c_graph', sparse=False) for g
in some_graphs]
n = len(some_graphs)
%time
# Start with result = false.
# That is, we haven't found a pair of isomorphic graphs.
result = false
for i in xrange(0,n-1):
for j in xrange(i+1, n):
if better_graphs[i].is_isomorphic(better_graphs[j]):
# Change better to some for 3.1.1.
result = true
break
if result:
break
result
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
