# Revision history [back]

I don't think anything like this exists in Sage now, but the code for random_subgraph is pretty simple:

def random_subgraph(self, p, inplace=False):
"""
Return a random subgraph containing each vertex with probability p.

INPUT:

- p -- the probability of choosing a vertex

- inplace -- boolean (default: False); using inplace=True
will simply delete the extra vertices and edges from the current
graph. This will modify the graph.

EXAMPLES::

sage: P = graphs.PetersenGraph()
sage: P.random_subgraph(.25)
Subgraph of (Petersen graph): Graph on ... vert...
"""
p = float(p)
if p < 0 or p > 1:
raise ValueError("a probability must be in range [0..1]")
vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)


The heart of it is:

    vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)


Something that doesn't quite work:

sage: g = graphs.PetersenGraph()
sage: p = 0.3
sage: V = [v for v in g  if random()<p]
sage: E =
sage: h = g.subgraph(vertices=V, edges=E)


The problem is that the definition of E ignores which vertices are in V. You could instead construct your subgraph in stages:

sage: h1 = g.random_subgraph(p)
sage: E = [e for e in h1.edge_iterator() if random()<p] # choose edges randomly from h1
sage: h2 = h1.subgraph(edges=E)


Now h2 will have the randomly chosen vertices that make up h1, and it will have edges chosen from h1 randomly.

I don't think anything like this exists in Sage now, but the code for random_subgraph is pretty simple:

def random_subgraph(self, p, inplace=False):
"""
Return a random subgraph containing each vertex with probability p.

INPUT:

- p -- the probability of choosing a vertex

- inplace -- boolean (default: False); using inplace=True
will simply delete the extra vertices and edges from the current
graph. This will modify the graph.

EXAMPLES::

sage: P = graphs.PetersenGraph()
sage: P.random_subgraph(.25)
Subgraph of (Petersen graph): Graph on ... vert...
"""
p = float(p)
if p < 0 or p > 1:
raise ValueError("a probability must be in range [0..1]")
vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)


The heart of it is:

    vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)


Something that doesn't quite work:

sage: g = graphs.PetersenGraph()
sage: p = 0.3
sage: V = [v for v in g  if random()<p]
sage: E =  [e for e in g.edge_iterator() if random()<p]
sage: h = g.subgraph(vertices=V, edges=E)


The problem is that the definition of E ignores which vertices are in V. You could instead construct your subgraph in stages:

sage: h1 = g.random_subgraph(p)
sage: E = [e for e in h1.edge_iterator() if random()<p] # choose edges randomly from h1
sage: h2 = h1.subgraph(edges=E)


Now h2 will have the randomly chosen vertices that make up h1, and it will have edges chosen from h1 randomly.