Wednesday, July 16, 2008

Graph Isomorphism

I have just reproduced some of the graph isomorphism doctests with the new partition refinement code. Of the two files meant to replace graph_isom.pyx, one is over a thousand lines and one is around 300 lines. The graph-specific parts become the 300 lines, and the generic stuff is most of it. I'm currently scraping graph_isom.pyx for useful tests of this new software. In a day or two, I should have a complete replacement for the current graph isomorphism code, which will show up on trac as a patch. I'm particularly excited to demonstrate some nontrivial calculations using the new software, such as the sizes of the automorphism groups of the dodecahedron and the cube (search_tree_old is a function with the same signature as the function in graph_isom.pyx which uses the new architecture):

sage: import sage.groups.perm_gps.partn_ref.refinement_graphs
sage: st = sage.groups.perm_gps.partn_ref.refinement_graphs.search_tree_old

sage: G = graphs.DodecahedralGraph()
sage: Pi = [range(20)]
sage: st(G, Pi, order=True)[2]
120

sage: G = graphs.CubeGraph(3)
sage: G.relabel()
sage: Pi = [G.vertices()]
sage: st(G, Pi, order=True)[2]
48

No comments: