Graph Theory – Simple Algorithm to Generate Unlabeled Graphs

algorithmscombinatoricscomputer sciencegraph theory

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.

Best Answer

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.

Related Solutions

[Math] Enumerate non-isomorphic graphs on n vertices

See e.g. https://oeis.org/A000088 and references given there.

[Math] Labeling vertices in a graph

Consider the very simple tree with one vertex of degree $2$ and two vertices of degree $1$. If I don’t label the vertices, all such trees are isomorphic: for all practical purposes there is only one such tree, though I can draw it in various ways. Two of these ways are shown below:

            *                     
           / \                  *--*--*  
          *   *

No matter how I draw it, the vertex of degree $2$ is adjacent to each of the other two vertices.

If I label the vertices with the numbers $1,2$, and $3$, however, there are $3$ distinguishable trees: the vertex of degree $2$ can always be distinguished from the other two vertices, since they have a different degree, so labelling that vertex $1$ is different from labelling it $2$ or $3$. The three labelled trees shown below are not the same when the labelling is taken into account:

        1--2--3           2--1--3              1--3--2

However, the first of these is indistinguishable from

        3--2--1

which is just the same labelled tree turned around: both have vertex $2$ as the unique vertex of degree $2$, and it is adjacent to each of vertices $1$ and $3$. It’s still the same labelled tree when I draw it in either of these ways:

           2                   2  
          / \                 / \  
         3   1               1   3

To give a concrete, everyday example, a family tree for one person extending back to the grandparents looks (in almost all cases) like this:

         D   E   F   G  
          \ /     \ /
           B       C
            \     /
             \   /
              \ /  
               A

The vertices are labelled with the names of the people involved. If you shift the labels around, you get a different family tree. A is a child of B, but if you interchange the labels A and B, you have a tree showing B as the child of A, a very different thing.

Best Answer

Related Solutions

[Math] Enumerate non-isomorphic graphs on n vertices

[Math] Labeling vertices in a graph

Related Question