3

I am writing a code to extract information from a directed graph. This graph has cycles as well. For example,

A->B->C->D A->E->F->A B->F->G

From this graph, I want to create a sub graph or the list of the nodes, where the input would be any node, and output would be the graph where the input node is the root, or the list of the nodes that has all the child nodes ( till the end of the graph ) from the input nodes

For example, in the above example, 1. If the input node is C, the output would be D 2. If the input node is B, the output node would be C,D,F,G,A ( Since there is a cycle, which makes A to B bidirectional ) 3. If the input is G, the output is blank or null.

Is there any functionality in python networkx, that I can use to solve this problem ?

Alternatively, is there any other tool that can help me solve this problem ?

Improve this question
2
  • How can the output be C,D,F,G,A if the input is B? Shouldn't it be only C and D? Commented Dec 19, 2017 at 18:22
  • @Swailem95 .. B is dependent on C and D ( 1st line ). B is dependent on F and G ( 3rd line ) , F is dependent on A ( 2nd line ) . It should actually be C,D,F,G,A, E .. I missed that. Commented Dec 19, 2017 at 19:59

2 Answers 2

Reset to default
4

What you want is the function dfs_preorder_nodes(). Here is a little demo based on your data:

import networkx as nx g = nx.DiGraph() g.add_edge('A', 'B') g.add_edge('B', 'C') g.add_edge('C', 'D') g.add_edge('A', 'E') g.add_edge('E', 'F') g.add_edge('F', 'A') g.add_edge('B', 'F') g.add_edge('F', 'G') print('A:', list(nx.dfs_preorder_nodes(g, 'A'))) print('B:', list(nx.dfs_preorder_nodes(g, 'B'))) print('G:', list(nx.dfs_preorder_nodes(g, 'G')))

Output:

A: ['A', 'B', 'C', 'D', 'F', 'G', 'E'] B: ['B', 'C', 'D', 'F', 'A', 'E', 'G'] G: ['G']

The output includes the starting node. Therefore, if you don't want it, just remove the first element from the list.

Note that dfs_preorder_nodes() returns a generator object. That is why I called list() to get usable output.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks so much !! I tried bfs_tree() and dfs_tree() functions , but this one looks better !
4

nx.ego_graph() does exactly what you describe. Using the example given by @Hai Vu:

g = nx.DiGraph() g.add_edge('A', 'B') g.add_edge('B', 'C') g.add_edge('C', 'D') g.add_edge('A', 'E') g.add_edge('E', 'F') g.add_edge('F', 'A') g.add_edge('B', 'F') g.add_edge('F', 'G') a = nx.ego_graph(g, 'A', radius=100) a.node #out: NodeView(('A', 'B', 'C', 'D', 'E', 'F', 'G')) list(nx.ego_graph(g, 'G', radius=100).node) #out: ['G']

radius should be an arbitrarily large number if you would like to get all nodes in the tree until the leafs.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.