quotient_graph#

quotient_graph(G, partition, edge_relation=None, node_data=None, edge_data=None, relabel=False, create_using=None)[源代码]#

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

参数
G网络X图表

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

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

如果是函数,则此函数必须表示 G 。它必须有两个参数 uv 并在下列情况下返回True uv 在同一等价类中。等价类形成返回图中的节点。

如果是列表/元组/集的字典,则键可以是任何有意义的块标签,但值必须是块列表/元组/集(每个块一个列表/元组/集),并且块必须形成图形节点的有效分区。也就是说,每个节点必须正好位于分区的一个块中。

如果是集合列表,则该列表必须构成图形节点的有效分区。也就是说,每个节点必须恰好位于分区的一个块中。

edge_relation带有两个参数的布尔函数

此函数必须表示 partitionG 。它必须有两个论点, BC ,每一个都是一组节点,并且在应该有边连接块时恰好返回True B 要阻止 C 在返回的图表中。

如果 edge_relation 未指定,假定为以下关系。街区 B 与块相关 C 如果且仅当中的某个节点 B 与中的某个节点相邻 C ,根据边缘集 G .

edge_data功能

该函数有两个参数, BC ,每个节点都是一组节点,并且必须返回表示要在边连接上设置的边数据属性的字典 BC ,是否应该有边连接 BC 在商图中(如果由下式确定的商图中没有出现这样的边 edge_relation 则忽略该函数的输出)。

如果商图是多图,则不应用此函数,因为图中每个边的边数据 G 出现在商图的边缘。

node_data功能

此函数接受一个参数, B 中的一组节点 G ,并且必须返回一个表示要在节点上设置的节点数据属性的字典, B 在商图中。如果无,则将设置以下节点属性:

  • “图形”,图形的子图形 G 这个块代表,

  • “nondes”,此块中的节点数,

  • “Nedges”,此块中的边数,

  • “密度”,子图的密度 G 此块表示的。

relabel布尔尔

如果为True,则将商图的节点重新标记为非负整数。否则,节点将使用 frozenset 实例表示中给出的块 partition

create_usingNetworkX图形构造函数,可选(默认=nx.Graph)

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

返回
网络X图表

的商图 G 在等价关系下 partition . 如果分区是作为 set 实例和 relabel 如果为false,则每个节点都将是 frozenset 对应于相同的 set .

加薪
NetworkXException

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

工具书类

1

Patrick Doreian、Vladimir Batagelj和Anuska Ferligoj。 广义块模型 . 剑桥大学出版社,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)]

以下是示例,但使用分区作为块集合的字典。

>>> 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) a list/tuple/set of block lists/tuples/sets
(1) a dict with block labels as keys and blocks lists/tuples/sets as values
(2) a dict with block lists/tuples/sets as keys and block labels as values
(3) a function from nodes in the original iterable to block labels
(4) an equivalence relation function on the target iterable

作为 quotient_graph 设计为仅接受表示为(0)、(1)或(4)的分区,则 equivalence_classes 函数可以用来获得正确形式的分区,以便调用 quotient_graph