"""
二分图的生成器和函数。
"""
import math
import numbers
from functools import reduce
import networkx as nx
from networkx.utils import nodes_or_number, py_random_state
__all__ = [
"configuration_model",
"havel_hakimi_graph",
"reverse_havel_hakimi_graph",
"alternating_havel_hakimi_graph",
"preferential_attachment_graph",
"random_graph",
"gnmk_random_graph",
"complete_bipartite_graph",
]
[docs]
@nx._dispatchable(graphs=None, returns_graph=True)
@nodes_or_number([0, 1])
def complete_bipartite_graph(n1, n2, create_using=None):
"""返回完整的二分图 `K_{n_1,n_2}` 。
该图由两个分区组成，第一个分区包含节点 0 到 (n1 - 1)，第二个分区包含节点 n1 到 (n1 + n2 - 1)。
第一个分区中的每个节点都与第二个分区中的每个节点相连。
Parameters
----------
n1, n2 : 整数或节点可迭代容器
如果是整数，节点来自 `range(n1)` 和 `range(n1, n1 + n2)` 。
如果是容器，元素即为节点。
create_using : NetworkX 图实例, (默认: nx.Graph)
返回此类型的图。
Notes
-----
除非 n1 或 n2 是节点容器，否则节点是整数 0 到 `n1 + n2 - 1` 。如果只有 n1 或 n2 是整数，该整数被替换为该整数的 `range` 。
节点被赋予属性 'bipartite'，值为 0 或 1，以指示节点属于哪个二分集。
此函数未导入主命名空间。要使用它，请使用 nx.bipartite.complete_bipartite_graph。
"""
G = nx.empty_graph(0, create_using)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")
n1, top = n1
n2, bottom = n2
if isinstance(n1, numbers.Integral) and isinstance(n2, numbers.Integral):
bottom = [n1 + i for i in bottom]
G.add_nodes_from(top, bipartite=0)
G.add_nodes_from(bottom, bipartite=1)
if len(G) != len(top) + len(bottom):
raise nx.NetworkXError("Inputs n1 and n2 must contain distinct nodes")
G.add_edges_from((u, v) for u in top for v in bottom)
G.graph["name"] = f"complete_bipartite_graph({len(top)}, {len(bottom)})"
return G
[docs]
@py_random_state(3)
@nx._dispatchable(name="bipartite_configuration_model", graphs=None, returns_graph=True)
def configuration_model(aseq, bseq, create_using=None, seed=None):
"""返回一个从给定度序列生成的随机二分图。
Parameters
----------
aseq : list
节点集A的度序列。
bseq : list
节点集B的度序列。
create_using : NetworkX图实例，可选
返回此类型的图。
seed : 整数，random_state，或None（默认）
随机数生成状态的指示器。
参见 :ref:`随机性<randomness>` 。
该图由两个分区组成。集合A包含节点0到(len(aseq) - 1)，集合B包含节点len(aseq)到(len(bseq) - 1)。集合A中的节点通过从可能的自由末端中随机选择一个A中的和一个B中的节点来连接到集合B中的节点。
Notes
-----
两个序列的和必须相等：sum(aseq)=sum(bseq)
如果没有指定图类型，则使用带有平行边的MultiGraph。
如果需要一个没有平行边的图，使用create_using=Graph()，但生成的度序列可能不准确。
节点被赋予属性'bipartite'，其值为0或1，以指示节点属于哪个二分集。
此函数未导入主命名空间。要使用它，请使用nx.bipartite.configuration_model
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")
# length and sum of each sequence
lena = len(aseq)
lenb = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)
if not suma == sumb:
raise nx.NetworkXError(
f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
)
G = _add_nodes_with_bipartite_label(G, lena, lenb)
if len(aseq) == 0 or max(aseq) == 0:
return G # done if no edges
# build lists of degree-repeated vertex numbers
stubs = [[v] * aseq[v] for v in range(lena)]
astubs = [x for subseq in stubs for x in subseq]
stubs = [[v] * bseq[v - lena] for v in range(lena, lena + lenb)]
bstubs = [x for subseq in stubs for x in subseq]
# shuffle lists
seed.shuffle(astubs)
seed.shuffle(bstubs)
G.add_edges_from([astubs[i], bstubs[i]] for i in range(suma))
G.name = "bipartite_configuration_model"
return G
[docs]
@nx._dispatchable(name="bipartite_havel_hakimi_graph", graphs=None, returns_graph=True)
def havel_hakimi_graph(aseq, bseq, create_using=None):
"""返回一个由给定的两个度序列使用Havel-Hakimi风格构造的二分图。
该图由两个分区组成。集合A包含节点0到(len(aseq) - 1)，集合B包含节点len(aseq)到(len(bseq) - 1)。集合A中的节点与集合B中的节点相连，方法是连接集合A中最高度数的节点与集合B中最高度数的节点，直到所有末端都连接。
Parameters
----------
aseq : list
节点集合A的度序列。
bseq : list
节点集合B的度序列。
create_using : NetworkX图实例, 可选
返回此类型的图。
Notes
-----
两个序列的总和必须相等：sum(aseq)=sum(bseq)
如果没有指定图类型，则使用带有平行边的MultiGraph。
如果你想得到一个没有平行边的图，使用create_using=Graph()，但这样生成的度序列可能不完全准确。
节点被赋予属性'bipartite'，其值为0或1，以指示节点属于哪个二分集。
此函数未导入主命名空间。要使用它，请使用nx.bipartite.havel_hakimi_graph。
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")
# length of the each sequence
naseq = len(aseq)
nbseq = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)
if not suma == sumb:
raise nx.NetworkXError(
f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
)
G = _add_nodes_with_bipartite_label(G, naseq, nbseq)
if len(aseq) == 0 or max(aseq) == 0:
return G # done if no edges
# build list of degree-repeated vertex numbers
astubs = [[aseq[v], v] for v in range(naseq)]
bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)]
astubs.sort()
while astubs:
(degree, u) = astubs.pop() # take of largest degree node in the a set
if degree == 0:
break # done, all are zero
# connect the source to largest degree nodes in the b set
bstubs.sort()
for target in bstubs[-degree:]:
v = target[1]
G.add_edge(u, v)
target[0] -= 1 # note this updates bstubs too.
if target[0] == 0:
bstubs.remove(target)
G.name = "bipartite_havel_hakimi_graph"
return G
[docs]
@nx._dispatchable(graphs=None, returns_graph=True)
def reverse_havel_hakimi_graph(aseq, bseq, create_using=None):
"""返回一个由给定的两个度序列使用Havel-Hakimi风格的构造方法生成的二分图。
该图由两个分区组成。集合A包含节点0到(len(aseq) - 1)，集合B包含节点len(aseq)到(len(bseq) - 1)。集合A中的节点通过将集合A中度数最高的节点与集合B中度数最低的节点连接，直到所有端点都被连接，从而与集合B中的节点相连。
Parameters
----------
aseq : 列表
节点集合A的度序列。
bseq : 列表
节点集合B的度序列。
create_using : NetworkX图实例，可选
返回此类型的图。
Notes
-----
两个序列的总和必须相等：sum(aseq)=sum(bseq)
如果没有指定图类型，则使用带有平行边的MultiGraph。
如果希望图没有平行边，请使用create_using=Graph()，但生成的度序列可能不完全准确。
节点被赋予属性'bipartite'，其值为0或1，以指示节点属于哪个二分集。
此函数未导入主命名空间。要使用它，请使用nx.bipartite.reverse_havel_hakimi_graph。
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")
# length of the each sequence
lena = len(aseq)
lenb = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)
if not suma == sumb:
raise nx.NetworkXError(
f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
)
G = _add_nodes_with_bipartite_label(G, lena, lenb)
if len(aseq) == 0 or max(aseq) == 0:
return G # done if no edges
# build list of degree-repeated vertex numbers
astubs = [[aseq[v], v] for v in range(lena)]
bstubs = [[bseq[v - lena], v] for v in range(lena, lena + lenb)]
astubs.sort()
bstubs.sort()
while astubs:
(degree, u) = astubs.pop() # take of largest degree node in the a set
if degree == 0:
break # done, all are zero
# connect the source to the smallest degree nodes in the b set
for target in bstubs[0:degree]:
v = target[1]
G.add_edge(u, v)
target[0] -= 1 # note this updates bstubs too.
if target[0] == 0:
bstubs.remove(target)
G.name = "bipartite_reverse_havel_hakimi_graph"
return G
[docs]
@nx._dispatchable(graphs=None, returns_graph=True)
def alternating_havel_hakimi_graph(aseq, bseq, create_using=None):
"""返回一个由给定的两个度序列使用交替Havel-Hakimi风格构造的二分图。
该图由两个分区组成。集合A包含节点0到(len(aseq) - 1)，集合B包含节点len(aseq)到(len(bseq) - 1)。集合A中的节点通过将集合A中最高度数的节点与集合B中交替的最高和最低度数的节点连接，直到所有端点都被连接。
Parameters
----------
aseq : list
节点集合A的度序列。
bseq : list
节点集合B的度序列。
create_using : NetworkX图实例, 可选
返回此类型的图。
Notes
-----
两个序列的总和必须相等：sum(aseq)=sum(bseq)
如果没有指定图类型，则使用带有平行边的MultiGraph。
如果希望图没有平行边，使用create_using=Graph()，但生成的度序列可能不完全准确。
节点被赋予属性'bipartite'，值为0或1，以指示节点属于哪个二分集。
此函数未导入主命名空间。
要使用它，请使用nx.bipartite.alternating_havel_hakimi_graph
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")
# length of the each sequence
naseq = len(aseq)
nbseq = len(bseq)
suma = sum(aseq)
sumb = sum(bseq)
if not suma == sumb:
raise nx.NetworkXError(
f"invalid degree sequences, sum(aseq)!=sum(bseq),{suma},{sumb}"
)
G = _add_nodes_with_bipartite_label(G, naseq, nbseq)
if len(aseq) == 0 or max(aseq) == 0:
return G # done if no edges
# build list of degree-repeated vertex numbers
astubs = [[aseq[v], v] for v in range(naseq)]
bstubs = [[bseq[v - naseq], v] for v in range(naseq, naseq + nbseq)]
while astubs:
astubs.sort()
(degree, u) = astubs.pop() # take of largest degree node in the a set
if degree == 0:
break # done, all are zero
bstubs.sort()
small = bstubs[0 : degree // 2] # add these low degree targets
large = bstubs[(-degree + degree // 2) :] # now high degree targets
stubs = [x for z in zip(large, small) for x in z] # combine, sorry
if len(stubs) < len(small) + len(large): # check for zip truncation
stubs.append(large.pop())
for target in stubs:
v = target[1]
G.add_edge(u, v)
target[0] -= 1 # note this updates bstubs too.
if target[0] == 0:
bstubs.remove(target)
G.name = "bipartite_alternating_havel_hakimi_graph"
return G
[docs]
@py_random_state(3)
@nx._dispatchable(graphs=None, returns_graph=True)
def preferential_attachment_graph(aseq, p, create_using=None, seed=None):
"""创建一个二分图，使用给定单一度序列的优先连接模型。
该图由两个分区组成。集合A包含节点0到（len(aseq) - 1），集合B包含从节点len(aseq)开始的节点。集合B中的节点数量是随机的。
Parameters
----------
aseq : 列表
节点集合A的度序列。
p : 浮点数
添加新底部节点的概率。
create_using : NetworkX图实例，可选
返回此类型的图。
seed : 整数，random_state，或None（默认）
随机数生成状态的指示器。
参见 :ref:`Randomness<randomness>` 。
References
----------
.. [1] Guillaume, J.L. 和 Latapy, M.,
二分图作为复杂网络的模型。
物理A：统计力学及其应用，
2006, 371(2), pp.795-813.
.. [2] Jean-Loup Guillaume 和 Matthieu Latapy,
所有复杂网络的二分结构，
信息处理快报 90, 2004, pg. 215-221
https://doi.org/10.1016/j.ipl.2004.03.007
Notes
-----
节点被赋予属性'bipartite'，其值为0或1，以指示节点属于哪个二分集。
此函数未导入主命名空间。
要使用它，请使用 nx.bipartite.preferential_attachment_graph
"""
G = nx.empty_graph(0, create_using, default=nx.MultiGraph)
if G.is_directed():
raise nx.NetworkXError("Directed Graph not supported")
if p > 1:
raise nx.NetworkXError(f"probability {p} > 1")
naseq = len(aseq)
G = _add_nodes_with_bipartite_label(G, naseq, 0)
vv = [[v] * aseq[v] for v in range(naseq)]
while vv:
while vv[0]:
source = vv[0][0]
vv[0].remove(source)
if seed.random() < p or len(G) == naseq:
target = len(G)
G.add_node(target, bipartite=1)
G.add_edge(source, target)
else:
bb = [[b] * G.degree(b) for b in range(naseq, len(G))]
# flatten the list of lists into a list.
bbstubs = reduce(lambda x, y: x + y, bb)
# choose preferentially a bottom node.
target = seed.choice(bbstubs)
G.add_node(target, bipartite=1)
G.add_edge(source, target)
vv.remove(vv[0])
G.name = "bipartite_preferential_attachment_model"
return G
[docs]
@py_random_state(3)
@nx._dispatchable(graphs=None, returns_graph=True)
def random_graph(n, m, p, seed=None, directed=False):
"""返回一个二分随机图。
这是二项式（Erdős-Rényi）图的二分版本。
该图由两个分区组成。集合A包含节点0到（n - 1），集合B包含节点n到（n + m - 1）。
Parameters
----------
n : int
第一个二分集合中的节点数。
m : int
第二个二分集合中的节点数。
p : float
创建边的概率。
seed : integer, random_state, 或 None（默认）
随机数生成状态的指示器。
参见 :ref:`Randomness<randomness>` 。
directed : bool, 可选（默认=False）
如果为True，返回一个有向图。
Notes
-----
二分随机图算法以概率p选择每个n*m（无向）或2*nm（有向）可能的边。
该算法的时间复杂度为$O(n+m)$，其中$m$是预期的边数。
节点被赋予属性'bipartite'，其值为0或1，以指示节点属于哪个二分集合。
此函数未导入主命名空间。
要使用它，请使用nx.bipartite.random_graph。
See Also
--------
gnp_random_graph, configuration_model
References
----------
.. [1] Vladimir Batagelj 和 Ulrik Brandes,
"高效生成大型随机网络",
Phys. Rev. E, 71, 036113, 2005.
"""
G = nx.Graph()
G = _add_nodes_with_bipartite_label(G, n, m)
if directed:
G = nx.DiGraph(G)
G.name = f"fast_gnp_random_graph({n},{m},{p})"
if p <= 0:
return G
if p >= 1:
return nx.complete_bipartite_graph(n, m)
lp = math.log(1.0 - p)
v = 0
w = -1
while v < n:
lr = math.log(1.0 - seed.random())
w = w + 1 + int(lr / lp)
while w >= m and v < n:
w = w - m
v = v + 1
if v < n:
G.add_edge(v, n + w)
if directed:
# use the same algorithm to
# add edges from the "m" to "n" set
v = 0
w = -1
while v < n:
lr = math.log(1.0 - seed.random())
w = w + 1 + int(lr / lp)
while w >= m and v < n:
w = w - m
v = v + 1
if v < n:
G.add_edge(n + w, v)
return G
[docs]
@py_random_state(3)
@nx._dispatchable(graphs=None, returns_graph=True)
def gnmk_random_graph(n, m, k, seed=None, directed=False):
"""返回一个随机二分图 G_{n,m,k}。
从所有具有 n 个顶部节点、m 个底部节点和 k 条边的图中随机选择一个二分图。
该图由两组节点组成。
集合 A 包含节点 0 到 (n - 1)，集合 B 包含节点 n 到 (n + m - 1)。
Parameters
----------
n : int
第一个二分集中的节点数。
m : int
第二个二分集中的节点数。
k : int
边的数量
seed : integer, random_state, 或 None (默认)
随机数生成状态的指示器。
参见 :ref:`Randomness<randomness>` 。
directed : bool, 可选 (默认=False)
如果为 True，返回一个有向图
Examples
--------
from nx.algorithms import bipartite
G = bipartite.gnmk_random_graph(10,20,50)
See Also
--------
gnm_random_graph
Notes
-----
如果 k > m * n，则返回一个完全二分图。
此图是 `G_{nm}` 随机图模型的二分版本。
节点被赋予属性 'bipartite'，其值为 0 或 1，以指示节点属于哪个二分集。
此函数未导入到主命名空间中。
要使用它，请使用 nx.bipartite.gnmk_random_graph
"""
G = nx.Graph()
G = _add_nodes_with_bipartite_label(G, n, m)
if directed:
G = nx.DiGraph(G)
G.name = f"bipartite_gnm_random_graph({n},{m},{k})"
if n == 1 or m == 1:
return G
max_edges = n * m # max_edges for bipartite networks
if k >= max_edges: # Maybe we should raise an exception here
return nx.complete_bipartite_graph(n, m, create_using=G)
top = [n for n, d in G.nodes(data=True) if d["bipartite"] == 0]
bottom = list(set(G) - set(top))
edge_count = 0
while edge_count < k:
# generate random edge,u,v
u = seed.choice(top)
v = seed.choice(bottom)
if v in G[u]:
continue
else:
G.add_edge(u, v)
edge_count += 1
return G
def _add_nodes_with_bipartite_label(G, lena, lenb):
G.add_nodes_from(range(lena + lenb))
b = dict(zip(range(lena), [0] * lena))
b.update(dict(zip(range(lena, lena + lenb), [1] * lenb)))
nx.set_node_attributes(G, b, "bipartite")
return G
