Hi Santanu,
On Thu, Apr 29, 2010 at 4:19 PM, Santanu Sarkar
<[email protected]> wrote:
> Hi,
> How one can create a binary tree
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. 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 out-neighbors 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.
[mv...@sage ~]$ sage
----------------------------------------------------------------------
| Sage Version 4.4, Release Date: 2010-04-24 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
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
> and cut some of its branches
> under some conditions continuously in Sage?
The "some conditions" you refer to is up to you to decide. Once you
have determined the root vertex of a branch that satisfies your
condition(s), you could use breadth-first search (or depth-first
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 to 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')]
--
Regards
Minh Van Nguyen
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
