[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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
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