Python & NetworkX - 如何检查节点是否 self-looped

Question

我有一个带有 2 个 ID 字段的 table，其中 parent 可以链接到自身：

Child	Parent
1	1
2	1
3	1
4	2
5	3

我使用 networkx 创建了一个有向图，现在正在尝试编写一个函数来识别每一行的所有根和叶并将它们添加回原始数据框：

def find_leaves(G, node):

    d = list(nx.descendants(G, node))+[node]
 
    H = G.subgraph(d)
    return [a for a in H.nodes if H.out_degree(a)==0 | (H.out_degree(a)==1 and <checking whether the node is a self-loop>)]

def find_roots(G, node):
    
    d = list(nx.ancestors(G, node))+[node]
    
    H = G.subgraph(d)
    return [a for a in H.nodes if H.in_degree(a)==0 | (H.in_degree(a)==1 and <checking whether the node is a self-loop>)]

因为 parent/child 可以链接到自身，所以我想添加第二个子句来检查 out/in 度数 = 1 并且该节点是否为自循环。我是 networkx 的新手，但从 2.5 文档来看，大多数函数似乎 self-loop return 图中 self-looped 节点的完整列表，例如nx.nodes_with_selfloops(G).

有没有一种方法可以检查一个节点是否被 self-looped 而不必每次都检查整个列表？

Answer 1

是的。以节点为键将有向图作为字典访问将 return 一个 AtlasView，它提供该节点的所有边。例如

>>> g[2]
AtlasView({1: {}})

因此，要查找节点是否具有连接回自身的边，您只需检查该节点是否存在于该视图中。

def is_self_looped(g, node):
    return node in g[node]

在你的例子中只有 1 个有自循环。

>>> for node in g.nodes:
...     print(node, is_self_looped(g, node))
... 
1 True
2 False
3 False
4 False
5 False

Answer 2

def has_self_loop(G: nx.Graph, node):
    try:
        if G[node][node] != None:
            return True
    except Exception:
        return False


G_edges = [(1, 1), (2, 1), (2, 3), (3, 3)]

G = nx.Graph()
G.add_edges_from(G_edges)

[print(node, "has self loop") for node in G.nodes() if has_self_loop(G, node) == True]

输出：

1 has self loop
3 has self loop

Python & NetworkX - 如何检查节点是否 self-looped

Python & NetworkX - How to check if a node is self-looped

python

networkx

pandas