dag_to_branching#

dag_to_branching(G)[source]#

返回一个分支结构，该结构表示给定有向无环图（DAG）中从根节点到叶节点的所有（重叠）路径。

如 networkx.algorithms.tree.recognition 中所述，一个*分支结构*是一个有向森林，其中每个节点最多只有一个父节点。换句话说，一个分支结构是*树状结构*的无交并。对于此函数，G 中每个入度为零的节点将成为一个树状结构的根，并且从该根到 G 中某个叶节点的每条不同路径都将对应一个叶节点。

G 中每个有 k 个父节点的节点 v 在返回的分支结构中会变成 k 个不同的节点，每个父节点对应一个，并且以 v 为根的子 DAG 会为每个副本复制。然后，该算法会对其 v 的每个副本的子节点进行递归。

参数:
GNetworkX 图

一个有向无环图。

返回:
有向图

返回的分支结构中，G 中从根到叶的路径（其中多条路径可能共享同一个叶节点）与分支结构中从根到叶的路径（其中从根到叶只有一条唯一路径）之间存在一一对应关系。

每个节点都有一个属性‘source’，其值是该节点对应的原始节点。其他图、节点或边的属性都不会复制到这个新图中。

引发:
NetworkXNotImplemented

如果 G 不是有向图，或者 G 是多重图。

HasACycle

如果 G 不是无环图。

注意事项

此函数不是幂等的，因为每次调用该函数时，返回的分支结构中的节点标签可能是唯一生成的。实际上，节点标签可能不是整数；为了使节点标签更易读，可以使用 networkx.convert_node_labels_to_integers() 函数。

此函数当前实现使用了 networkx.prefix_tree()，因此受该函数限制的影响。

示例

为了检查返回的分支结构中的哪些节点是由有向无环图中的哪个原始节点生成的，我们可以将从源节点到新节点的映射收集到一个字典中。例如，考虑有向菱形图

>>> from collections import defaultdict
>>> from operator import itemgetter
>>>
>>> G = nx.DiGraph(nx.utils.pairwise("abd"))
>>> G.add_edges_from(nx.utils.pairwise("acd"))
>>> B = nx.dag_to_branching(G)
>>>
>>> sources = defaultdict(set)
>>> for v, source in B.nodes(data="source"):
...     sources[source].add(v)
>>> len(sources["a"])
1
>>> len(sources["d"])
2

要将节点属性从原始图复制到新图，可以使用上面示例中构建的字典

>>> for source, nodes in sources.items():
...     for v in nodes:
...         B.nodes[v].update(G.nodes[source])
在本页