Robert Miller wrote:
> 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?
Is there a reason that you don't convert to C graphs by default anymore?
I can see this preventing at least some people from getting fast
answers and having a bad opinion of Sage :(.
Jason
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
