python - 如何列出 networkx 中的特定节点/边缘？

Question

假设networkx图中有一个树状结构:

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


      n4------n41
      n5

1. 如何列出所有具有“子节点”及其深度的节点，这里是:n,n1,n13,n2,n22,n4
2. 如何列出没有“子节点”的所有节点，这里是:n11,n12,n21,n41,n5
3. 如何列出孤儿节点，这里是:n5 以及如何列出“孤儿”边，不属于根 n 边，这里是 n4-n41，
4. 如何列出超过 2 个“子节点”的节点，这里是 n,n1
5. 节点遍历中n131,n221有边存在怎么处理，会不会死循环？

谢谢。

Answer 1

图形构造:

>>> 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. 使用 out_degree查找所有有子节点的函数:

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

   请注意，n131 和 n221 也出现在这里，因为它们彼此都有优势。如果需要，您可以过滤掉这些。

2. 所有没有 child 的节点:

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

3. 所有孤立节点，即度数为 0 的节点:

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

   要获取所有孤立的“边”，您可以获取图的组件列表，过滤掉不包含 n 的组件，然后仅保留具有边的组件:

   >>> [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. 有超过 2 个 child 的节点:

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

5. 如果遍历树，就不会出现无限循环。 NetworkX 具有对此具有鲁棒性的遍历算法。