# Enumerating all connected graphs with 9 vertices

The version of my Mathematica is 10. I generate a connected graph with 9 vertices, but find that it is not included in Mathematica.

adjm = {{0, 1, 0, 0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 0, 1, 0}, {0, 1, 0,
1, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 1,
0, 0, 0}, {0, 0, 0, 1, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 1,
1}, {0, 1, 1, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0}};
(*generate the graph g1*)
ori2 = GraphData;
set2 = GraphData[#] & /@ ori2;
set3 = Select[set2, ConnectedGraphQ[#] == True &];
IsomorphicGraphQ[g1, #] & /@ (set3)
(*generate all the graphs with 9 vertices, select the connected ones and check if g1 is there*)


The output is a list of False.

If I have missed something. Then the question is how to get the database of all connected graphs with 9 vertices?

• Very important for all such questions: what precise version of Mathematica are you using, on what operating system? – Szabolcs Sep 26 '14 at 12:50
• OK, I looked at your code. I cannot run it because at the moment I do not have access to a fast enough internet connection to be able to download all the graph data ... However, you seem to be assuming that GraphData will return all possible graphs on 9 vertices. I do not see why this should be so. It is just a non-exhaustive graph database, don't assume it contains everything. – Szabolcs Sep 26 '14 at 12:54
• Actually there seem to be no less than 274668 unlabelled graphs on 9 vertices ... which is much more than what the database can be expected to contain. Voting to close since this question is due to a simple misunderstanding. – Szabolcs Sep 26 '14 at 12:56
• @Szabolcs Thanks! I update the question. – Eden Harder Sep 26 '14 at 13:21
• There is no such database built into Mathematica, so for a pre-made database you'd have to look elsewhere. Generating all unlabelled graphs on 9 vertices and making sure there are no duplicates in the list is going to be hard and definitely impossible using a naive approach of simply using IsomorphicGraphQ to filter duplicates. Not to say it's impossible with smarter methods (it probably is), but how to do it seems hard enough that I'd say it's a math question first, and a Mathematica question only once you have a strategy in mind ... – Szabolcs Sep 26 '14 at 13:32

Here is a recursive way to get them all: (slow due to the use of IsomorphicGraphQ inside DeleteDuplicates, if anybody knows how to do it faster, please comment). Much faster now thanks to @MarkMcClure's clever improvement.

Edit

Improved again by 40% prefiltering the added rows using the automorphisms of the n-1 graph:

<< Combinatorica
filtPerms[skel_, rows_] := Module[{perms, gathered},
gathered = GatherBy[rows, Tr@# &];
Flatten[ DeleteDuplicates[#, MemberQ[SystemPermute[#1, PermutationGroup[perms]], #2] &] & /@
gathered, 1]
]
getConnG = {{{0, 1}, {1, 0}}};
getConnG[n_] := getConnG[n] =
skels = ArrayPad[#, {{1, 0}, {1, 0}}] & /@ getConnG[n - 1];
rows = Rest@Tuples[Join[{{0}}, Array[{0, 1} &, n - 1]]];
adjk = (Unitize@(# + Transpose@#) & /@
Flatten[Flatten[Outer[ReplacePart[#1, 1->#2]&, {#}, filtPerms[#,rows],  1], 1] & /@ skels, 1]);
gathered, 1]]

GraphicsGrid@Partition[Framed /@ AdjacencyGraph /@ getConnG@6, 8] • I modified your code slightly so that getConnG runs in 5 seconds as opposed to 30 seconds on my machine. The major point is that DeleteDuplicates has quadratic time complexity when using a user defined comparison function. Thus, breaking the list of graphs in smaller parts using the total number of edges helps a lot. Of course, DeleteDuplicates can run like $n\log(n)$, when the data is linearly ordered, but that's not generally possible with a user defined comparison function. – Mark McClure Sep 27 '14 at 12:38
• getConnG in about 6 minutes. – Mark McClure Sep 27 '14 at 12:55
• @MarkMcClure Thanks! Sound good, very clever. I'm trying to filter the rows to use on each getConnF[n-1] based on the Automorphisms[] of the getConnF[n-1] and its permutation group to produce much less isomorphic results to be discarded later. – Dr. belisarius Sep 27 '14 at 18:38
• @MarkMcClure I've done it. Resulted in a 40% time gain. – Dr. belisarius Sep 27 '14 at 21:56
• Should be faster if you use FindIsomorphism[g,g,All] on a Graph object. On my iPhone right now so I can't try it just now. – Mark McClure Sep 27 '14 at 22:21

The geng tool of the nauty suite can generate all non-isomorphic connected graphs on a specified number of vertices. The format used by nauty is directly supported by Mathematica, making it easy to use these tools.

I installed nauty using MacPorts (sudo port install nauty), but it's generally easy to compile on Unix-like systems. Once you have the geng binary, simply use the command below (adjusting the path to geng appropriately).

cg = Import["!/opt/local/bin/geng -c 9", "Graph6"];

Length[cg]
(* 261080 *)


(This takes a minute or so.)

As you can see, there are 261,080 connected non-isomorphic graphs on 9 vertices.

If you want even larger graphs, it will be useful to read them one-by-one. You can do it like so:

geng = StartProcess[{"/opt/local/bin/geng", "-c", "9"}]
Import[geng, {"Graph6", "GraphList", 123}] (* read 123th graph from the output *)


The website http://cs.anu.edu.au/~bdm/data/graphs.html contains a list of all unlabelled graphs, with up to 10 vertices.

Update: As @paw says in a comment, the format used on this website can be read directly by Mathematica, so the conversion I described below is not necessary: Graph6.

It uses a special format, which can be converted to an adjacency matrix using the showg program, downloadable (as C source code) from here.

I compiled showg on a Unix-like system with the command

cc -O2 showg.c -o showg


then imported e.g. the graph H???C@w to Mathematica using

First@ImportString[#, "Table"] & /@ Rest@Import["!echo H???C@w | ~/test/showg -A", "Lines"]


(I'm sure this can be done better...)

• Yes this can be done better. Mathematica supports .g6 natively and you can import the list of graphs with n vertices with gSet[n_] := Import["http://cs.anu.edu.au/~bdm/data/graph" <> ToString@n <> ".g6"]; – paw Sep 26 '14 at 13:54

You can generate a connected random graph with the same number of vertices and edges as g1.

adjm = {{0, 1, 0, 0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 1,
0, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 0,
0}, {0, 0, 0, 1, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 1, 1}, {0, 1, 1, 0,
0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0}}; 