"""多图操作。"""
from itertools import chain, repeat
import networkx as nx
__all__ = ["union_all", "compose_all", "disjoint_union_all", "intersection_all"]
[docs]
@nx._dispatchable(graphs="[graphs]", preserve_all_attrs=True, returns_graph=True)
def union_all(graphs, rename=()):
"""返回所有图的并集。
这些图必须是互不相交的，否则会引发异常。
Parameters
----------
graphs : iterable
包含NetworkX图的可迭代对象
rename : iterable, 可选
可以通过指定元组（例如，rename=('G-','H-')）来更改图的节点名称。图G中的节点"u"将被重命名为"G-u"，图H中的节点"v"将被重命名为"H-v"。也支持无限生成器（如itertools.count）。
Returns
-------
U : 与列表中第一个图类型相同的图
Raises
------
ValueError
如果 `graphs` 是一个空列表。
NetworkXError
如果存在混合类型的图，如多重图和简单图，或是有向图和无向图。
Notes
-----
对于操作混合类型的图，应将它们转换为相同类型。
>>> G = nx.Graph()
>>> H = nx.DiGraph()
>>> GH = union_all([nx.DiGraph(G), H])
要强制进行节点重命名的不相交并集，请使用
disjoint_union_all(G,H) 或 convert_node_labels_to_integers()。
图、边和节点属性会被传播到并集图中。
如果某个图属性在多个图中存在，则使用列表中最后一个具有该属性的图的值。
Examples
--------
>>> G1 = nx.Graph([(1, 2), (2, 3)])
>>> G2 = nx.Graph([(4, 5), (5, 6)])
>>> result_graph = nx.union_all([G1, G2])
>>> result_graph.nodes()
NodeView((1, 2, 3, 4, 5, 6))
>>> result_graph.edges()
EdgeView([(1, 2), (2, 3), (4, 5), (5, 6)])
See Also
--------
union
disjoint_union_all
"""
R = None
seen_nodes = set()
# rename graph to obtain disjoint node labels
def add_prefix(graph, prefix):
if prefix is None:
return graph
def label(x):
return f"{prefix}{x}"
return nx.relabel_nodes(graph, label)
rename = chain(rename, repeat(None))
graphs = (add_prefix(G, name) for G, name in zip(graphs, rename))
for i, G in enumerate(graphs):
G_nodes_set = set(G.nodes)
if i == 0:
# Union is the same type as first graph
R = G.__class__()
elif G.is_directed() != R.is_directed():
raise nx.NetworkXError("All graphs must be directed or undirected.")
elif G.is_multigraph() != R.is_multigraph():
raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
elif not seen_nodes.isdisjoint(G_nodes_set):
raise nx.NetworkXError(
"The node sets of the graphs are not disjoint.\n"
"Use `rename` to specify prefixes for the graphs or use\n"
"disjoint_union(G1, G2, ..., GN)."
)
seen_nodes |= G_nodes_set
R.graph.update(G.graph)
R.add_nodes_from(G.nodes(data=True))
R.add_edges_from(
G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
)
if R is None:
raise ValueError("cannot apply union_all to an empty list")
return R
[docs]
@nx._dispatchable(graphs="[graphs]", preserve_all_attrs=True, returns_graph=True)
def disjoint_union_all(graphs):
"""返回所有图的不相交并集。
此操作强制从0开始为列表中的第一个图分配不同的整数节点标签，并连续编号。
Parameters
----------
graphs : 可迭代对象
包含NetworkX图的可迭代对象
Returns
-------
U : 与列表中第一个图类型相同的图
Raises
------
ValueError
如果 `graphs` 是空列表。
NetworkXError
如果存在混合类型的图，如多重图和简单图，或有向图和无向图。
Examples
--------
>>> G1 = nx.Graph([(1, 2), (2, 3)])
>>> G2 = nx.Graph([(4, 5), (5, 6)])
>>> U = nx.disjoint_union_all([G1, G2])
>>> list(U.nodes())
[0, 1, 2, 3, 4, 5]
>>> list(U.edges())
[(0, 1), (1, 2), (3, 4), (4, 5)]
Notes
-----
对于操作混合类型的图，应将它们转换为相同类型。
图、边和节点属性会传播到并集图。如果某个图属性在多个图中存在，则使用列表中最后一个具有该属性的图的值。
"""
def yield_relabeled(graphs):
first_label = 0
for G in graphs:
yield nx.convert_node_labels_to_integers(G, first_label=first_label)
first_label += len(G)
R = union_all(yield_relabeled(graphs))
return R
[docs]
@nx._dispatchable(graphs="[graphs]", preserve_all_attrs=True, returns_graph=True)
def compose_all(graphs):
"""返回所有图的组合。
组合是节点集和边集的简单并集。
提供的图的节点集不必不相交。
Parameters
----------
graphs : iterable
可迭代的NetworkX图
Returns
-------
C : 与列表中第一个图相同类型的图
Raises
------
ValueError
如果 `graphs` 是空列表。
NetworkXError
在混合类型图（如多图和图，或有向图和无向图）的情况下。
Examples
--------
>>> G1 = nx.Graph([(1, 2), (2, 3)])
>>> G2 = nx.Graph([(3, 4), (5, 6)])
>>> C = nx.compose_all([G1, G2])
>>> list(C.nodes())
[1, 2, 3, 4, 5, 6]
>>> list(C.edges())
[(1, 2), (2, 3), (3, 4), (5, 6)]
Notes
-----
对于操作混合类型图，应将它们转换为相同类型。
图、边和节点属性会传播到并集图。
如果某个图属性在多个图中存在，则使用列表中具有该属性的最后一个图的值。
"""
R = None
# add graph attributes, H attributes take precedent over G attributes
for i, G in enumerate(graphs):
if i == 0:
# create new graph
R = G.__class__()
elif G.is_directed() != R.is_directed():
raise nx.NetworkXError("All graphs must be directed or undirected.")
elif G.is_multigraph() != R.is_multigraph():
raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
R.graph.update(G.graph)
R.add_nodes_from(G.nodes(data=True))
R.add_edges_from(
G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
)
if R is None:
raise ValueError("cannot apply compose_all to an empty list")
return R
[docs]
@nx._dispatchable(graphs="[graphs]", returns_graph=True)
def intersection_all(graphs):
"""返回一个仅包含所有图中存在的节点和边的新图。
Parameters
----------
graphs : 可迭代对象
包含NetworkX图的可迭代对象
Returns
-------
R : 与列表中第一个图类型相同的新图
Raises
------
ValueError
如果 `graphs` 是一个空列表。
NetworkXError
如果图中包含混合类型，如MultiGraph和Graph，或是有向图和无向图。
Notes
-----
对于操作混合类型的图，应将它们转换为相同类型。
图、节点和边的属性不会复制到新图中。
如果需要，可以更新结果图的属性。例如，添加每个节点在所有图中的最小属性值的代码可以工作。
>>> g = nx.Graph()
>>> g.add_node(0, capacity=4)
>>> g.add_node(1, capacity=3)
>>> g.add_edge(0, 1)
>>> h = g.copy()
>>> h.nodes[0]["capacity"] = 2
>>> gh = nx.intersection_all([g, h])
>>> new_node_attr = {
... n: min(*(anyG.nodes[n].get("capacity", float("inf")) for anyG in [g, h]))
... for n in gh
... }
>>> nx.set_node_attributes(gh, new_node_attr, "new_capacity")
>>> gh.nodes(data=True)
NodeDataView({0: {'new_capacity': 2}, 1: {'new_capacity': 3}})
Examples
--------
>>> G1 = nx.Graph([(1, 2), (2, 3)])
>>> G2 = nx.Graph([(2, 3), (3, 4)])
>>> R = nx.intersection_all([G1, G2])
>>> list(R.nodes())
[2, 3]
>>> list(R.edges())
[(2, 3)]
"""
R = None
for i, G in enumerate(graphs):
G_nodes_set = set(G.nodes)
G_edges_set = set(G.edges)
if not G.is_directed():
if G.is_multigraph():
G_edges_set.update((v, u, k) for u, v, k in list(G_edges_set))
else:
G_edges_set.update((v, u) for u, v in list(G_edges_set))
if i == 0:
# create new graph
R = G.__class__()
node_intersection = G_nodes_set
edge_intersection = G_edges_set
elif G.is_directed() != R.is_directed():
raise nx.NetworkXError("All graphs must be directed or undirected.")
elif G.is_multigraph() != R.is_multigraph():
raise nx.NetworkXError("All graphs must be graphs or multigraphs.")
else:
node_intersection &= G_nodes_set
edge_intersection &= G_edges_set
if R is None:
raise ValueError("cannot apply intersection_all to an empty list")
R.add_nodes_from(node_intersection)
R.add_edges_from(edge_intersection)
return R
