如何在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在节点遍历中存在一条边，会发生无限循环吗？

谢谢。

- user478514

---

你应该查看网络X图形的文档：http://networkx.lanl.gov/reference/classes.graph.html#networkx.Graph 大部分的任务都可以通过那里的功能和一点迭代来解决。 - Michael Mauderer

@Michael Mauderer，对于没有属性的节点来说，这么简单吗？ - user478514

属性对你正在做的事情不应该有任何影响。 - Michael Mauderer

你应该给出一个图的示例结构，这样我们才能帮助解决每个问题。 - jterrace

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. 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.

- jterrace

---

谢谢您清晰的演示，但对于问题1，您能否展示更多以确定n131和n221是沿其路径到n的最深节点，如果我们将“n”作为根？我无法想出一个方法使 shortest_path(n, X) 在这种情况下有效，是否还需要涉及 neighbor() 函数？ - user478514

如果n为根节点，则n221不应该是n131的子节点，反之亦然。那么如何检测这种节点并将它们定义为“无子节点”？ - user478514

是的，严格来说这不再是一棵“树”，我不知道该怎么称呼它，但这些边缘确实存在。问题在于如何检测这些存在于这个“类似树形”的结构中的边缘？ - user478514

你只想检测具有两条边的节点吗？ - jterrace

所以，我的想法是检测这种类型的边缘（可以从任何节点作为起点，例如在此示例中，n是起点），这是否可能？ - user478514