# Using GraphData to generate all directed graphs with n vertices

Using Combinatorica, it was possible to generate unlabeled (non-isomorphic) directed graphs of $|V|=n$. Here the example is for $n=4$:

Needs["Combinatorica"]
ShowGraph /@ ListGraphs[4,Directed];


Using GraphData, I know how to generate undirected ones:

GraphData /@ GraphData[4]


What's the trick to make it generate directed ones?

Bonus point for directed and connected ones.

• With 'directed ones' you mean replacing all UndirectedEdge-s with DirectedEdge-s?. Commented Feb 7, 2015 at 18:44
• No actually the number of directed graphs with n nodes is larger than the undirected graphs with the same number of nodes. Just compare ShowGraph /@ ListGraphs[4,Directed]; with ShowGraph /@ ListGraphs[4]; Commented Feb 7, 2015 at 19:45
• Yeah but for n edges there are 2^n choices for directing. Maybe some things become isomorphic to others but still it should give that enlarged set. Commented Feb 7, 2015 at 22:41
• Keep in mind that GraphData is just a database of graphs. It's not exhaustive, and it doesn't generate graphs. It just looks up the database entries. Commented Feb 8, 2015 at 15:17

# Directed, Connected Graphs of n vertices

First let's find the undirected graphs of n vertices. We're only considering those graphs having a single weakly-connected component.

connectedUndirectedGraphs[n_]:=Module[{graphs},graphs=GraphData/@GraphData[n];
Cases[graphs,x_/; Length@WeaklyConnectedComponents[x]==1]]


example

connectedUndirectedGraphs[4]


This imposes a direction on an (undirected) edge. The direction depends on the value of 'bool.

directTheEdge[a_<->b_,bool_]:=If[bool==1,b\[DirectedEdge]a,a\[DirectedEdge]b]


(* The following finds all the combinations of directed edges for a set of undirected edges *)

directedEdges[unDirectedEdges_]:=


example:

directedEdges[{1 <-> 4, 2 <-> 4, 3 <-> 4}]


Display the directed graphs that can be produced from a single undirected graph. Isomorphism check based on kguler's approach.

displayDirectedGraphs[unDirectedGraph_]:=
Module[{el,d},el=EdgeList[unDirectedGraph];d=directedEdges[el];
DeleteDuplicates[Flatten[Graph[#,
EdgeShapeFunction->GraphElementData[{"HalfFilledArrow","ArrowSize"->.18}],
VertexLabels->"Name"]&/@d],IsomorphicGraphQ]]


Show all the directed, connected graphs with 3 vertices:

displayDirectedGraphs /@ connectedUndirectedGraphs[3]


displayDirectedGraphs /@ connectedUndirectedGraphs[4]


• Nice. One minor but important point: GraphData["Connected", n] only gives a complete list of all non-isomorphic graphs on $n$ vertices for $1\leq n \leq 7$, and thus this fails when $n\geq 8$. Of course, there are a lot of graphs when $n$ gets that large (11,117 with $n=8$ and 261,080 when $n=9$), so this limitation is sort of to be expected. Commented Feb 15, 2015 at 23:53
• I wasn't aware of that limitation. Thanks. Commented Feb 16, 2015 at 0:06

We can get connected undirected graphs on four vertices using

c4 = GraphData["Connected", 4];


Names and images:

Row[Column[GraphData[#, {"StandardName", "Image"}]] & /@ c4, Spacer[10]]


Define a function that gives all (non-isomorphic) directed graphs when input a list of edges:

ClearAll[dgF];
dgF[opts : OptionsPattern[]] := Module[{el = #, tpls = Tuples[{Identity, Reverse}, Length@#]},
DeleteDuplicates[Graph[MapThread[Thread[#[#2]] &, {#, el}], opts] & /@ tpls,
IsomorphicGraphQ]] &;


and set some options:

options = {VertexLabels -> Placed["Name", Center], VertexSize -> .3, ImageSize -> {200, 200},
EdgeShapeFunction->GraphElementData[{"FilledArrow", "ArrowSize"->.1, "ArrowPositions" ->.75}]};


Combining all into a function that takes an integer and options as arguments (as suggested by David):

graphsF[n_, opts : OptionsPattern[Graph]] :=
Module[{c = GraphData[#, {"Name", "Image", "EdgeRules"}] & /@ GraphData["Connected", n]},
Grid[{Rotate[Style[#1, "Panel", 14], Pi/2],Magnify[#2, .5], ## & @@ dgF[opts][#3]} & @@@ c,
Dividers -> {{True, True, {False}, True}, All}]]

graphsF[4, VertexCoordinates -> Thread[Range[4] -> Tuples[{0, 1}, 2]], ## & @@ options]


graphsF[3, VertexCoordinates -> Thread[Range[3]->{{0, 0}, {0, 1}, {1, 0}}], ## & @@ options]


• +1 Nice use of graph names, "Connected", and isomorphism. Commented Feb 8, 2015 at 0:02
• A generalization of your method for labeling: graphs[n_] := Module[{c, cb}, c = GraphData["Connected", n]; cb = GraphData[#, "EdgeRules"] & /@ c; Row[Column[GraphData[#, {"StandardName", "Image"}]] & /@ c, Spacer[10]]] Commented Feb 8, 2015 at 0:42

The following is by far the most efficient solution (let me know if you know a better one).

You can use the geng tools from the nauty suite to generate non-isomorphic undirected graphs with various constraints. The directg tool can take un undirected graph as input, and generate all non-isomorphic directed ones by orienting its edges as ->, <- or <->.

These tools use the Graph6, Digraph6 and Sparse6 format for interchanging graphs. Mathematica has built-in support for Graph6 and Sparse6, but not for Digraph6. The [IGraph/M package](http://szhorvat.net/mathematica/IGraphM adds support for Digraph6 and improves the import performance for Graph6 and Sparse6.

Assuming that the nauty suite is installed and in your path, you can do the following:

Needs["IGraphM"]


Generate all unlabelled directed graphs on 4 vertices, and count them:

IGImport["!geng 4 | directg", "Nauty"] // Length
(* 218 *)


The same on 5 vertices:

IGImport["!geng 5 | directg", "Nauty"] // Length
(* 9608 *)


Count how many are strongly connected. The -c option of geng generates only connected undirected graphs, which reduces the number of graphs that we need to import into Mathematica for further processing, and improves performance:

IGImport["!geng -c 5 | directg", "Nauty"] // Select[ConnectedGraphQ] // Length
(* 5048 *)


Orient each edge in only one direction (-o) and select strongly connected graphs:

IGImport["!geng -c 4 | directg -o", "Nauty"] // Select[ConnectedGraphQ]


Pre-filtering using the options of geng and directg can vastly improve performance. This takes only 1.6 seconds on my machine:

IGImport["!geng -c 6 | directg -o", "Nauty"] // Select[ConnectedGraphQ] // Length
(* 4232 *)
`

In total, there are 1.5 million directed graphs on 6 vertices, which would take much longer to import.