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

user_15363675 0
Viewed 265

I have a table with 2 ID fields like this, where it is possible for a parent to be linked to itself:

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

I created a digraph using networkx and am now trying to write a function to identify all the roots and leaves for each row and adding them back to the original dataframe:

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>)]

Because a parent/child can be linked to itself, I'm looking to add a second clause to check whether the out/in degree = 1 and the node is a self loop. I am fairly new to networkx but from the 2.5 documentation it seems that most functions for self-loop return an entire list of self-looped nodes in the graph e.g. nx.nodes_with_selfloops(G).

Is there a way to check whether a node is self-looped without having to check through the entire list every time?

pandas networkx python
2 Answers

Yes. Accessing the DiGraph as a dictionary with the node as the key will return an AtlasView, which gives all the edges from that node. e.g.

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

So to find if a node has an edge that connects back to itself you just need to check for the presence of the node in that view.

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

In your example only 1 has a self-loop.

>>> for node in g.nodes:
...     print(node, is_self_looped(g, node))
... 
1 True
2 False
3 False
4 False
5 False
user_13005190 
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]

outputs:

1 has self loop
3 has self loop
user_56762060
Related