Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# 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 with k subtrees is represented by a tuple of length k 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. A nested tuple representation of the tree. tuple

Notes

This function is not the inverse of from_nested_tuple(); the only guarantee is that the rooted trees are isomorphic.

Examples

The tree need not be a balanced binary tree:

>>> T = nx.Graph()
>>> T.add_edges_from([(0, 1), (0, 2), (0, 3)])
>>> root = 0
>>> nx.to_nested_tuple(T, root)
(((), ()), (), ((), ()))


Continuing the above example, if canonical_form is True, 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)
((((),),),)