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) ((((),),),)