4

In networkX, I have a tree as DiGraph().

#!/usr/bin/python
# -*- coding: utf-8 -*-
import networkx as nx
t = nx.DiGraph()
t.add_edge(1,'r')
t.add_edge(2,'r')
t.add_edge(3,'r')
t.add_edge(4,2)
t.add_edge(5,2)
t.add_edge(6,5)
print t.edges() 

If a take the node 2 of tree.
how I can get the subtree of 2 ?

Edit

I expected this subtree

[(4,2),(5,2),(6,5)]
1
  • Can you be more specific about what you mean by "subtree of 2" in your oriented/directed tree?
    – Aric
    Oct 25, 2011 at 17:00

1 Answer 1

13

If you mean the subtree rooted at node 2, that's

from networkx.algorithms.traversal.depth_first_search import dfs_tree

subtree_at_2 = dfs_tree(t, 2)

Edit: it seems you've reversed the order of nodes in your edges. In a directed tree, all paths proceed from the root to a leaf, not the other way around. dfs_tree(t.reverse(), 2) gives you the tree that you want, but do change your code.

4
  • with this I get [(2, 'r')] and not is a subtree
    – JuanPablo
    Oct 25, 2011 at 18:02
  • @JuanPablo: that certainly is the subtree rooted at 2 in your graph. You've reversed the edges.
    – Fred Foo
    Oct 25, 2011 at 18:15
  • and in a undirected tree, how I can use dfs_tree ?
    – JuanPablo
    Oct 25, 2011 at 18:22
  • @JuanPablo: in an undirected tree, the notion of a unique subtree rooted at a node simply disappears; no can do. (There are still subtrees, but not unique ones per node.) You can still apply dfs_tree, but it will give you a directed tree containing all nodes, rooted at the node you give as an argument. Try nx.draw(dfs_tree(t.to_undirected(), 2)), for example.
    – Fred Foo
    Oct 25, 2011 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.