quotient_graph#

quotient_graph(G, partition, edge_relation=None, node_data=None, edge_data=None, weight='weight', relabel=False, create_using=None)[source]#

返回在节点上指定等价关系下 G 的商图。

Parameters:
GNetworkX 图

要返回具有指定节点关系的商图的图。

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 中给定块的 frozenset 实例来标识。

create_usingNetworkX 图构造函数，可选（默认=nx.Graph）

要创建的图类型。如果是图实例，则在填充之前清除。

Returns:
NetworkX 图

G 在由 partition 指定的等价关系下的商图。如果分区以 set 实例的列表形式给出且 relabel 为 False，则每个节点将是一个对应于相同 set 的 frozenset 。

Raises:
NetworkXException

如果给定的分区不是 G 节点的有效分区。

References

[1]

Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj. Generalized Blockmodeling. Cambridge University Press, 2004.

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

在“相同强连通分量”等价关系下，有向图的商图是图的凝聚（参见 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)]

分区可以以多种方式表示：

  1. 块的列表/元组/集合的列表/元组/集合

  2. 以块标签为键，块的列表/元组/集合为值的字典

  3. 以块的列表/元组/集合为键，块标签为值的字典

  4. 从原始可迭代对象到块标签的函数

  5. 目标可迭代对象上的等价关系函数

由于 quotient_graph 仅接受以 (0)、(1) 或 (4) 形式表示的分区，因此可以使用 equivalence_classes 函数获取正确形式的分区，以便调用 quotient_graph 。

On this page