3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

Update:

The simple way to do this is

DirectedGraph[CompleteGraph[5], "Random"]

enter image description here


Old answer:

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}]]
$\endgroup$
0
$\begingroup$

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}]
$\endgroup$
  • $\begingroup$ 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}]. $\endgroup$ – Szabolcs Mar 13 '15 at 1:21
  • $\begingroup$ 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. $\endgroup$ – LLlAMnYP Mar 13 '15 at 1:37
0
$\begingroup$
n = 8;
u = UpperTriangularize[RandomInteger[{0, 1}, {n, n}], 1];
am = u + LowerTriangularize[1 - Transpose@u, -1]; 
AdjacencyGraph[am, GraphLayout -> "CircularEmbedding"]

enter image description here

$\endgroup$
  • $\begingroup$ See the update to my answer for a simple way. $\endgroup$ – Szabolcs Feb 6 '18 at 10:13
  • $\begingroup$ @Szabolcs, excellent!! $\endgroup$ – kglr Feb 6 '18 at 15:20

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.