"""
图操作包括并集、交集、差集。
"""
import networkx as nx
__all__ = [
"union",
"compose",
"disjoint_union",
"intersection",
"difference",
"symmetric_difference",
"full_join",
]
_G_H = {"G": 0, "H": 1}
[docs]
@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
def union(G, H, rename=()):
"""合并图 G 和 H。节点的名称必须是唯一的。
如果图之间存在名称冲突，将引发异常。
提供了一个重命名功能以避免名称冲突。
Parameters
----------
G, H : graph
一个 NetworkX 图
rename : iterable, 可选
可以通过指定元组 rename=('G-','H-')（例如）来更改 G 和 H 的节点名称。G 中的节点 "u" 将被重命名为 "G-u"，H 中的节点 "v" 将被重命名为 "H-v"。
Returns
-------
U : 一个与 G 类型相同的联合图。
See Also
--------
compose
:func:`~networkx.Graph.update`
disjoint_union
Notes
-----
要合并具有公共节点的图，请考虑使用 compose(G, H) 或方法 Graph.update()。
disjoint_union() 类似于 union()，但它通过将节点重命名为连续整数来避免名称冲突。
边和节点属性从 G 和 H 传播到联合图。图属性也会传播，但如果它们同时存在于 G 和 H 中，则使用 H 中的值。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
>>> H = nx.Graph([(0, 1), (0, 3), (1, 3), (1, 2)])
>>> U = nx.union(G, H, rename=("G", "H"))
>>> U.nodes
NodeView(('G0', 'G1', 'G2', 'H0', 'H1', 'H3', 'H2'))
>>> U.edges
EdgeView([('G0', 'G1'), ('G0', 'G2'), ('G1', 'G2'), ('H0', 'H1'), ('H0', 'H3'), ('H1', 'H3'), ('H1', 'H2')])
"""
return nx.union_all([G, H], rename)
[docs]
@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
def disjoint_union(G, H):
"""合并图 G 和 H。假设节点是唯一的（不相交的）。
该算法会自动重新标记节点以避免名称冲突。
Parameters
----------
G,H : 图
一个 NetworkX 图
Returns
-------
U : 一个与 G 类型相同的联合图。
See Also
--------
union
compose
:func:`~networkx.Graph.update`
Notes
-----
创建一个与 G 相同类别的新图。建议 G 和 H 要么都是有向的，要么都是无向的。
G 的节点被重新标记为 0 到 len(G)-1，H 的节点被重新标记为 len(G) 到 len(G)+len(H)-1。
重新编号强制 G 和 H 不相交，因此不会因名称冲突而引发异常。要保留对公共节点的检查，请使用 union()。
边和节点属性从 G 和 H 传播到联合图。图属性也会传播，但如果它们同时存在于 G 和 H 中，则使用 H 的值。
要合并具有公共节点的图，请考虑使用 compose(G, H) 或方法 Graph.update()。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
>>> H = nx.Graph([(0, 3), (1, 2), (2, 3)])
>>> G.nodes[0]["key1"] = 5
>>> H.nodes[0]["key2"] = 10
>>> U = nx.disjoint_union(G, H)
>>> U.nodes(data=True)
NodeDataView({0: {'key1': 5}, 1: {}, 2: {}, 3: {'key2': 10}, 4: {}, 5: {}, 6: {}})
>>> U.edges
EdgeView([(0, 1), (0, 2), (1, 2), (3, 4), (4, 6), (5, 6)])
"""
return nx.disjoint_union_all([G, H])
[docs]
@nx._dispatchable(graphs=_G_H, returns_graph=True)
def intersection(G, H):
"""返回一个仅包含在G和H中同时存在的节点和边的新图。
Parameters
----------
G,H : 图
一个NetworkX图。G和H可以有不同的节点集，但必须都是图或都是多重图。
Raises
------
NetworkXError
如果一个是多重图而另一个是图。
Returns
-------
GH : 一个与G类型相同的新图。
Notes
-----
图、节点和边的属性不会复制到新图中。如果你想得到一个包含G和H交集的新图，并且带有来自G的属性（包括边数据），可以使用remove_nodes_from()方法，如下所示：
>>> G = nx.path_graph(3)
>>> H = nx.path_graph(5)
>>> R = G.copy()
>>> R.remove_nodes_from(n for n in G if n not in H)
>>> R.remove_edges_from(e for e in G.edges if e not in H.edges)
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2)])
>>> H = nx.Graph([(0, 3), (1, 2), (2, 3)])
>>> R = nx.intersection(G, H)
>>> R.nodes
NodeView((0, 1, 2))
>>> R.edges
EdgeView([(1, 2)])
"""
return nx.intersection_all([G, H])
[docs]
@nx._dispatchable(graphs=_G_H, returns_graph=True)
def difference(G, H):
"""返回一个新图，该图包含在G中存在但不在H中的边。
H和G的节点集必须相同。
Parameters
----------
G,H : 图
一个NetworkX图。G和H必须具有相同的节点集。
Returns
-------
D : 一个与G类型相同的新图。
Notes
-----
图、节点和边的属性不会复制到新图中。如果你想要一个包含G和H差异的新图，并且包含G的属性（包括边数据），可以使用remove_nodes_from()方法，如下所示：
>>> G = nx.path_graph(3)
>>> H = nx.path_graph(5)
>>> R = G.copy()
>>> R.remove_nodes_from(n for n in G if n in H)
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)])
>>> H = nx.Graph([(0, 1), (1, 2), (0, 3)])
>>> R = nx.difference(G, H)
>>> R.nodes
NodeView((0, 1, 2, 3))
>>> R.edges
EdgeView([(0, 2), (1, 3)])
"""
# create new graph
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError("G and H must both be graphs or multigraphs.")
R = nx.create_empty_copy(G, with_data=False)
if set(G) != set(H):
raise nx.NetworkXError("Node sets of graphs not equal")
if G.is_multigraph():
edges = G.edges(keys=True)
else:
edges = G.edges()
for e in edges:
if not H.has_edge(*e):
R.add_edge(*e)
return R
[docs]
@nx._dispatchable(graphs=_G_H, returns_graph=True)
def symmetric_difference(G, H):
"""返回一个新图，包含在G或H中存在但不在两者中的边。
H和G的节点集必须相同。
Parameters
----------
G,H : 图
一个NetworkX图。G和H必须具有相同的节点集。
Returns
-------
D : 一个与G类型相同的新图。
Notes
-----
图、节点和边的属性不会复制到新图中。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3)])
>>> H = nx.Graph([(0, 1), (1, 2), (0, 3)])
>>> R = nx.symmetric_difference(G, H)
>>> R.nodes
NodeView((0, 1, 2, 3))
>>> R.edges
EdgeView([(0, 2), (0, 3), (1, 3)])
"""
# create new graph
if not G.is_multigraph() == H.is_multigraph():
raise nx.NetworkXError("G and H must both be graphs or multigraphs.")
R = nx.create_empty_copy(G, with_data=False)
if set(G) != set(H):
raise nx.NetworkXError("Node sets of graphs not equal")
gnodes = set(G) # set of nodes in G
hnodes = set(H) # set of nodes in H
nodes = gnodes.symmetric_difference(hnodes)
R.add_nodes_from(nodes)
if G.is_multigraph():
edges = G.edges(keys=True)
else:
edges = G.edges()
# we could copy the data here but then this function doesn't
# match intersection and difference
for e in edges:
if not H.has_edge(*e):
R.add_edge(*e)
if H.is_multigraph():
edges = H.edges(keys=True)
else:
edges = H.edges()
for e in edges:
if not G.has_edge(*e):
R.add_edge(*e)
return R
[docs]
@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
def compose(G, H):
"""将图G和H组合成一个单一的图，合并节点和边。
节点集和边集不需要是互斥的。
组合操作保留节点和边的属性。H中的属性值优先于G中的属性值。
Parameters
----------
G, H : 图
一个NetworkX图
Returns
-------
C: 一个与G类型相同的新图
See Also
--------
:func:`~networkx.Graph.update`
union
disjoint_union
Notes
-----
建议G和H要么都是有向图，要么都是无向图。
对于MultiGraphs，边由相邻节点和边键标识。这可能导致意外情况（例如，边 `(1, 2)` 在两个图中可能相同也可能不同），如果你使用MultiGraph而不跟踪边键。
如果不希望合并公共节点的属性，可以考虑使用union()，它在名称冲突时会引发异常。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2)])
>>> H = nx.Graph([(0, 1), (1, 2)])
>>> R = nx.compose(G, H)
>>> R.nodes
NodeView((0, 1, 2))
>>> R.edges
EdgeView([(0, 1), (0, 2), (1, 2)])
默认情况下， `H` 的属性优先于 `G` 的属性。如果你希望以其他方式合并属性，可以在组合操作后更新它们：
>>> G = nx.Graph([(0, 1, {"weight": 2.0}), (3, 0, {"weight": 100.0})])
>>> H = nx.Graph([(0, 1, {"weight": 10.0}), (1, 2, {"weight": -1.0})])
>>> nx.set_node_attributes(G, {0: "dark", 1: "light", 3: "black"}, name="color")
>>> nx.set_node_attributes(H, {0: "green", 1: "orange", 2: "yellow"}, name="color")
>>> GcomposeH = nx.compose(G, H)
通常，GcomposeH节点的颜色属性值来自H。我们可以通过以下方式解决这个问题：
>>> node_data = {
... n: G.nodes[n]["color"] + " " + H.nodes[n]["color"]
... for n in G.nodes & H.nodes
... }
>>> nx.set_node_attributes(GcomposeH, node_data, "color")
>>> print(GcomposeH.nodes[0]["color"])
dark green
>>> print(GcomposeH.nodes[3]["color"])
black
类似地，我们可以在组合操作后以我们喜欢的方式更新边属性：
>>> edge_data = {
... e: G.edges[e]["weight"] * H.edges[e]["weight"] for e in G.edges & H.edges
... }
>>> nx.set_edge_attributes(GcomposeH, edge_data, "weight")
>>> print(GcomposeH.edges[(0, 1)]["weight"])
20.0
>>> print(GcomposeH.edges[(3, 0)]["weight"])
100.0
"""
return nx.compose_all([G, H])
[docs]
@nx._dispatchable(graphs=_G_H, preserve_all_attrs=True, returns_graph=True)
def full_join(G, H, rename=(None, None)):
"""返回图 G 和 H 的全连接。
全连接是 G 和 H 的并集，其中所有 G 和 H 之间的边都被添加。
G 和 H 的节点集必须不相交，否则会引发异常。
Parameters
----------
G, H : 图
一个 NetworkX 图
rename : 元组, 默认=(None, None)
可以通过指定元组 rename=('G-','H-') 来更改 G 和 H 的节点名称（例如）。G 中的节点 "u" 将被重命名为 "G-u"，H 中的节点 "v" 将被重命名为 "H-v"。
Returns
-------
U : 与 G 类型相同的全连接图。
Notes
-----
建议 G 和 H 要么都是有向的，要么都是无向的。
如果 G 是有向的，那么会添加从 G 到 H 以及从 H 到 G 的边。
注意，full_join() 不会为 MultiGraphs 生成平行边。
图 G 和 H 的全连接操作与获取它们的补图、执行不相交并集，最后获取结果图的补图相同。
图、边和节点属性从 G 和 H 传播到并集图。如果 G 和 H 中都存在某个图属性，则使用 H 中的值。
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2)])
>>> H = nx.Graph([(3, 4)])
>>> R = nx.full_join(G, H, rename=("G", "H"))
>>> R.nodes
NodeView(('G0', 'G1', 'G2', 'H3', 'H4'))
>>> R.edges
EdgeView([('G0', 'G1'), ('G0', 'G2'), ('G0', 'H3'), ('G0', 'H4'), ('G1', 'H3'), ('G1', 'H4'), ('G2', 'H3'), ('G2', 'H4'), ('H3', 'H4')])
See Also
--------
union
disjoint_union
"""
R = union(G, H, rename)
def add_prefix(graph, prefix):
if prefix is None:
return graph
def label(x):
return f"{prefix}{x}"
return nx.relabel_nodes(graph, label)
G = add_prefix(G, rename[0])
H = add_prefix(H, rename[1])
for i in G:
for j in H:
R.add_edge(i, j)
if R.is_directed():
for i in H:
for j in G:
R.add_edge(i, j)
return R
