"""用于查找一组节点的边界的例程。
边边界是一组边，其中每条边恰好有一个端点在给定的一组节点中（或者在有向图的情况下，是指源节点在集合中的边）。
一组节点 *S* 的节点边界是 *S* 中节点的（出）邻居中不在 *S* 内的节点集合。
"""
from itertools import chain
import networkx as nx
__all__ = ["edge_boundary", "node_boundary"]
[docs]
@nx._dispatchable(edge_attrs={"data": "default"}, preserve_edge_attrs="data")
def edge_boundary(G, nbunch1, nbunch2=None, data=False, keys=False, default=None):
"""返回 `nbunch1` 的边缘边界。
集合 *S* 相对于集合 *T* 的*边缘边界*是所有边 (*u*, *v*) 的集合，其中 *u* 在 *S* 中，*v* 在 *T* 中。如果未指定 *T*，则假定它是所有不在 *S* 中的节点的集合。
Parameters
----------
G : NetworkX 图
nbunch1 : 可迭代对象
图中表示节点集合的可迭代对象，其边缘边界将被返回。（这是上述定义中的集合 *S*。）
nbunch2 : 可迭代对象
表示目标（或“外部”）节点集合的可迭代对象。（这是上述定义中的集合 *T*。）如果未指定，则假定它是 `G` 中所有不在 `nbunch1` 中的节点集合。
keys : bool
此参数与 :meth:`MultiGraph.edges` 中的含义相同。
data : bool 或 object
此参数与 :meth:`MultiGraph.edges` 中的含义相同。
default : object
此参数与 :meth:`MultiGraph.edges` 中的含义相同。
Returns
-------
迭代器
一个迭代器，遍历 `nbunch1` 相对于 `nbunch2` 的边缘边界中的边。如果指定了 `keys` 、 `data` 或 `default` ，并且 `G` 是多图，则边将返回带有键和/或数据，如 :meth:`MultiGraph.edges` 中所示。
Examples
--------
>>> G = nx.wheel_graph(6)
当 nbunch2=None 时：
>>> list(nx.edge_boundary(G, (1, 3)))
[(1, 0), (1, 2), (1, 5), (3, 0), (3, 2), (3, 4)]
当 nbunch2 被指定时：
>>> list(nx.edge_boundary(G, (1, 3), (2, 0)))
[(1, 0), (1, 2), (3, 0), (3, 2)]
Notes
-----
任何在 `nbunch` 中但不在图 `G` 中的元素将被忽略。
`nbunch1` 和 `nbunch2` 通常应是互斥的，但为了速度和通用性，这里并不要求如此。
"""
nset1 = {n for n in nbunch1 if n in G}
# Here we create an iterator over edges incident to nodes in the set
# `nset1`. The `Graph.edges()` method does not provide a guarantee
# on the orientation of the edges, so our algorithm below must
# handle the case in which exactly one orientation, either (u, v) or
# (v, u), appears in this iterable.
if G.is_multigraph():
edges = G.edges(nset1, data=data, keys=keys, default=default)
else:
edges = G.edges(nset1, data=data, default=default)
# If `nbunch2` is not provided, then it is assumed to be the set
# complement of `nbunch1`. For the sake of efficiency, this is
# implemented by using the `not in` operator, instead of by creating
# an additional set and using the `in` operator.
if nbunch2 is None:
return (e for e in edges if (e[0] in nset1) ^ (e[1] in nset1))
nset2 = set(nbunch2)
return (
e
for e in edges
if (e[0] in nset1 and e[1] in nset2) or (e[1] in nset1 and e[0] in nset2)
)
[docs]
@nx._dispatchable
def node_boundary(G, nbunch1, nbunch2=None):
"""返回 `nbunch1` 的节点边界。
集合 *S* 相对于集合 *T* 的*节点边界*是集合 *T* 中的节点 *v* 的集合，使得对于 *S* 中的某个节点 *u*，存在一条边连接 *u* 和 *v*。如果未指定 *T*，则假定它是所有不在 *S* 中的节点的集合。
Parameters
----------
G : NetworkX 图
nbunch1 : 可迭代对象
图中表示节点集合的可迭代对象，其节点边界将被返回。（这是上述定义中的集合 *S*。）
nbunch2 : 可迭代对象
表示目标（或“外部”）节点集合的可迭代对象。（这是上述定义中的集合 *T*。）如果未指定，则假定它是 `G` 中不在 `nbunch1` 中的所有节点的集合。
Returns
-------
集合
`nbunch1` 相对于 `nbunch2` 的节点边界。
Examples
--------
>>> G = nx.wheel_graph(6)
当 nbunch2=None 时：
>>> list(nx.node_boundary(G, (3, 4)))
[0, 2, 5]
当 nbunch2 被指定时：
>>> list(nx.node_boundary(G, (3, 4), (0, 1, 5)))
[0, 5]
Notes
-----
任何在 `nbunch` 中但不在图 `G` 中的元素将被忽略。
`nbunch1` 和 `nbunch2` 通常意味着是不相交的，但为了速度和通用性，这里并不要求如此。
"""
nset1 = {n for n in nbunch1 if n in G}
bdy = set(chain.from_iterable(G[v] for v in nset1)) - nset1
# If `nbunch2` is not specified, it is assumed to be the set
# complement of `nbunch1`.
if nbunch2 is not None:
bdy &= set(nbunch2)
return bdy
