Using GraphData to generate all directed graphs with n vertices

Question

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.

Answer 1

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_]:=
Thread[directTheEdge[unDirectedEdges,#]]&/@Tuples[{0,1},Length[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]

Answer 2

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]

Answer 3

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.