I seem to think of equality as something trivial. Granted that structural equality isn't graph isomorphism. But I don't see why something as specific and performance-sensitive as that deserves the tag "equality". Make a function graphsIsomorphic(), where's the problem?

Btw. in my practice (writing really dull code, and some algorithms) I've never seen the need for complex equality functions. In practice I test IDs - typically integers or short strings.