"""提供用于计算图的次要图的函数。"""
from itertools import chain, combinations, permutations, product
import networkx as nx
from networkx import density
from networkx.exception import NetworkXException
from networkx.utils import arbitrary_element
__all__ = [
"contracted_edge",
"contracted_nodes",
"equivalence_classes",
"identified_nodes",
"quotient_graph",
]
chaini = chain.from_iterable
[docs]
def equivalence_classes(iterable, relation):
"""返回将 `relation` 应用于 `iterable` 时的等价类。
等价类或块由 `iterable` 中的对象组成，这些对象都是等价的。它们被定义为等价，如果 `relation` 函数在传递该类中的任意两个对象时返回 `True` ，否则返回 `False` 。要定义等价关系，函数必须是自反的、对称的和传递的。
Parameters
----------
iterable : list, tuple, 或 set
元素/节点的可迭代对象。
relation : function
一个布尔值函数，实现 `iterable` 元素上的等价关系（自反、对称、传递的二元关系）——它必须接受两个元素并返回 `True` 如果它们是相关的，否则返回 `False` 。
Returns
-------
set of frozensets
由等价关系函数 `relation` 在 `iterable` 元素上诱导的分区的集合。返回集合中的每个成员集表示一个等价类或块。
重复元素将被忽略，因此 `iterable` 为 :class:`set` 时最有意义。
Notes
-----
此函数不检查 `relation` 是否表示等价关系。你可以使用 `is_partition` 检查你的等价类是否提供分区。
Examples
--------
设 `X` 为从 `0` 到 `9` 的整数集合，并考虑 `X` 上的等价关系 `R` ，即模 `3` 的同余关系：这意味着 `X` 中的两个整数 `x` 和 `y` 在 `R` 下等价，如果它们除以 `3` 时余数相同，即 `(x - y) mod 3 = 0` 。
此关系的等价类为 `{0, 3, 6, 9}` 、 `{1, 4, 7}` 、 `{2, 5, 8}` ： `0` 、 `3` 、 `6` 、 `9` 都能被 `3` 整除并余数为零； `1` 、 `4` 、 `7` 余数为 `1` ；而 `2` 、 `5` 、 `8` 余数为 `2` 。我们可以通过调用 `equivalence_classes` 并传入 `X` 和一个 `R` 的函数实现来看到这一点。
>>> X = set(range(10))
>>> def mod3(x, y):
... return (x - y) % 3 == 0
>>> equivalence_classes(X, mod3) # doctest: +SKIP
{frozenset({1, 4, 7}), frozenset({8, 2, 5}), frozenset({0, 9, 3, 6})}
"""
# For simplicity of implementation, we initialize the return value as a
# list of lists, then convert it to a set of sets at the end of the
# function.
blocks = []
# Determine the equivalence class for each element of the iterable.
for y in iterable:
# Each element y must be in *exactly one* equivalence class.
#
# Each block is guaranteed to be non-empty
for block in blocks:
x = arbitrary_element(block)
if relation(x, y):
block.append(y)
break
else:
# If the element y is not part of any known equivalence class, it
# must be in its own, so we create a new singleton equivalence
# class for it.
blocks.append([y])
return {frozenset(block) for block in blocks}
[docs]
@nx._dispatchable(edge_attrs="weight", returns_graph=True)
def quotient_graph(
G,
partition,
edge_relation=None,
node_data=None,
edge_data=None,
weight="weight",
relabel=False,
create_using=None,
):
"""返回在节点上指定等价关系下 `G` 的商图。
Parameters
----------
G : NetworkX 图
要返回具有指定节点关系的商图的图。
partition : 函数，或字典或列表的列表、元组或集合
如果是函数，该函数必须表示 `G` 节点上的等价关系。它必须接受两个参数 *u* 和 *v*，并在 *u* 和 *v* 处于同一等价类时返回 True。等价类形成返回图中节点的形式。
如果是字典的列表/元组/集合，键可以是任何有意义的块标签，但值必须是块的列表/元组/集合（每个块一个列表/元组/集合），并且块必须形成图节点的有效分区。也就是说，每个节点必须恰好在一个分区块中。
如果是集合的列表，该列表必须形成图节点的有效分区。也就是说，每个节点必须恰好在一个分区块中。
edge_relation : 具有两个参数的布尔函数
该函数必须在 `G` 的分区的 *块* 上表示边关系。它必须接受两个参数，*B* 和 *C*，每个参数都是一个节点集合，并在返回图中块 *B* 和块 *C* 之间应该有一条边时返回 True。
如果未指定 `edge_relation` ，则假定为以下关系。块 *B* 与块 *C* 相关联，当且仅当 *B* 中的某些节点与 *C* 中的某些节点相邻，根据 `G` 的边集。
node_data : 函数
该函数接受一个参数，*B*， `G` 中的一个节点集合，并且必须返回一个字典，表示要在商图中表示 *B* 的节点上设置的节点数据属性。如果为 None，将设置以下节点属性：
* 'graph'，该块表示的图 `G` 的子图，
* 'nnodes'，该块中的节点数，
* 'nedges'，该块内的边数，
* 'density'，该块表示的 `G` 子图的密度。
edge_data : 函数
该函数接受两个参数，*B* 和 *C*，每个参数都是一个节点集合，并且必须返回一个字典，表示要在商图中连接 *B* 和 *C* 的边上设置的边数据属性（如果根据 `edge_relation` 在商图中没有这样的边，则该函数的输出将被忽略）。
如果商图是多重图，则不应用此函数，因为图 `G` 中每条边的边数据都出现在商图的边中。
weight : 字符串或 None，可选（默认="weight"）
边属性的名称，该属性保存用作权重的数值。如果为 None，则每条边的权重为 1。
relabel : 布尔值
如果为 True，则将商图的节点重新标记为非负整数。否则，节点将通过表示 `partition` 中给定块的 :class:`frozenset` 实例来标识。
create_using : NetworkX 图构造函数，可选（默认=nx.Graph）
要创建的图类型。如果是图实例，则在填充之前清除。
Returns
-------
NetworkX 图
`G` 在由 `partition` 指定的等价关系下的商图。如果分区以 :class:`set` 实例的列表形式给出且 `relabel` 为 False，则每个节点将是一个对应于相同 :class:`set` 的 :class:`frozenset` 。
Raises
------
NetworkXException
如果给定的分区不是 `G` 节点的有效分区。
Examples
--------
在“相同邻居”等价关系下，完全二分图的商图是 `K_2` 。在此关系下，两个节点等价当且仅当它们不邻接但具有相同的邻居集合。
>>> G = nx.complete_bipartite_graph(2, 3)
>>> same_neighbors = lambda u, v: (u not in G[v] and v not in G[u] and G[u] == G[v])
>>> Q = nx.quotient_graph(G, same_neighbors)
>>> K2 = nx.complete_graph(2)
>>> nx.is_isomorphic(Q, K2)
True
在“相同强连通分量”等价关系下，有向图的商图是图的凝聚（参见 :func:`condensation` ）。此示例来自维基百科文章 * `强连通分量`_*。
>>> G = nx.DiGraph()
>>> edges = [
... "ab",
... "be",
... "bf",
... "bc",
... "cg",
... "cd",
... "dc",
... "dh",
... "ea",
... "ef",
... "fg",
... "gf",
... "hd",
... "hf",
... ]
>>> G.add_edges_from(tuple(x) for x in edges)
>>> components = list(nx.strongly_connected_components(G))
>>> sorted(sorted(component) for component in components)
[['a', 'b', 'e'], ['c', 'd', 'h'], ['f', 'g']]
>>>
>>> C = nx.condensation(G, components)
>>> component_of = C.graph["mapping"]
>>> same_component = lambda u, v: component_of[u] == component_of[v]
>>> Q = nx.quotient_graph(G, same_component)
>>> nx.is_isomorphic(C, Q)
True
节点识别可以表示为在将两个节点置于一个块并将每个其他节点置于其自己的单例块的等价关系下的图的商图。
>>> K24 = nx.complete_bipartite_graph(2, 4)
>>> K34 = nx.complete_bipartite_graph(3, 4)
>>> C = nx.contracted_nodes(K34, 1, 2)
>>> nodes = {1, 2}
>>> is_contracted = lambda u, v: u in nodes and v in nodes
>>> Q = nx.quotient_graph(K34, is_contracted)
>>> nx.is_isomorphic(Q, C)
True
>>> nx.is_isomorphic(Q, K24)
True
[1]_ 中描述的块建模技术可以实现为商图。
>>> G = nx.path_graph(6)
>>> partition = [{0, 1}, {2, 3}, {4, 5}]
>>> M = nx.quotient_graph(G, partition, relabel=True)
>>> list(M.edges())
[(0, 1), (1, 2)]
以下是使用块集字典的示例。
>>> G = nx.path_graph(6)
>>> partition = {0: {0, 1}, 2: {2, 3}, 4: {4, 5}}
>>> M = nx.quotient_graph(G, partition, relabel=True)
>>> list(M.edges())
[(0, 1), (1, 2)]
分区可以以多种方式表示：
0. 块的列表/元组/集合的列表/元组/集合
1. 以块标签为键，块的列表/元组/集合为值的字典
2. 以块的列表/元组/集合为键，块标签为值的字典
3. 从原始可迭代对象到块标签的函数
4. 目标可迭代对象上的等价关系函数
由于 `quotient_graph` 仅接受以 (0)、(1) 或 (4) 形式表示的分区，因此可以使用 `equivalence_classes` 函数获取正确形式的分区，以便调用 `quotient_graph` 。
.. _强连通分量: https://en.wikipedia.org/wiki/Strongly_connected_component
References
----------
.. [1] Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj.
*Generalized Blockmodeling*.
Cambridge University Press, 2004.
"""
# If the user provided an equivalence relation as a function to compute
# the blocks of the partition on the nodes of G induced by the
# equivalence relation.
if callable(partition):
# equivalence_classes always return partition of whole G.
partition = equivalence_classes(G, partition)
if not nx.community.is_partition(G, partition):
raise nx.NetworkXException(
"Input `partition` is not an equivalence relation for nodes of G"
)
return _quotient_graph(
G,
partition,
edge_relation,
node_data,
edge_data,
weight,
relabel,
create_using,
)
# If the partition is a dict, it is assumed to be one where the keys are
# user-defined block labels, and values are block lists, tuples or sets.
if isinstance(partition, dict):
partition = list(partition.values())
# If the user provided partition as a collection of sets. Then we
# need to check if partition covers all of G nodes. If the answer
# is 'No' then we need to prepare suitable subgraph view.
partition_nodes = set().union(*partition)
if len(partition_nodes) != len(G):
G = G.subgraph(partition_nodes)
# Each node in the graph/subgraph must be in exactly one block.
if not nx.community.is_partition(G, partition):
raise NetworkXException("each node must be in exactly one part of `partition`")
return _quotient_graph(
G,
partition,
edge_relation,
node_data,
edge_data,
weight,
relabel,
create_using,
)
def _quotient_graph(
G, partition, edge_relation, node_data, edge_data, weight, relabel, create_using
):
"""构建商图，假设输入已经过检查"""
if create_using is None:
H = G.__class__()
else:
H = nx.empty_graph(0, create_using)
# By default set some basic information about the subgraph that each block
# represents on the nodes in the quotient graph.
if node_data is None:
def node_data(b):
S = G.subgraph(b)
return {
"graph": S,
"nnodes": len(S),
"nedges": S.number_of_edges(),
"density": density(S),
}
# Each block of the partition becomes a node in the quotient graph.
partition = [frozenset(b) for b in partition]
H.add_nodes_from((b, node_data(b)) for b in partition)
# By default, the edge relation is the relation defined as follows. B is
# adjacent to C if a node in B is adjacent to a node in C, according to the
# edge set of G.
#
# This is not a particularly efficient implementation of this relation:
# there are O(n^2) pairs to check and each check may require O(log n) time
# (to check set membership). This can certainly be parallelized.
if edge_relation is None:
def edge_relation(b, c):
return any(v in G[u] for u, v in product(b, c))
# By default, sum the weights of the edges joining pairs of nodes across
# blocks to get the weight of the edge joining those two blocks.
if edge_data is None:
def edge_data(b, c):
edgedata = (
d
for u, v, d in G.edges(b | c, data=True)
if (u in b and v in c) or (u in c and v in b)
)
return {"weight": sum(d.get(weight, 1) for d in edgedata)}
block_pairs = permutations(H, 2) if H.is_directed() else combinations(H, 2)
# In a multigraph, add one edge in the quotient graph for each edge
# in the original graph.
if H.is_multigraph():
edges = chaini(
(
(b, c, G.get_edge_data(u, v, default={}))
for u, v in product(b, c)
if v in G[u]
)
for b, c in block_pairs
if edge_relation(b, c)
)
# In a simple graph, apply the edge data function to each pair of
# blocks to determine the edge data attributes to apply to each edge
# in the quotient graph.
else:
edges = (
(b, c, edge_data(b, c)) for (b, c) in block_pairs if edge_relation(b, c)
)
H.add_edges_from(edges)
# If requested by the user, relabel the nodes to be integers,
# numbered in increasing order from zero in the same order as the
# iteration order of `partition`.
if relabel:
# Can't use nx.convert_node_labels_to_integers() here since we
# want the order of iteration to be the same for backward
# compatibility with the nx.blockmodel() function.
labels = {b: i for i, b in enumerate(partition)}
H = nx.relabel_nodes(H, labels)
return H
[docs]
@nx._dispatchable(
preserve_all_attrs=True, mutates_input={"not copy": 4}, returns_graph=True
)
def contracted_nodes(G, u, v, self_loops=True, copy=True):
"""返回由收缩 `u` 和 `v` 得到的图。
节点收缩将这两个节点识别为一个单一节点，该节点与原有两个节点所连接的任何边相连。
Parameters
----------
G : NetworkX 图
将要进行节点收缩的图。
u, v : 节点
必须是 `G` 中的节点。
self_loops : 布尔值
如果为 True， `G` 中连接 `u` 和 `v` 的任何边在返回的图中将成为新节点上的自环。
copy : 布尔值
如果为 True（默认 True），将复制 `G` 并返回该副本，而不是直接修改 `G` 。
Returns
-------
Networkx 图
如果 Copy 为 True，
返回一个与 `G` 类型相同的新图对象（ `G` 保持不变），其中 `u` 和 `v` 被识别为一个单一节点。右节点 `v` 将被合并到节点 `u` 中，因此返回的图中只会出现 `u` 。
如果 copy 为 False，
修改 `G` ，使 `u` 和 `v` 被识别为一个单一节点。右节点 `v` 将被合并到节点 `u` 中，因此返回的图中只会出现 `u` 。
Notes
-----
对于多重图，重定向边的边键可能与旧边的边键不同。这是因为边键在每对节点中仅是唯一的。
对于非多重图，如果 `u` 和 `v` 与第三个节点 `w` 相邻，边 ( `v` , `w` ) 将被收缩到边 ( `u` , `w` )，其属性存储在一个 "contraction" 属性中。
此函数也可作为 `identified_nodes` 使用。
Examples
--------
收缩四节点循环图 `C_4` 中的两个非相邻节点会得到路径图（忽略平行边）：
>>> G = nx.cycle_graph(4)
>>> M = nx.contracted_nodes(G, 1, 3)
>>> P3 = nx.path_graph(3)
>>> nx.is_isomorphic(M, P3)
True
>>> G = nx.MultiGraph(P3)
>>> M = nx.contracted_nodes(G, 0, 2)
>>> M.edges
MultiEdgeView([(0, 1, 0), (0, 1, 1)])
>>> G = nx.Graph([(1, 2), (2, 2)])
>>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
>>> list(H.nodes())
[1]
>>> list(H.edges())
[(1, 1)]
在具有自环的 ``MultiDiGraph`` 中，入边和出边将分别作为边处理，因此在收缩具有自环的节点时，收缩将添加多条边：
>>> G = nx.MultiDiGraph([(1, 2), (2, 2)])
>>> H = nx.contracted_nodes(G, 1, 2)
>>> list(H.edges()) # 原图 G 中的边 1->2, 2->2, 2<-2
[(1, 1), (1, 1), (1, 1)]
>>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
>>> list(H.edges()) # 原图 G 中的边 2->2, 2<-2
[(1, 1), (1, 1)]
See Also
--------
contracted_edge
quotient_graph
"""
# Copying has significant overhead and can be disabled if needed
if copy:
H = G.copy()
else:
H = G
# edge code uses G.edges(v) instead of G.adj[v] to handle multiedges
if H.is_directed():
edges_to_remap = chain(G.in_edges(v, data=True), G.out_edges(v, data=True))
else:
edges_to_remap = G.edges(v, data=True)
# If the H=G, the generators change as H changes
# This makes the edges_to_remap independent of H
if not copy:
edges_to_remap = list(edges_to_remap)
v_data = H.nodes[v]
H.remove_node(v)
for prev_w, prev_x, d in edges_to_remap:
w = prev_w if prev_w != v else u
x = prev_x if prev_x != v else u
if ({prev_w, prev_x} == {u, v}) and not self_loops:
continue
if not H.has_edge(w, x) or G.is_multigraph():
H.add_edge(w, x, **d)
else:
if "contraction" in H.edges[(w, x)]:
H.edges[(w, x)]["contraction"][(prev_w, prev_x)] = d
else:
H.edges[(w, x)]["contraction"] = {(prev_w, prev_x): d}
if "contraction" in H.nodes[u]:
H.nodes[u]["contraction"][v] = v_data
else:
H.nodes[u]["contraction"] = {v: v_data}
return H
identified_nodes = contracted_nodes
[docs]
@nx._dispatchable(
preserve_edge_attrs=True, mutates_input={"not copy": 3}, returns_graph=True
)
def contracted_edge(G, edge, self_loops=True, copy=True):
"""返回由收缩指定边得到的新图。
边收缩将边的两个端点识别为一个单一节点，该节点连接到原有两个节点所连接的任何边。通过边收缩得到的新图称为原图的*子图*。
Parameters
----------
G : NetworkX图
将要收缩边的图。
edge : 元组
必须是 `G` 中的两个节点。
self_loops : 布尔值
如果为True， `G` 中连接边端点的任何边（包括 `edge` ）在返回的图中将成为新节点的自环。
copy : 布尔值（默认为True）
如果为True，将在 `G` 的副本上执行收缩操作，否则将在原地进行收缩。
Returns
-------
NetworkX图
一个与 `G` 类型相同的新图对象（ `G` 保持不变），其中 `edge` 的端点被识别为一个单一节点。 `edge` 的右节点将被合并到左节点中，因此返回的图中只会出现左节点。
Raises
------
ValueError
如果 `edge` 不是 `G` 中的边。
Examples
--------
尝试收缩两个非相邻节点会引发错误：
>>> G = nx.cycle_graph(4)
>>> nx.contracted_edge(G, (1, 3))
Traceback (most recent call last):
...
ValueError: Edge (1, 3) does not exist in graph G; cannot contract it
在具有*n*个节点的环图中收缩两个相邻节点会得到具有*n - 1*个节点的环图：
>>> C5 = nx.cycle_graph(5)
>>> C4 = nx.cycle_graph(4)
>>> M = nx.contracted_edge(C5, (0, 1), self_loops=False)
>>> nx.is_isomorphic(M, C4)
True
See Also
--------
contracted_nodes
quotient_graph
"""
u, v = edge[:2]
if not G.has_edge(u, v):
raise ValueError(f"Edge {edge} does not exist in graph G; cannot contract it")
return contracted_nodes(G, u, v, self_loops=self_loops, copy=copy)
