dag_to_branching(G)
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 in G 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 in G.
Each node :None:None:`v` in G with k parents becomes k distinct nodes in the returned branching, one for each parent, and the sub-DAG rooted at :None:None:`v` is duplicated for each copy. The algorithm then recurses on the children of each copy of :None:None:`v`.
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.
A directed acyclic graph.
If G is not acyclic.
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.
Returns a branching representing all (overlapping) paths from root nodes to leaf nodes in the given directed acyclic 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"])
2See :>>> for source, nodes in sources.items(): ... for v in nodes: ... B.nodes[v].update(G.nodes[source])
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them