假设networkx
图中有一个树状结构:
n-----n1----n11
| |----n12
| |----n13
| |----n131
|----n2 |
| |-----n21 X
| |-----n22 |
| |----n221
|----n3
n4------n41
n5
- 如何列出所有具有“子节点”及其深度的节点,这里是:n,n1,n13,n2,n22,n4
- 如何列出没有“子节点”的所有节点,这里是:n11,n12,n21,n41,n5
- 如何列出孤儿节点,这里是:n5 以及如何列出“孤儿”边,不属于根 n 边,这里是 n4-n41,
- 如何列出超过 2 个“子节点”的节点,这里是 n,n1
- 节点遍历中n131,n221有边存在怎么处理,会不会死循环?
谢谢。
最佳答案
图形构造:
>>> 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')
使用 out_degree查找所有有子节点的函数:
>>> [k for k,v in G.out_degree().iteritems() if v > 0] ['n13', 'n', 'n131', 'n1', 'n22', 'n2', 'n221', 'n4']
请注意,n131 和 n221 也出现在这里,因为它们彼此都有优势。如果需要,您可以过滤掉这些。
所有没有 child 的节点:
>>> [k for k,v in G.out_degree().iteritems() if v == 0] ['n12', 'n11', 'n3', 'n41', 'n21', 'n5']
所有孤立节点,即度数为 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')]]
有超过 2 个 child 的节点:
>>> [k for k,v in G.out_degree().iteritems() if v > 2] ['n', 'n1']
如果遍历树,就不会出现无限循环。 NetworkX 具有对此具有鲁棒性的遍历算法。
关于python - 如何列出 networkx 中的特定节点/边缘?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12020020/