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
。它必须有两个参数 u 和 v 并在下列情况下返回True u 和 v 在同一等价类中。等价类形成返回图中的节点。如果是列表/元组/集的字典,则键可以是任何有意义的块标签,但值必须是块列表/元组/集(每个块一个列表/元组/集),并且块必须形成图形节点的有效分区。也就是说,每个节点必须正好位于分区的一个块中。
如果是集合列表,则该列表必须构成图形节点的有效分区。也就是说,每个节点必须恰好位于分区的一个块中。
- edge_relation带有两个参数的布尔函数
此函数必须表示 块 的
partition
的G
。它必须有两个论点, B 和 C ,每一个都是一组节点,并且在应该有边连接块时恰好返回True B 要阻止 C 在返回的图表中。如果
edge_relation
未指定,假定为以下关系。街区 B 与块相关 C 如果且仅当中的某个节点 B 与中的某个节点相邻 C ,根据边缘集G
.- edge_data功能
该函数有两个参数, B 和 C ,每个节点都是一组节点,并且必须返回表示要在边连接上设置的边数据属性的字典 B 和 C ,是否应该有边连接 B 和 C 在商图中(如果由下式确定的商图中没有出现这样的边
edge_relation
则忽略该函数的输出)。如果商图是多图,则不应用此函数,因为图中每个边的边数据
G
出现在商图的边缘。- node_data功能
此函数接受一个参数, B 中的一组节点
G
,并且必须返回一个表示要在节点上设置的节点数据属性的字典, B 在商图中。如果无,则将设置以下节点属性:“图形”,图形的子图形
G
这个块代表,“nondes”,此块中的节点数,
“Nedges”,此块中的边数,
“密度”,子图的密度
G
此块表示的。
- relabel布尔尔
如果为True,则将商图的节点重新标记为非负整数。否则,节点将使用
frozenset
实例表示中给出的块partition
。- create_usingNetworkX图形构造函数,可选(默认=nx.Graph)
要创建的图表类型。如果是图表实例,则在填充之前清除。
- 返回
- 加薪
- 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
。