While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain number of vertices or edges (vertices would be enough as I can group them by edges later).

Generating all labeled graphs and then choosing a representative from each class is NOT an option. This would take too long.

Something like "the orderly method" from this website http://www.cs.uc.edu/~andersr9/interests/enumeration-of-unlabeled-graphs/ would work for me, but I couldn't find the original source.

Remark: A description of a canonical way of labeling an unlabeled graph will probably be enough for me at this moment. I might be able to devise an algorithm from there. However, a more precise answer would be greatly appreciated.

  • $\begingroup$ The link suggests that this method is for conserving memory not for gaining speed. Since the canoncial labelling has to be equivalent to isomorphism checking, it is not very likely that it can be speedy. $\endgroup$ – Phira Oct 30 '11 at 16:12
  • $\begingroup$ As I understand it, a "canonical labeling" doesn't have to be equivalent to isomorphism checking. A simple example: You wish to generate subsets of $X=\{1,...,n\}$ with the isomorphism $A\sim B$ if $∣A∣=∣B∣$. The canonical representative of the class $\{A:∣A∣=k\}$ is ${1,2,…,k}$, and the generation of these canonical representatives is much easier, lighter and faster than looking at all subsets and checking the isomorphism. Of course this is an extremely simple example so you might be right in this case. I haven't seen the actual algorithm. $\endgroup$ – wircho Oct 30 '11 at 16:33
  • $\begingroup$ What you write about the example is true, but this does not correspond at all to the procedure described in your link. The procedure in the link explicitly necessitates a procedure that checks a labelling for canonicity for all trees in the $n-1$ list. The canoncial labelling would have to be very special for this to be easier than isomorphism checking. $\endgroup$ – Phira Oct 30 '11 at 16:38
  • $\begingroup$ You are right. I had not read that in detail. I still hope there is a faster algorithm. $\endgroup$ – wircho Oct 30 '11 at 16:53

I would suggest using Nauty by Brendan McKay. It is very quick for up to 10 vertices (and at this point the compressed list of graphs are about 100MB). More specifically, use geng 10 -l > v10.g6.txt to create the graphs on 10 vertices, canonically labelled. There are 12005168 (1.2e7) unlabeled graphs on 10 vertices found in 8 seconds. Brendan McKay's webpage has information on the canonical labelling and the generation algorithms used. The program is distributed as source code and is very widely used.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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