dag_to_branching

dag_to_branching(G)

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

如上所述 networkx.algorithms.tree.recognition ，A 分支 是一个定向林，其中每个节点最多有一个父节点。换句话说，分支是 树枝状 . 对于此函数，每个节点的度数为0 G 变成了一个乔木的根，从根到叶节点的每一条不同路径都有一个叶节点。 G .

每个节点 v 在里面 G 具有 k 父母成为 k 返回分支中的不同节点，每个父节点一个，子DAG的根位于 v 每个副本都有副本。然后该算法在每个副本的子级上循环 v .

参数

G网络X图表

有向无环图。

返回

DiGraph

根到叶之间有双射的分支。 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])