Archive

Archive for May, 2010

On reproducible research

16 May 2010 1 comment

Random oriented graphs

This one is from a recent sage-support thread.

Problem

Let $D$ be a digraph and let $u,v$ be vertices of $D$. Then $D$ is said to be oriented if at most one of $uv, vu$ is an edge of $D$. This means that $D$ might not contain any of the edges $vu, uv$. However, if $vu \in E(D)$, then $uv \not\in E(D)$ and vice versa. The problem now is to generate a random oriented graph.

Solution

A quick-and-dirty solution is as follows:

1. Generate a random graph $G$ with RanomGNP, i.e. $G$ is undirected.
2. Let $D$ be the digraph version of $G$, i.e. if $uv$ is an edge of $D$, then $vu$ is also an edge.
3. Let $P$ be the edge removal probability.
4. For each edge $uv \in E(G)$, generate a cutoff probability $p$. If $p \leq P$, remove $uv$ from the digraph $D$. Otherwise $p > P$, so we remove $vu$ from $D$.

Here is sample code using Sage 4.4.1 illustrating the above procedure:

sage: G = graphs.RandomGNP(10, random())
sage: G.edges(labels=False)
[(0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (1, 7), (1, 8), (2, 4), (2, 6), (2, 8), (2, 9), (3, 4), (3, 6), (3, 7), (3, 8), (3, 9), (4, 5), (4, 9), (5, 6), (5, 8), (5, 9), (6, 9), (7, 8), (8, 9)]
sage: D = G.to_directed()
sage: D.edges(labels=False)
[(0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (1, 7), (1, 8), (2, 0), (2, 1), (2, 4), (2, 6), (2, 8), (2, 9), (3, 0), (3, 1), (3, 4), (3, 6), (3, 7), (3, 8), (3, 9), (4, 0), (4, 2), (4, 3), (4, 5), (4, 9), (5, 0), (5, 1), (5, 4), (5, 6), (5, 8), (5, 9), (6, 0), (6, 2), (6, 3), (6, 5), (6, 9), (7, 1), (7, 3), (7, 8), (8, 0), (8, 1), (8, 2), (8, 3), (8, 5), (8, 7), (8, 9), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 8)]
sage: D.size()
56
sage: P = random(); P
0.55638632541078259
sage: for u, v in G.edge_iterator(labels=False):
....:     p = random()
....:     if p <= P:
....:         D.delete_edge(u, v)
....:     else:
....:         D.delete_edge(v, u)
....:
sage: D.edges(labels=False)
[(0, 2), (0, 3), (0, 6), (1, 2), (1, 5), (2, 8), (3, 1), (3, 6), (3, 8), (3, 9), (4, 0), (4, 2), (4, 3), (4, 5), (5, 0), (6, 2), (6, 5), (6, 9), (7, 1), (7, 3), (8, 0), (8, 1), (8, 5), (8, 7), (9, 2), (9, 4), (9, 5), (9, 8)]
sage: D.size()
28


Sage 4.4.2 release schedule

Sage 4.4.2 is intended to be a little release on the way to Sage 5.0. I’m devoting a week or so to managing the release of Sage 4.4.2. Here’s a proposed release schedule I posted to sage-release:

• Sage 4.4.2.alpha0 — release 10th May 2010
• Sage 4.4.2.rc0 — feature freeze; release 15th May 2010
• Anything critical to get Sage 4.4.2.final to stabilize
• Sage 4.4.2.final — release 18th May 2010

I’m being too optimistic here with the above schedule. But we’ll see how things go.

Binary trees and branch cut

1 May 2010 1 comment

The topic and content of this post originate from a question to sage-support. I’m posting the essential responses here so it doesn’t get lost in the sage-support 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 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.

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 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 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')]