1 | initial version |
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.
2 | No.2 Revision |
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.