由 dawei
【笔记】
用__all__定义全局变量，即所有可以生成的图
itertools.permutations(range(n),2)：返回n个数中任意取2个元素做排列的元组的迭代器
itertools.combinations(range(n),2)：返回n个数中任意取2个元素做组合的元组的迭代器
itertools.chain(arr1,arr2)：将两个数组arr1和arr2链接在一起，返回迭代器，迭代器可被list()与set()转化
=============================================
下面是python-networkx中，生成图的文件random_graphs的源码（加注释）：
# Dan Schult
# Pieter Swart
# All rights reserved.
# BSD license.
"""
Generators for random graphs.
"""
from future import division
import itertools
import math
import random
import networkx as nx
from .classic import empty_graph,path_graph,complete_graph
from .degree_seq import degree_sequence_tree
from collections import defaultdict
all = ['fast_gnp_random_graph','gnp_random_graph','dense_gnm_random_graph','gnm_random_graph','erdos_renyi_graph','binomial_graph','newman_watts_strogatz_graph','watts_strogatz_graph','connected_watts_strogatz_graph','random_regular_graph','barabasi_albert_graph','extended_barabasi_albert_graph','powerlaw_cluster_graph','random_lobster','random_shell_graph','random_powerlaw_tree','random_powerlaw_tree_sequence','random_kernel_graph']
-------------------------------------------------------------------------
Some Famous Random Graphs
-------------------------------------------------------------------------
def fast_gnp_randomgraph(n,p,seed=None,directed=False):
"""Returns a $G{n,p}$ random graph,also known as an Erds-Rényi graph or
a binomial graph.
Parameters
----------
n : int
The number of nodes.
p : float
Probability for edge creation.
seed : int,optional
Seed for random number generator (default=None).
directed : bool,optional (default=False)
If True,this function returns a directed graph.
Notes
-----
The $G_{n,p}$ graph algorithm chooses each of the $[n (n - 1)] / 2$
(undirected) or $n (n - 1)$ (directed) possible edges with probability $p$.
This algorithm [1]_ runs in $O(n + m)$ time,where `m` is the expected number of
edges,which equals $p n (n - 1) / 2$. This should be faster than
:func:`gnp_random_graph` when $p$ is small and the expected number of edges
is small (that is,the graph is sparse).
See Also
--------
gnp_random_graph
References
----------
.. [1] Vladimir Batagelj and Ulrik Brandes,"Efficient generation of large random networks",Phys. Rev. E,71,036113,2005.
"""
G = empty_graph(n)
if seed is not None:
random.seed(seed)
if p <= 0 or p >= 1:
return nx.gnp_random_graph(n,directed=directed)
w = -1
lp = math.log(1.0 - p)
if directed:
G = nx.DiGraph(G)
# Nodes in graph are from 0,n-1 (start with v as the first node index).
v = 0
while v < n:
lr = math.log(1.0 - random.random())
w = w + 1 + int(lr / lp)
if v == w: # avoid self loops
w = w + 1
while v < n <= w:
w = w - n
v = v + 1
if v == w: # avoid self loops
w = w + 1
if v < n:
G.add_edge(v,w)
else:
# Nodes in graph are from 0,n-1 (start with v as the second node index).
v = 1
while v < n:
lr = math.log(1.0 - random.random())
w = w + 1 + int(lr / lp)
while w >= v and v < n:
w = w - v
v = v + 1
if v < n:
G.add_edge(v,w)
return G
def gnp_random_graph(n,also known as an Erds-Rényi graph
or a binomial graph.
The $G_{n,p}$ model chooses each of the possible edges with probability $p$.
The functions :func:`binomial_graph` and :func:`erdos_renyi_graph` are
aliases of this function.
Parameters
----------
n : int
The number of nodes.
p : float
Probability for edge creation.
seed : int,this function returns a directed graph.
See Also
--------
fast_gnp_random_graph
Notes
-----
This algorithm [2]_ runs in $O(n^2)$ time. For sparse graphs (that is,for
small values of $p$),:func:`fast_gnp_random_graph` is a faster algorithm.
References
----------
.. [1] P. Erds and A. Rényi,On Random Graphs,Publ. Math. 6,290 (1959).
.. [2] E. N. Gilbert,Random Graphs,Ann. Math. Stat.,30,1141 (1959).
"""
if directed:
G = nx.DiGraph()
else:
G = nx.Graph()
G.add_nodes_from(range(n))
if p <= 0:
return G
if p >= 1:
return complete_graph(n,create_using=G)
if seed is not None:
random.seed(seed)
if G.is_directed():
edges = itertools.permutations(range(n),2)
else:
edges = itertools.combinations(range(n),2)
for e in edges:
if random.random() < p:
G.add_edge(*e)
return G
add some aliases to common names
binomial_graph = gnp_random_graph
erdos_renyi_graph = gnp_random_graph
def dense_gnm_randomgraph(n,m,seed=None):
"""Returns a $G{n,m}$ random graph.
In the $G_{n,m}$ model,a graph is chosen uniformly at random from the set
of all graphs with $n$ nodes and $m$ edges.
This algorithm should be faster than :func:`gnm_random_graph` for dense
graphs.
Parameters
----------
n : int
The number of nodes.
m : int
The number of edges.
seed : int,optional
Seed for random number generator (default=None).
See Also
--------
gnm_random_graph()
Notes
-----
Algorithm by Keith M. Briggs Mar 31,2006.
Inspired by Knuth's Algorithm S (Selection sampling technique),in section 3.4.2 of [1]_.
References
----------
.. [1] Donald E. Knuth,The Art of Computer Programming,Volume 2/Seminumerical algorithms,Third Edition,Addison-Wesley,1997.
"""
mmax = n * (n - 1) / 2
if m >= mmax:
G = complete_graph(n)
else:
G = empty_graph(n)
if n == 1 or m >= mmax:
return G
if seed is not None:
random.seed(seed)
u = 0
v = 1
t = 0
k = 0
while True:
if random.randrange(mmax - t) < m - k:
G.add_edge(u,v)
k += 1
if k == m:
return G
t += 1
v += 1
if v == n: # go to next row of adjacency matrix
u += 1
v = u + 1
def gnm_random_graph(n,a graph is chosen uniformly at random from the set
of all graphs with $n$ nodes and $m$ edges.
This algorithm should be faster than :func:`dense_gnm_random_graph` for
sparse graphs.
Parameters
----------
n : int
The number of nodes.
m : int
The number of edges.
seed : int,optional (default=False)
If True return a directed graph
See also
--------
dense_gnm_random_graph
"""
if directed:
G = nx.DiGraph()
else:
G = nx.Graph()
G.add_nodes_from(range(n))
if seed is not None:
random.seed(seed)
if n == 1:
return G
max_edges = n * (n - 1)
if not directed:
max_edges /= 2.0
if m >= max_edges:
return complete_graph(n,create_using=G)
nlist = list(G)
edge_count = 0
while edge_count < m:
# generate random edge,u,v
u = random.choice(nlist)
v = random.choice(nlist)
if u == v or G.has_edge(u,v):
continue
else:
G.add_edge(u,v)
edge_count = edge_count + 1
return G
def newman_watts_strogatz_graph(n,k,seed=None):
"""Return a Newman–Watts–Strogatz small-world graph.
Parameters
----------
n : int
The number of nodes.
k : int
Each node is joined with its `k` nearest neighbors in a ring
topology.
p : float
The probability of adding a new edge for each edge.
seed : int,optional
The seed for the random number generator (the default is None).
Notes
-----
First create a ring over $n$ nodes [1]_. Then each node in the ring is
connected with its $k$ nearest neighbors (or $k - 1$ neighbors if $k$
is odd). Then shortcuts are created by adding new edges as follows: for
each edge $(u,v)$ in the underlying "$n$-ring with $k$ nearest
neighbors" with probability $p$ add a new edge $(u,w)$ with
randomly-chosen existing node $w$. In contrast with
:func:`watts_strogatz_graph`,no edges are removed.
See Also
--------
watts_strogatz_graph()
References
----------
.. [1] M. E. J. Newman and D. J. Watts,Renormalization group analysis of the small-world network model,Physics Letters A,263,341,1999.
http://dx.doi.org/10.1016/S0375-9601(99)00757-4
"""
if seed is not None:
random.seed(seed)
if k >= n:
raise nx.NetworkXError("k>=n,choose smaller k or larger n")
G = empty_graph(n)
nlist = list(G.nodes())
fromv = nlist
# connect the k/2 neighbors
for j in range(1,k // 2 + 1):
tov = fromv[j:] + fromv[0:j] # the first j are now last
for i in range(len(fromv)):
G.add_edge(fromv[i],tov[i])
# for each edge u-v,with probability p,randomly select existing
# node w and add new edge u-w
e = list(G.edges())
for (u,v) in e:
if random.random() < p:
w = random.choice(nlist)
# no self-loops and reject if edge u-w exists
# is that the correct NWS model?
while w == u or G.has_edge(u,w):
w = random.choice(nlist)
if G.degree(u) >= n - 1:
break # skip this rewiring
else:
G.add_edge(u,w)
return G