Binary trees and branch cut
The topic and content of this post originate from a question to sagesupport. I’m posting the essential responses here so it doesn’t get lost in the sagesupport archive.
Problem
How do you construct a binary tree in Sage? If T is a binary tree, how do you cut off a branch of that tree?
Solution
There is as yet no class for representing binary trees in Sage. However, you could use either the classes Graph or DiGraph to construct a graph T and then use the method T.is_tree() to determine whether or not T is a tree. There is also a balanced tree generator. Also missing is a method to determine whether or not a tree is binary. That can be remedied by defining your own function to test the number of children a vertex has. Using Graph to construct a tree, and then test that tree to see that it is binary, is rather difficult because unless you label the vertices to indicate their parents, you don’t know which vertex is a child of which other vertex.
In general, I prefer using DiGraph to construct a tree T and then use the method T.neighbors_out() in testing whether or not T is a binary tree. The reason is that in a digraph that represents a tree, you can think of the outneighbors of a vertex as being the children of that vertex. Here is an example demonstrating the construction of a binary tree rooted at vertex v. By definition, a vertex in a binary tree has at most 2 children. The session below uses this definition to test whether or not a tree is binary.
sage: T = DiGraph({"v": ["a", "w"], ....: "w": ["x", "y"], ....: "x": ["c", "b"], ....: "y": ["z", "d"], ....: "z": ["f", "e"]}) sage: T.vertices() ['a', 'b', 'c', 'd', 'e', 'f', 'v', 'w', 'x', 'y', 'z'] sage: T.edges(labels=None) [('v', 'a'), ('v', 'w'), ('w', 'x'), ('w', 'y'), ('x', 'b'), ('x', 'c'), ('y', 'd'), ('y', 'z'), ('z', 'e'), ('z', 'f')] sage: T.is_tree() True sage: def is_binary_tree(tree): ....: for v in tree.vertex_iterator(): ....: if len(tree.neighbors_out(v)) > 2: ....: return False ....: return True ....: sage: is_binary_tree(T) True
Nathann Cohen offered another way to test that a graph is a binary tree.
sage: def is_binary_tree(g): ....: if g.is_tree() and max(g.degree()) == 3 and g.degree().count(2) == 1: ....: return True ....: return False ....: sage: is_binary_tree(T) True
Once you have determined the root vertex of a branch that you want to cut off, you could use breadthfirst search (or depthfirst search) to determine all vertices in that branch. Again, assume that your binary tree T is represented using the DiGraph class and V is a list of vertices in the branch you want to cut off. You can use the method T.delete_vertices() to cut off that branch. Deleting a vertex v not only deletes v, but also all edges incident on that vertex. Say you have constructed your tree as in the above session and you have determined that the vertex y is the root of the branch you want to cut off. Here is how you can cut off that branch:
sage: V = list(T.breadth_first_search("y")) sage: V ['y', 'd', 'z', 'e', 'f'] sage: T.delete_vertices(V) sage: T.vertices() ['a', 'b', 'c', 'v', 'w', 'x'] sage: T.edges(labels=None) [('v', 'a'), ('v', 'w'), ('w', 'x'), ('x', 'b'), ('x', 'c')]

2 May 2010 at 12:03 amTweets that mention Binary Trees and Branch Cut « mvngu  Topsy.com