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

[Tamas Nepusz]

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
add_vertices() and add_edges() on an empty graph.

> and then writing algorithms for traversal it
The breadth first traversal is already implemented in igraph:

>>> 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