Oriented Graph

Author

Eric W. Weisstein
June 3, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/OrientedGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/OrientedGraph.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

OrientedGraphs[n_]:=OrientedGraphs[n]=Tally[Sort[Join@@(OrientedSets/@Graphs[n])]][[All,1]]

OrientedSets[g_System`Graph]:=Module[{e=List@@@EdgeList[g],t,m=EdgeCount[g],n=VertexCount[g]},
If[m===0,Return[{g}]];
t=Transpose[{e,Reverse/@e}];
Tally[Sort[CanonicalGraph[System`Graph[Range[n],DirectedEdge@@@#]]&/@Flatten[Outer[List,Sequence@@t,1],m-1]]][[All,1]]
]

Oriented Graphs

A001174

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, 816007449011040, 4374406209970747314, 64539836938720749739356, 2637796735571225009053373136, 300365896158980530053498490893399

Clear[OrientedGraphs]

Do[Print[{n,Length[OrientedGraphs[n]]//Timing}],{n,6}]

V5

ShowGraphArray[Flatten[
Map[Partition[#,7,7,{1,1},{}]&,
Select[#,OrientedQ]&/@Digraphs/@Range[3],
{1}],1]
]

V6

GraphicsGrid[Map[SetProperty[#,GraphLayout->"CircularEmbedding"]&,OrientedGraphs/@Range[3],{2}],Dividers->All]

Weakly Connected Oriented Graphs

A086345

1, 1, 5, 34, 535, 20848, 2120098, 572849763, 415361983540, 815590925440865, 4373589784210012634, 64535461714821630421106, 2637732191356603658136444467, 300363258297687600380548275359231

Do[Print[{n,Count[OrientedGraphs[n],_?WeaklyConnectedGraphQ]//Timing}],{n,6}]

V5

ShowGraphArray[Flatten[
Map[Partition[#,7,7,{1,1},{}]&,
Function[f,Select[f,ConnectedQ[#]&&OrientedQ[#]&]]/@Digraphs/@Range[3],
{1}],1]
]

V6

GraphicsGrid[Map[SetProperty[#,{GraphLayout->"CircularEmbedding",EdgeShapeFunction->GraphElementData[{"HalfFilledArrow","ArrowSize"->.1}]}]&,Cases[OrientedGraphs[#],_?WeaklyConnectedGraphQ]&/@Range[3],{2}],Dividers->All]