Home > documentation, graph theory, Sage > Random oriented graphs

Random oriented graphs

This one is from a recent sage-support thread.

Problem

Let D be a digraph and let u,v be vertices of D. Then D is said to be oriented if at most one of uv, vu is an edge of D. This means that D might not contain any of the edges vu, uv. However, if vu \in E(D), then uv \not\in E(D) and vice versa. The problem now is to generate a random oriented graph.

Solution

A quick-and-dirty solution is as follows:

  1. Generate a random graph G with RanomGNP, i.e. G is undirected.
  2. Let D be the digraph version of G, i.e. if uv is an edge of D, then vu is also an edge.
  3. Let P be the edge removal probability.
  4. For each edge uv \in E(G), generate a cutoff probability p. If p \leq P, remove uv from the digraph D. Otherwise p > P, so we remove vu from D.

Here is sample code using Sage 4.4.1 illustrating the above procedure:

sage: G = graphs.RandomGNP(10, random())
sage: G.edges(labels=False)
[(0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (1, 7), (1, 8), (2, 4), (2, 6), (2, 8), (2, 9), (3, 4), (3, 6), (3, 7), (3, 8), (3, 9), (4, 5), (4, 9), (5, 6), (5, 8), (5, 9), (6, 9), (7, 8), (8, 9)]
sage: D = G.to_directed()
sage: D.edges(labels=False)
[(0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (1, 7), (1, 8), (2, 0), (2, 1), (2, 4), (2, 6), (2, 8), (2, 9), (3, 0), (3, 1), (3, 4), (3, 6), (3, 7), (3, 8), (3, 9), (4, 0), (4, 2), (4, 3), (4, 5), (4, 9), (5, 0), (5, 1), (5, 4), (5, 6), (5, 8), (5, 9), (6, 0), (6, 2), (6, 3), (6, 5), (6, 9), (7, 1), (7, 3), (7, 8), (8, 0), (8, 1), (8, 2), (8, 3), (8, 5), (8, 7), (8, 9), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 8)]
sage: D.size()
56
sage: P = random(); P
0.55638632541078259
sage: for u, v in G.edge_iterator(labels=False):
....:     p = random()
....:     if p <= P:
....:         D.delete_edge(u, v)
....:     else:
....:         D.delete_edge(v, u)
....: 
sage: D.edges(labels=False)
[(0, 2), (0, 3), (0, 6), (1, 2), (1, 5), (2, 8), (3, 1), (3, 6), (3, 8), (3, 9), (4, 0), (4, 2), (4, 3), (4, 5), (5, 0), (6, 2), (6, 5), (6, 9), (7, 1), (7, 3), (8, 0), (8, 1), (8, 5), (8, 7), (9, 2), (9, 4), (9, 5), (9, 8)]
sage: D.size()
28
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: