networkx.algorithms.tree.coding.to_nested_tuple¶
-
to_nested_tuple
(T, root, canonical_form=False)[source]¶ Returns a nested tuple representation of the given tree.
The nested tuple representation of a tree is defined recursively. The tree with one node and no edges is represented by the empty tuple,
()
. A tree withk
subtrees is represented by a tuple of lengthk
in which each element is the nested tuple representation of a subtree.Parameters: - T (NetworkX graph) – An undirected graph object representing a tree.
- root (node) – The node in
T
to interpret as the root of the tree. - canonical_form (bool) – If
True
, each tuple is sorted so that the function returns a canonical form for rooted trees. This means “lighter” subtrees will appear as nested tuples before “heavier” subtrees. In this way, each isomorphic rooted tree has the same nested tuple representation.
Returns: A nested tuple representation of the tree.
Return type: Notes
This function is not the inverse of
from_nested_tuple()
; the only guarantee is that the rooted trees are isomorphic.See also
Examples
The tree need not be a balanced binary tree:
>>> T = nx.Graph() >>> T.add_edges_from([(0, 1), (0, 2), (0, 3)]) >>> T.add_edges_from([(1, 4), (1, 5)]) >>> T.add_edges_from([(3, 6), (3, 7)]) >>> root = 0 >>> nx.to_nested_tuple(T, root) (((), ()), (), ((), ()))
Continuing the above example, if
canonical_form
isTrue
, the nested tuples will be sorted:>>> nx.to_nested_tuple(T, root, canonical_form=True) ((), ((), ()), ((), ()))
Even the path graph can be interpreted as a tree:
>>> T = nx.path_graph(4) >>> root = 0 >>> nx.to_nested_tuple(T, root) ((((),),),)