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)

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.

Returns

A nested tuple representation of the tree.

Return type

tuple

Notes

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

See also

from_nested_tuple(), to_prufer_sequence()

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