networkx.algorithms.dag.dag_to_branching¶
-
dag_to_branching
(G)[source]¶ Returns a branching representing all (overlapping) paths from root nodes to leaf nodes in the given directed acyclic graph.
As described in
networkx.algorithms.tree.recognition
, a branching is a directed forest in which each node has at most one parent. In other words, a branching is a disjoint union of arborescences. For this function, each node of in-degree zero inG
becomes a root of one of the arborescences, and there will be one leaf node for each distinct path from that root to a leaf node inG
.Each node
v
inG
with k parents becomes k distinct nodes in the returned branching, one for each parent, and the sub-DAG rooted atv
is duplicated for each copy. The algorithm then recurses on the children of each copy ofv
.- Parameters
G (NetworkX graph) – A directed acyclic graph.
- Returns
The branching in which there is a bijection between root-to-leaf paths in
G
(in which multiple paths may share the same leaf) and root-to-leaf paths in the branching (in which there is a unique path from a root to a leaf).Each node has an attribute ‘source’ whose value is the original node to which this node corresponds. No other graph, node, or edge attributes are copied into this new graph.
- Return type
- Raises
NetworkXNotImplemented – If
G
is not directed, or ifG
is a multigraph.HasACycle – If
G
is not acyclic.
Examples
To examine which nodes in the returned branching were produced by which original node in the directed acyclic graph, we can collect the mapping from source node to new nodes into a dictionary. For example, consider the directed diamond graph:
>>> 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
To copy node attributes from the original graph to the new graph, you can use a dictionary like the one constructed in the above example:
>>> for source, nodes in sources.items(): ... for v in nodes: ... B.nodes[v].update(G.nodes[source])
Notes
This function is not idempotent in the sense that the node labels in the returned branching may be uniquely generated each time the function is invoked. In fact, the node labels may not be integers; in order to relabel the nodes to be more readable, you can use the
networkx.convert_node_labels_to_integers()
function.The current implementation of this function uses
networkx.prefix_tree()
, so it is subject to the limitations of that function.