I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if they are isomorphic.

In particular, I'm looking for a simple algorithm that is easy to implement with a reasonable performance on most graphs (worst case super-polynomial, of course). I'm expecting small graphs, so performance doesn't have to be stellar, just good enough.

Unfortunately, most things I've found are highly complex and more interested in expressing deep mathematical connections than simply describing the algorithm. I'm afraid I don't have the time to dive that deep. Can anyone give me a shortcut?

I'm hoping for something like the Floyd-Warshall algorithm. Not optimal, but good enough, and easy to implement.

  • $\begingroup$ Are the graphs labelled consistently? If yes, just write down all the edges and sort the list. $\endgroup$
    – adrianN
    Sep 16, 2013 at 14:26
  • $\begingroup$ Ah, sorry. The vertices and edges are labeled, but not uniquely. Each label can occur mulitiple times. I guess the mathematical phrase is "coloured" rather than labeled. I'll edit the question. $\endgroup$
    – Peter
    Sep 16, 2013 at 14:49
  • $\begingroup$ "worst case NP, of course" -- just so that we are clear: there is known (deterministic) polynomial-time algorithm for graph-isomorphism, so the best you can expect is a super-polynomial solution. And yes, the problem is in NP. See here for details on these notions. $\endgroup$
    – Raphael
    Sep 17, 2013 at 7:50
  • $\begingroup$ @Raphael You're right, more inexact terminology. Worst case is super-polynomial. There are average-case polynomial algorithms, though, so that should at least be achievable. $\endgroup$
    – Peter
    Sep 17, 2013 at 9:02
  • $\begingroup$ @Raphael The best you can expect is a fast algorithm that works for most graphs. $\endgroup$ Sep 17, 2013 at 16:37

3 Answers 3


Brendan McKay and Adolfo Piperno have written a survey paper regarding this question in 2013. They present several efficient computer programs that canonicalize many graphs faster than you would imagine. There is no need (and no point) in implementing these algorithms yourself - they are available online, even as source code.

  • $\begingroup$ There is a reduction between colored GI and GI (with constant multiplicative blowup given a constant number of colors), or perhaps the algorithms themselves could be modified. $\endgroup$ Sep 17, 2013 at 16:41
  • $\begingroup$ Can you describe one here as to give a full answer? $\endgroup$
    – Raphael
    Sep 17, 2013 at 19:35
  • 4
    $\begingroup$ For each color, add an extra vertex. Connect each original vertex to the vertex representing its color by adding an edge. Make sure that the degrees of the "color" vertices are unique - if this is not the case, add loops or other fake edges. By the way, I am less than happy about the McKay/Piperno survey paper - it is a survey of their own research, and the comparisons they make to other tools are on the benchmarks that they consider interesting. They omit important recent developments and almost all benchmarks derived from non-theoretical applications, which affects empirical results. $\endgroup$ Sep 18, 2013 at 21:51

I ended up implementing the Nauty algorithm, but in doing so, I did figure out an answer to my own question. Nauty extends this basic algorithm with many complicated heuristics:

Given a small graphs G of length n:

  1. Loop over all $n!$ permutations of its vertices.
  2. Generate a string representation of each (one-to-one).
  3. Define some canonical ordering of strings, and remember the smallest string encountered.

This algorithm is $O(n!)$, but for small graphs it should work fine.

Nauty extends this algorithm primarily by pruning the search space of graphs to consider, when looking for the one with the smallest string representation.

  • 1
    $\begingroup$ The graphs must be really small if this brute-force approach is plausible. Even $15!$ is greater than $10^{12}$. $\endgroup$ Jun 13, 2016 at 11:53
  • 1
    $\begingroup$ @DavidRicherby Absolutely. However, there are use cases, such as motif analysis, where this operation is only done on graphs of size 3 or 4. In fact, I don't know if finding a canonical isomorphic subgraph can be achieved in reasonable time at all for graphs over 15 nodes (even if subgraph isomorphism itself is now known to be very close to polynomial) $\endgroup$
    – Peter
    Jun 13, 2016 at 12:09

My understanding is that there is a quasi-polynomial time algorithm for graph isomorphism but subgraph isomorphism is np-complete.

  • $\begingroup$ This does not appear to answer the question that was asked. Please use the 'Your Answer' field only for material that directly answers the question that was asked, not for other commentary on general topics related to the question. $\endgroup$
    – D.W.
    Apr 5 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.