How to list specific node/edge in networkx?

问题:

Suppose one below tree-like structure in networkx graph:

n-----n1----n11
 |     |----n12
 |     |----n13
 |           |----n131 
 |----n2             | 
 |     |-----n21     X
 |     |-----n22     |
 |            |----n221 
 |----n3


      n4------n41
      n5

1. How to list all nodes with "subnode" and its depth, here: n,n1,n13,n2,n22,n4
2. How to list all nodes without "subnode", here: n11,n12,n21,n41,n5
3. How to list orphan node, here: n5 and how to list "orphan" edge, not belongs to root n edge, here n4-n41,
4. How to list node with more than 2 "subnode", here n,n1
5. How to deal with if n131,n221 have an edge exists in nodes traversal, will infinity loop happen?

Thanks.

回答1:

Graph construction:

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3')])
>>> G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13')])
>>> G.add_edges_from([('n2', 'n21'), ('n2', 'n22')])
>>> G.add_edges_from([('n13', 'n131'), ('n22', 'n221')])
>>> G.add_edges_from([('n131', 'n221'), ('n221', 'n131')]
>>> G.add_node('n5')

1. Using the out_degree function to find all the nodes with children:

   >>> [k for k,v in G.out_degree().iteritems() if v > 0]
   ['n13', 'n', 'n131', 'n1', 'n22', 'n2', 'n221', 'n4']
   

   Note that n131 and n221 also show up here since they both have an edge to each other. You could filter these out if you want.

2. All nodes without children:

   >>> [k for k,v in G.out_degree().iteritems() if v == 0]
   ['n12', 'n11', 'n3', 'n41', 'n21', 'n5']
   

3. All orphan nodes, i.e. nodes with degree 0:

   >>> [k for k,v in G.degree().iteritems() if v == 0]
   ['n5']
   

   To get all orphan "edges", you can get the list of components of the graph, filter out the ones that don't contain n and then keep only the ones that have edges:

   >>> [G.edges(component) for component in nx.connected_components(G.to_undirected()) if len(G.edges(component)) > 0 and 'n' not in component]
   [[('n4', 'n41')]]
   

4. Nodes with more than 2 children:

   >>> [k for k,v in G.out_degree().iteritems() if v > 2]
   ['n', 'n1']
   

5. If you traverse the tree, you will not get an infinite loop. NetworkX has traversal algorithms that are robust to this.