quotient_graph#

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

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

参数：
GNetworkX 图

要返回其在指定节点关系下的商图的图。

partition函数，或列表、元组或集合组成的字典或列表

如果是一个函数，该函数必须表示图 G 节点上的一个等价关系。它必须接受两个参数 u 和 v，并且仅当 u 和 v 属于同一等价类时返回 True。这些等价类构成返回图中的节点。

如果是一个列表/元组/集合组成的字典，键可以是任何有意义的块标签，但值必须是块列表/元组/集合（每个块一个列表/元组/集合），并且这些块必须构成图节点的有效划分。也就是说，每个节点必须且仅属于划分中的一个块。

如果是一个集合组成的列表，该列表必须构成图节点的有效划分。也就是说，每个节点必须且仅属于划分中的一个块。

edge_relation接受两个参数的布尔函数

此函数必须表示图 G 划分的块上的一个边关系。它必须接受两个参数 B 和 C（每个参数都是一个节点集合），并且仅当返回的图中应存在连接块 B 到块 C 的边时返回 True。

如果未指定 edge_relation，则默认为以下关系：块 B 与块 C 相关当且仅当根据图 G 的边集，B 中的某个节点与 C 中的某个节点相邻。

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）

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

返回：
NetworkX 图

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

抛出：
NetworkXException

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

参考文献

[1]

Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj. 泛化块模型 (Generalized Blockmodeling). Cambridge University Press, 2004.

示例

完全二分图在“相同邻居”等价关系下的商图是 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()）。此示例来自维基百科文章《强连通分量》（`Strongly connected component`_）。

>>> 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)]

这里是使用块集合字典作为 partition 的示例。

>>> 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。

在本页