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

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.

  • 1
    $\begingroup$ With 'directed ones' you mean replacing all UndirectedEdge-s with DirectedEdge-s?. $\endgroup$ Commented Feb 7, 2015 at 18:44
  • 2
    $\begingroup$ 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]; $\endgroup$
    – MostafaMV
    Commented Feb 7, 2015 at 19:45
  • $\begingroup$ 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. $\endgroup$ Commented Feb 7, 2015 at 22:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Commented Feb 8, 2015 at 15:17

3 Answers 3


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.

   Cases[graphs,x_/; Length@WeaklyConnectedComponents[x]==1]]



4 vertices

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


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



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.


Show all the directed, connected graphs with 3 vertices:

displayDirectedGraphs /@ connectedUndirectedGraphs[3]


displayDirectedGraphs /@ connectedUndirectedGraphs[4]


  • 2
    $\begingroup$ 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. $\endgroup$ Commented Feb 15, 2015 at 23:53
  • $\begingroup$ I wasn't aware of that limitation. Thanks. $\endgroup$
    – DavidC
    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]]

enter image description here

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

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]

enter image description here

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

enter image description here

  • $\begingroup$ +1 Nice use of graph names, "Connected", and isomorphism. $\endgroup$
    – DavidC
    Commented Feb 8, 2015 at 0:02
  • $\begingroup$ 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]]] $\endgroup$
    – DavidC
    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:


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]

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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