code: def dag_to_branching(G):
      """Returns a branching representing all (overlapping) paths from
      root nodes to leaf nodes in the given directed acyclic graph.
  
      As described in :mod:`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 `v` in `G` with *k* parents becomes *k* distinct nodes in
      the returned branching, one for each parent, and the sub-DAG rooted
      at `v` is duplicated for each copy. The algorithm then recurses on
      the children of each copy of `v`.
  
      Parameters
      ----------
      G : NetworkX graph
          A directed acyclic graph.
  
      Returns
      -------
      DiGraph
          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.
  
      Raises
      ------
      NetworkXNotImplemented
          If `G` is not directed, or if `G` 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
      :func:`networkx.convert_node_labels_to_integers` function.
  
      The current implementation of this function uses
      :func:`networkx.prefix_tree`, so it is subject to the limitations of
      that function.
  
      """
      if has_cycle(G):
          msg = "dag_to_branching is only defined for acyclic graphs"
          raise nx.HasACycle(msg)
      paths = root_to_leaf_paths(G)
      B = nx.prefix_tree(paths)
      # Remove the synthetic `root`(0) and `NIL`(-1) nodes from the tree
      B.remove_node(0)
      B.remove_node(-1)
      return B
  
imports: import heapq
  from collections import deque
  from functools import partial
  from itertools import chain, combinations, product, starmap
  from math import gcd
  import networkx
  from networkx.utils import arbitrary_element, not_implemented_for, pairwise
label_desc: Use image node_id 17 for calling a global function with example usage: dag_to_branching(G) and returns: B