Mark,
Between Sage 3.1.1 and 3.2.3, the background implementation of graph
isomorphism was completely switched over. The old implementation
simply computed canonical labels, but it always constructed a C graph
first. Now, it actually uses an algorithm specifically designed to
test for isomorphism between two inputs, but it uses the underlying
implementation of the input graph. Therefore, 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. If
G is a graph, you can do
sage: H = G.copy(implementation='c_graph')
Here are some benchmarks:
sage: G = graphs.PetersenGraph()
sage: S = SymmetricGroup(10)
sage: H = G.relabel(S.random_element(), inplace=False)
sage: G_C = G.copy(implementation='c_graph', sparse=False)
sage: H_C = H.copy(implementation='c_graph', sparse=False)
sage: G_C_S = G.copy(implementation='c_graph', sparse=True)
sage: H_C_S = H.copy(implementation='c_graph', sparse=True)
sage: timeit('G.is_isomorphic(H)')
625 loops, best of 3: 1.2 ms per loop
sage: timeit('G_C.is_isomorphic(H_C)')
625 loops, best of 3: 206 µs per loop
sage: timeit('G_C_S.is_isomorphic(H_C_S)')
625 loops, best of 3: 208 µs per loop
sage: D = graphs.DodecahedralGraph()
sage: S = SymmetricGroup(20)
sage: H = D.relabel(S.random_element(), inplace=False)
sage: D_C = D.copy(implementation='c_graph', sparse=False)
sage: H_C = H.copy(implementation='c_graph', sparse=False)
sage: D_C_S = D.copy(implementation='c_graph', sparse=True)
sage: H_C_S = H.copy(implementation='c_graph', sparse=True)
sage: timeit('D.is_isomorphic(H)')
125 loops, best of 3: 2.06 ms per loop
sage: timeit('D_C.is_isomorphic(H_C)')
625 loops, best of 3: 305 µs per loop
sage: timeit('D_C_S.is_isomorphic(H_C_S)')
625 loops, best of 3: 312 µs per loop
Does this modification bring you back up to old speed, or hopefully,
even better?
RLM
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
