igraph-help
[Top][All Lists]

## Re: [igraph] How to enter and process a general tree in python using igr

 From: Tamas Nepusz Subject: Re: [igraph] How to enter and process a general tree in python using igraph Date: Fri, 25 Jun 2010 16:14:35 +0100 User-agent: Mutt/1.5.20 (2009-06-14)

```Hi,

> I want to generate a general tree
Graph.Tree() can generate regular directed and undirected trees for you
with a given number of nodes. "regular" means that almost all nodes have
the same number of neighbours:

>>> g = Graph.Tree(n=15, children=2)
>>> print g
Undirected graph (|V| = 15, |E| = 14)
>>> g.get_edgelist()
[(0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (3,8), (4,9),
(4,10), (5,11), (5,12), (6,13), (6,14)]
>>> plot(g)

If you are looking for other kinds of trees where the branching ratio is
not equal, you have to construct the tree yourself by using

> and then writing algorithms for traversal it

>>> for vertex in tree.bfsiter(0):
...     print vertex.index

The depth first search is not implemented yet, but it's easy to
implement it:

def dfsiter(graph, root):
stack = [root]
visited = set(stack)
while stack:
vertex = stack.pop()
yield vertex
not_visited_neis = set(graph.neighbors(vertex)) - visited
stack.extend(not_visited_neis)
visited.update(not_visited_neis)

for vertex in tree.dfsiter(0):
print vertex.index

> and for finding a certain path from the root to a leaf node.
See the get_shortest_paths() method of the Graph object:

>>> g.shortest_paths(0, [5])
[[0, 2, 5]]

Note that g.shortest_paths can be used to determine the shortest paths
from a given vertex to more than one other vertex:

>>> g.shortest_paths(0, [5, 7])
[[0, 2, 5], [0, 1, 3, 7]]

--
Tamas

```