dag_to_branching#

dag_to_branching(G)[source]#

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

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

G 中每个有 k 个父节点的节点 v 在返回的分支中变成 k 个不同的节点，每个父节点对应一个，并且以 v 为根的子有向无环图在每个副本中重复。然后算法递归处理每个副本的子节点。

Parameters:
GNetworkX 图

一个有向无环图。

Returns:
DiGraph

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

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

Raises:
NetworkXNotImplemented

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

HasACycle

如果 G 不是无环的。

Notes

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

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

Examples

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

>>> 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])
On this page