5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ With 'directed ones' you mean replacing all UndirectedEdge-s with DirectedEdge-s?. $\endgroup$ – Sjoerd C. de Vries Feb 7 '15 at 18:44
  • $\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 Feb 7 '15 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$ – Daniel Lichtblau Feb 7 '15 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 Feb 8 '15 at 15:17
6
$\begingroup$

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]

4 vertices


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}]

deges


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]

three


displayDirectedGraphs /@ connectedUndirectedGraphs[4]

four

$\endgroup$
  • 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$ – DumpsterDoofus Feb 15 '15 at 23:53
  • $\begingroup$ I wasn't aware of that limitation. Thanks. $\endgroup$ – DavidC Feb 16 '15 at 0:06
4
$\begingroup$

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:

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]

enter image description here

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

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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