Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Phira Oct 30 '11 at 16:12
    
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. –  wircho Oct 30 '11 at 16:33
    
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. –  Phira Oct 30 '11 at 16:38
    
You are right. I had not read that in detail. I still hope there is a faster algorithm. –  wircho Oct 30 '11 at 16:53
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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