# How can I construct a random graph, which is created by adding orientation to a complete graph?

Given a complete graph on N vertices, how can I randomly orient all of its edges? I thought about starting out with CompleteGraph[n], and then somehow transforming its adjancecy matrix, but I can't seem to find an easy way to do this.

Update:

The simple way to do this is

DirectedGraph[CompleteGraph[5], "Random"]


You can use

Graph[DirectedEdge @@@ RandomSample /@ List @@@ EdgeList@CompleteGraph[n]]


Let's break it down:

• EdgeList gives you the edge list

• List @@@ is used to convert each directed edge a <-> b to a list of pairs {a, b}. See also Apply.

• RandomSample[{a,b}] returns a and b in random order. See also Map.

Then we convert them back to directed edges and construct a Graph.

A similar alternative:

Graph[DirectedEdge @@@ RandomSample /@ Subsets[Range[n], {2}]]


Transforming the adjacency matrix is a viable solution. Let m be an n*n two-dimensional adjacency matrix for the complete graph (ones at every off-diagonal element, zeroes on the diagonal). This snippet of code should work:

Do[Do[{m[[i,j]],m[[j,i]]}=RandomChoice[{{0,1},{1,0}}],{i,1,j-1}],{j,2,n}]


The two nested Do functions cycle through all matrix elements where i<j, that is those on one side of the diagonal. As the graph was initially complete, all such elements m[[i,j]] were equal to 1 and had a corresponding element m[[j,i]] (the symetrically located one) also equal to 1. To orient a give edge we must either make m[[i,j]] equal to 1 and m[[j,i]] equal to 0 or vice versa, which is exactly what

{m[[i,j]],m[[j,i]]}=RandomChoice[{{0,1},{1,0}}]


does.

UPD

As Szabolcs suggests, for extra brevity (perhaps at the expense of readability for people unfamiliar with Mathematica) a shorter version of that line of code:

Do[{m[[i,j]],m[[j,i]]}=RandomSample[{0,1}],{j,2,n},{i,1,j-1}]

• It's not necessary to nest Do. Do[..., {i, 1, n}, {j, 1, i-1}] works. RandomChoice[{{0,1},{1,0}}] is equivalent to RandomSample[{0,1}]. – Szabolcs Mar 13 '15 at 1:21
• Thanks for filling me in. I've always had my doubts when one iterator was dependent on the other, so I always nested the Do's, but that does indeed work (the other way round ...{j,1,i-1},{i,2,n}] doesn't though). Nice to know any little tricks that get a line of code even shorter. – LLlAMnYP Mar 13 '15 at 1:37
n = 8;
u = UpperTriangularize[RandomInteger[{0, 1}, {n, n}], 1];
am = u + LowerTriangularize[1 - Transpose@u, -1];