Currently SageMath checks for graph isomorphism through an internal package with a corresponding method, called isomorphic and contained in sage.groups.perm_gps.partn_ref.refinement_graphs. This method, in addition to being quite convoluted and without much documentation about its inner workings, was last updated in a significant manner in 2011.
The project aims at creating a new package which implements an efficient in practice heuristic method to check if two graphs are isomorphic, using one of the members of the Weisfeiler-Lehman (WL) algorithm hierarchy. An attempt was made in the past at the same task (but with a narrower scope, limited to only implementing the second order version of the WL algorithm), but the code was found to contain a bug and was never implemented/removed from the codebase (see Trac #10482).
To the best of my knowledge, this would be the first working open-source implementation of k-WL, for k > 1.

Student

Dario Asprone

Mentors

  • Dima Pasechnik
close

2018